以分支定界法基於啟發式演算法求取具時 間窗口限制之平行機台之批次處理問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：13

、訪客IP：3.144.251.83

姓名

彭昭揚(Peng-Chao Yang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以分支定界法基於啟發式演算法求取具時間窗口限制之平行機台之批次處理問題
(A Branch-and-bound Based Heuristic for Parallel Batch Processing Problem with Time Window Constraint)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

在此研究中，我們考慮具有批次的平行機台在具有時間窗口的限制條件下，求取最小化的完工時間。本研究環境中在加工特性上面會有多個不同的工件在多個相同類型機台以批次的方式進行加工，並且每個批次都有固定的數量上限制；在時間方面，每個工件不一定同時到達加工點，此外根據製成參數中關於時間的限制表示：工件在到達工作站後一段時間內一定要開始加工，否則該工件會報廢且不得重工，本研究會依工件存活時間的限制作為工件的時間窗口進行排程規劃。
我們提出一分支定界法求取該問題之最小化完工時間，並使用時間紀元的方法來做為每次的拓展子問題，而時間紀元可以記錄每個可能拓展子問題的時間點並藉由一些算法可以計算出下個拓展子問題的時間紀元，且在每一個子問題使用在批次排程的問題上我們使用冪集的方式將可能的批次組合窮舉出來，搜尋方式使用循環最佳優先搜索的方法進行探索，我們所提出的分支定界法所求取的解為近似解。

摘要(英)

Semiconductor manufacturing features several characteristics: Q-time, batch processing. Q-time is the time constraint of jobs. Batch processing is a kind of
processing method in process. Motivated by these characteristics, we study parallel batch processing machines scheduling problem where jobs are processed
simultaneously. We assume there are ? jobs with arbitrary release time and should start to process in their remaining lifetime.
We develop a Branch and bound based heuristic method to minimize makespan of our problem. First, we calculate time epoch to know which time point will assigned a
batch to machine, then we will we enumerate all the possible combinations of batches by batch scheme and assign one of batch combination after initial scheduling while branching out. We propose several propositions and bounding schemes to cut off some branches. The computational analysis shows that the solution our Branch and bound algorithm found is feasible and the gap between our branch-and-bound algorithm heuristic and the optimal solution is lower than 10%.

關鍵字(中)

★ 平行機台
★ 批次加工
★ 時間窗口
★ 最後完工時間
★ 分枝定界法
★ 啟發式演算法

關鍵字(英)

★ Parallel machines
★ Batch processing
★ Time window
★ makespan
★ Branch and bound heuristic

論文目次

Table of content
摘要 i
Abstract ii
Table of content iii
List of figures v
List of table vi
Chapter 1. Introduction 1
1.1 Research background and motivation 1
1.2 Problem definition 2
1.3 Research objectives 4
1.4 Research methodology 4
1.5 Research framework 5
Chapter 2. Literature Review 7
2.1 Parallel batch processing machines scheduling 7
2.2 Scheduling problems with time window constraint 7
2.3 Time epoch set concept 8
2.4 Branch and bound algorithm 9
Chapter 3. The branch-and-bound algorithm 11
3.1 Notations 11
3.2 Time epoch 12
3.3 Batch scheme 13
3.4 Pruning rules 15
3.5 Branching scheme 17
3.6 Bounding schemes 20
3.6.1 Upper bound 20
3.6.2 Lower bound 20
3.7 Search strategy 22
Chapter 4. Computation Analysis 26
4.1 Test problem generation 26
4.2 Validation of the branch-and-bound algorithm based heuristic 28
4.3 Performance of the of the branch-and-bound algorithm based heuristic 31
Chapter 5. Conclusion 36
5.1 Research Contribution 36
5.2 Research Limitation 36
5.3 Further Research 36
Appendix 38
Appendix A. The branch-and-bound algorithm 38
Appendix B. Propositions 39
Appendix C. Detail Experiments from 2 machines 10 jobs 41
Reference 50

參考文獻

[1] Chris N. Potts, Mikhail Y. Kovalyov. “Scheduling with batching: A review”, European Journal of Operational Research 120 228±249, 2000.
[2] C.S. Sung, Y.I. Choung. “Minimizing makespan on a single burn-in oven in semiconductor manufacturing”, European Journal of Operational Research 120 559±574, 2000.
[3] David R. Morrison, Jason J. Sauppe, Wenda Zhang, Sheldon H. Jacobson, Edward C. Sewell 1Yelp, San Francisco, CA. “Cyclic best first search: using contours to guide branch-and-bound algorithms”, Naval Research Logistics 64: 64–82, 2017.
[4] Dong-Won Kima, Kyong-Hee Kima, Wooseung Jangb, F. Frank Chen. “Unrelated parallel machine scheduling with setup times using simulated annealing”, Robotics and Computer Integrated Manufacturing 18 223–231, 2002.
[5] Dror, M., Stern, H., and Lenstra, J.K. “Parallel machine scheduling: processing rates dependent on number of jobs in operation”, Management Science 33/8, 1001-1009, 1987.
[6] Huaping Chena, Bing Dua and George Q. Huang. “Metaheuristics to minimise makespan on parallel batch processing machines with dynamic job arrivals”. International Journal of Computer Integrated Manufacturing Vol. 23, No. 10, October, 942–956, 2010.
[7] José Elias C. Arroyo, Joseph Y.-T. Leung. “Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times”, Computers and Operation Research 2016.
[8] Jonathan F. Bard, Siwate Rojanasoonthon, “A Branch-and-price algorithm for parallel machine scheduling with time windows and job priorities”, Wiley Periodicals, Inc. Naval Research Logistics 53: 24–44, 2005.
[9] Ju-Yong Lee and Yeong-Dae Kim. “A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint”, Journal of the Operational Research Society, 1–13, 2015.
[10] Lu-Wen Liao, Gwo-Ji Sheen. “Parallel machine scheduling with machine availability and eligibility constraints”, European Journal of Operational Research 184 458–467, 2008.
[11] M.R. Garey and D.S. Johnson, “Strong NP-completeness results: motivation, examples and implications”, Journal of the Association for Computing Machinery 25, 499-508, 1978.
[12] M. Mathirajan · A.I. Sivakumar. “A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor”, Int J Advance Manufacturing Technology 29: 990–100, 2006.
[13] Onur Ozturk, Mehmet A. Begen and Gregory S. Zaric. “A branch and bound based heuristic for makespan minimization of washing operations in hospital sterilization services”. European Journal of Operational Research, 2014.
[14] Onur Ozturk, Mehmet A. Begen & Gregory S. Zaric. “A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan”. International Journal of Production Research, 2016.
[15] Purushothaman Damodaran, Mario C. “Vélez-Gallego. A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times”, Expert Systems with Applications 39: 1451–1458, 2012.
[16] XiaoLin Li, YanLi Huang, Qi Tan, HuaPing Chen. “Scheduling unrelated parallel batch processing machines with non-identical job sizes”, Computers & Operations Research 40, 2983–2990, 2013.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2021-7-14

推文