以分支定界法求取具時間窗口限制之單一批次加工機台最小化完工時間

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：19

、訪客IP：18.117.186.92

姓名

郭哲瑋(ZHE-WEI GUO) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以分支定界法求取具時間窗口限制之單一批次加工機台最小化完工時間
(A branch and bound algorithm for single batch processing machine with time window constraint to minimize makespan)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2026-1-1以後開放)

摘要(中)

本研究主旨在探討單一批次加工機台在工件具時間窗口限制下極小化完工時間之排程問題。此單一機台具有固定的批次容量上限，每個工件具有一定的釋放時間和工件大小。在工件被釋放後必須在特定時間內開始加工；此特性稱為時間窗口。
我們建立一多層分離圖來表示此排程問題。在多層分離圖中，上層的批次節點之間已事先給定了表示加工順序的連結弧線；下層的每個工件節點和上層所有批次節點間皆有往來的虛擬弧線以此表示待定的指派關係。我們提出一個分支定界演算法去選定層間不同的虛擬弧線成為連結弧線來尋找這個問題的一個最佳解。

摘要(英)

We study a scheduling problem on the single batch processing machine to minimize the makespan. The single batch processing machine has a stable batch capacity indicating the total size of any formed batch cannot exceed the capacity. Each job has a time window to indicate the maximum waiting time of the job.
We establish a multiple-layer disjunctive graph to represent this scheduling problem. In a multiple-layer disjunctive graph, the conjunctive arcs in the upper-layer have been given to represent the processing sequence of batch nodes. The disjunctive arcs in the inter-layer represent the problem of the assignment of jobs to the batches. We purpose a branch and bound algorithm to solve the problem.

關鍵字(中)

★ 單機台
★ 時間窗口
★ 批量
★ 分支定界法
★ 排程
★ 最晚完工時間

關鍵字(英)

★ Single machine
★ Batch processing
★ Time window
★ Makespan
★ Branch and bound algorithm

論文目次

摘要-ii
Abstract----iii
Table of contents----iv
List of figures.----vi
List of tables---- vii
Chapter 1 Introduction ---1
1.1 Research background and motivation ---1
1.2 Problem description ---3
1.3 Research objectives ---4
1.4 Research methodology ---4
1.5 Research framework ---5
Chapter 2 Literature Review ---7
2.1 Batch processing ---7
2.2 Time window ---8
2.3 Disjunctive graph ---8
Chapter 3 Branch-and-Bound algorithm ---10
3.1 Notations ---10
3.2 Multiple-layer disjunctive graph ---11
3.2.1 Node set ---11
3.2.2 Conjunctive arc set and disjunctive arc set---12
3.3 Combination of batches ---13
3.4 Branch and bound method ---14
3.4.1 Search strategy ---14
3.4.2 Node representation ---17
3.4.3 Branching scheme ---17
3.4.4 Bounding scheme ---20
3.4.5 Input and output determination ---21
3.4.6 Branch and bound algorithm ---22
Chapter 4 Computational analysis ---24
4.1 Test problem generation ---24
4.2 Validation of branch and bound algorithm ---25
4.3 Evaluation of branch and bound algorithm ---29
4.3.1 Performance of propositions ---29
4.3.2 Performance of branch and bound algorithm ---31
4.3.3 Maximum size of an instance ---32
Chapter 5 Conclusion ---34
5.1 Research contribution ---34
5.2 Research limitation ---35
5.3 Further research ---35
Reference ---36
Appendix A ---38

參考文獻

[1] Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., and Van De Velde, S. L., Scheduling a batching machine. Journal of scheduling, 1(1), 31-54, 1998.
[2] Carlier, J. “The one-machine sequencing problem”, European Journal of Operational Research, 11(1), 42-47, 1982.
[3] Carlier, J., and Pinson, É., An algorithm for solving the job-shop problem. Management science, 35(2), 164-176, 1989.
[4] Dupont, L and Dhaenens-Flipo, C, “Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure”, Computers & operations research, 29(7), 807-819, 2002.
[5] Dupont, L and Ghazvini., F. J. “Minimizing makespan on a single batch processing machine with non-identical job sizes”, European Journal of Automation, 32(4), 431-440, 1998.
[6] Ghazvini, F. J., & Dupont, L., Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes. International Journal of Production Economics, 55(3), 273-280,1998.
[7] Graham, R. L., Lawler, E. L., Lenstra, J. K., and Kan, A. R, “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of discrete mathematics, Vol. 5. Elsevier, 287-326, 1979.
[8] Hu, H. B., Li, C. H., and Miao, Q. Y., “Opinion diffusion on multilayer social networks”, Advances in Complex Systems, 20(06n07), 1750015, 2017.
[9] Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., & Porter, M. A., Multilayer networks. Journal of complex networks, 2(3), 203-271, 2014.
[10] Li, C. L., and Lee, C. Y., Scheduling with agreeable release times and due dates on a batch processing machine. European Journal of Operational Research, 96(3), 564-569, 1997.
[11] Magnanti, T. L., & Orlin, J. B., Network Flows. PHI Englewood Cliffs NJ, 1993.
[12] Mönch, L., Fowler, J. W., Dauzère-Pérès, S., Mason, S. J., & Rose, O. A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of scheduling, 14(6), 583-599, 2011.
[13] Morrison, D. R., Jacobson, S. H., Sauppe, J. J., and Sewell, E. C, Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19, 79-102, 2016.
[14] Morrison, D. R., Sauppe, J. J., Zhang, W., Jacobson, S. H., and Sewell, E. C., Cyclic best first search: Using contours to guide branch‐and‐bound algorithms. Naval Research Logistics (NRL), 64(1), 64-82, 2017.
[15] Sheen, G. J., & Liao, L. W., A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags. European journal of operational research, 181(1), 102-116, 2007.
[16] Sung, C. S., and Choung, Y. I., Minimizing makespan on a single burn-in oven in semiconductor manufacturing. European Journal of Operational Research, 120(3), 559-574, 2000.
[17] Sung, C. S., Kim, Y. H., and Yoon, S. H., A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines. European Journal of Operational Research, 121(1), 179-192, 2000.
[18] Tangudu, S. K., and Kurz, M. E., A branch and bound algorithm to minimise total weighted tardiness on a single batch processing machine with ready times and incompatible job families. Production Planning & Control, 17(7), 728-741, 2006.
[19] Uzsoy, R. Scheduling a single batch processing machine with non-identical job sizes. The International Journal of Production Research, 32(7), 1615-1635, 1994.
[20] Uzsoy, R., Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685-2708, 1995.
[21] Zhang, W., Sauppe, J. J., & Jacobson, S. H., Comparison of the number of nodes explored by cyclic best first search with depth contour and best first search. Computers & Operations Research, 126, 105129, 2021.
[22] Carlier, J., and Pinson, E., Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78(2), 146-161, 1994.
[23] Brucker, P., Jurisch, B., and Sievers, B., A branch and bound algorithm for the job-shop scheduling problem. Discrete applied mathematics, 49(1-3), 107-127, 1994.
[24] Yan, P., Chu, C., Yang, N., & Che, A., A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows. International Journal of Production Research, 48(21), 6461-6480, 2010.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2021-7-14

推文