以分支定界法求取具時間窗口與群組限制之單一機台批次最小化總完工時間之排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：162

、訪客IP：3.129.247.196

姓名

林欣儀(Hsin-Yi Lin) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以分支定界法求取具時間窗口與群組限制之單一機台批次最小化總完工時間之排程問題
(A Branch and Bound Algorithm for a Single Machine Batch Scheduling Problem with Time Window and Job Family Constraints to Minimize Total Completion Time)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本研究考慮單一機台在群組與時間窗口限制下進行批次加工，求取最小總完工時間之排程問題。本研究設定有數個工件要在同個機台上進行批次加工，每個批次能放入的工件有數量上限。因應半導體製程之特性，每個工件有其製程參數，記錄事先設定好的溫度、濕度、時間等加工限制參數，工件依不同的製程參數可被分類成不同群組，只有相同群組的工件才能在同一批次中進行加工。在時間方面，每個工件不一定同時到達加工站，且根據製程參數中時間的限制，工件在到達工作站後一段時間內一定要開始加工，否則該工件會報廢，本研究依此兩時間限制作為工件的時間窗口限制其開始加工時間。
我們提出一分支定界法求取問題之最小總完工時間。首先，我們將工件分組產生數個子問題以縮小問題大小提升演算法求解效率，接著在限制下決定哪些工件可以被放在同批次中進行加工，窮舉所有可能的工件組合後決定其加工順序並且提出刪枝的方法提高演算法求解速度。實驗的分析顯示，我們所提出的分支定界法所求取的解為最佳解，我們也證明事先將工件分組能提升演算法之效率，減少運算時間高達83.87%。另外，我們逐一檢視刪枝方法的表現並根據結果將其順序重新排列，演算法的效率也能有所提升。

摘要(英)

Semiconductor manufacturing features several characteristics: recipe, Q-time, batch processing. Recipe records the process parameters such as time, temperature, humidity, chemical restriction, etc. Q-time is the time constraint of jobs. Motivated by these characteristics, we study a single machine batch scheduling problem, where jobs are processed simultaneously. Using the three fields α | β | γ, our problem can be represented as 1 | p-batch,r_j,R_j,┤ incompat | ∑C_j┤. We assume there are n jobs with arbitrary release time and should start to process in remaining lifetime. Jobs has its own recipe and jobs using the different recipe can’t be processed together.
We develop a Branch and bound algorithm to minimize total completion time of our problem. First, we separate jobs into several groups by a grouping method to narrow down the problem size, then we enumerate all the possible combinations of batches and assign one of them after initial scheduling while branching out. We propose several propositions and a bounding scheme to cut off some branches. The computational analysis shows that the solution our Branch and bound algorithm found is optimal and the grouping method can effectively decrease 83.87% of run time. Finally, we find that the sequence of propositions while applying them to eliminate nodes can improve the efficiency of our algorithm.

關鍵字(中)

★ 單一機台
★ 批次加工
★ 群組限制
★ 時間窗口
★ 總完工時間
★ 分枝定界法

關鍵字(英)

★ Single machine
★ Batch processing
★ Job family
★ Time window
★ Total completion time
★ Branch and bound algorithm

論文目次

摘要 i
Abstract ii
Contents iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Research background and motivation 1
1.2 Problem definition 2
1.3 Research objective 3
1.4 Research methodology 4
1.5 Research framework 4
Chapter 2 Literature Review 6
2.1 Single machine batch processing 6
2.2 Scheduling problems with job family constraint 7
2.3 Scheduling problems with time window constraint 8
2.4 Branch and bound algorithm 9
Chapter 3 Methodology 10
3.1 Notations 10
3.2 Propositions 11
3.3 Branch and bound 20
3.3.1 Node 20
3.3.2 Grouping method 21
3.3.3 Branching scheme 21
3.3.4 Searching strategy 23
3.3.5 Bounding scheme 24
3.3.6 Branch and bound algorithm 27
Chapter 4 Computational Analysis 33
4.1 Generating test problems 33
4.2 Performance of the Branch and bound algorithm 33
4.2.1 Validation of branch and bound algorithm 34
4.2.2 Performance of Grouping method 36
4.3 Performances of propositions and lower bound 39
Chapter 5 Conclusion 43
5.1 Research contribution 43
5.2 Research limitation 44
5.3 Further research 44
Reference 45

參考文獻

Reference
[1] Ahmadi, J. H., Ahmadi, R. H., Dasu, S., & Tang, C. S., Batching and Scheduling Jobs on Batch and Discrete Processors. Operations Research, 40(4), 750–763, 1992.
[2] Azizoglu, M., & Webster, S., Scheduling a batch processing machine with incompatible job families. Computers and Industrial Engineering, 39(3–4), 325–335, 2001.
[3] Balasubramanian, H., Mönch, L., Fowler, J., & Pfund, M., Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness. International Journal of Production Research, 42(8), 1621–1638, 2004.
[4] Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T., & Van De Velde, S. L., Scheduling a batching machine. Journal of Scheduling, 1(1), 31–54, 1998.
[5] Chand, S., Traub, R., & Uzsoy, R., Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm. Naval Research Logistics, 43(5), 709–719, 1996.
[6] Chandru, V., Lee, C. Y., & Uzsoy, R., Minimizing total completion time on batch processing machines. International Journal of Production Research, 31(9), 2097–2121, 1993.
[7] Chandru, Vijaya, Lee, C. Y., & Uzsoy, R., Minimizing total completion time on a batch processing machine with job families. Operations Research Letters, 13(2), 61–65, 1993.
[8] Cheng, B., Cai, J., Yang, S., & Hu, X., Algorithms for scheduling incompatible job families on single batching machine with limited capacity. Computers and Industrial Engineering, 75(1), 116–120, 2014.
[9] Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R.,Optimization and approximation in deterministic machine scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326, 1979.
[10] Hochbaum, D. S., & Landy, D., Scheduling semiconductor burn-in operations to minimize total flowtime. Operations Research, 45(6), 874–885, 1997.
[11] Kurz, M. E., & Mason, S. J., Minimizing total weighted tardiness on a batch-processing machine with incompatible job families and job ready times. International Journal of Production Research, 46(1), 131–151, 2008.
[12] Land, A. H., & Doig, A. G., The Econometric Society. The Economic Journal, 42(166), 331, 1960.
[13] Li, S., A hybrid two-stage flowshop with part family, batch production, major and minor set-ups. European Journal of Operational Research, 102(1), 142–156, 1997.
[14] Mathirajan, M., & Sivakumar, A. I., A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor. International Journal of Advanced Manufacturing Technology, 29(9–10), 990–1001, 2006.
[15] Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C., Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19, 79–102, 2016.
[16] Morrison, D. R., Sauppe, J. J., Zhang, W., Jacobson, S. H., & Sewell, E. C., Cyclic Best First Search: Using Contours to Guide Branch-and-Bound Algorithms. Naval Research Logistics (NRL), 64(1), 64–82, 2017.
[17] Mosheiov, G., Due-date assignment with asymmetric earliness-tardiness cost. Journal of the Operational Research Society, 54(11), 1222–1224, 2003.
[18] Potts, C. N., & Kovalyov, M. Y., Scheduling with batching: a review. European Journal of Operational Research, 120(2), 228–249, 2000.
[19] Su, L. H., A hybrid two-stage flowshop with limited waiting time constraints. Computers and Industrial Engineering, 44(3), 409–424, 2003.
[20] Sung, C. S., & Choung, Y. I., Minimizing makespan on a single burn-in oven in semiconductor manufacturing. European Journal of Operational Research, 120(3), 559–574, 2000.
[21] Sung, C. S., Choung, Y. I., Hong, J. M., & Kim, Y. H., Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals. Computers and Operations Research, 29(8), 995–1007, 2002.
[22] Tangudu, S. K., & 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 and Control, 17(7), 728–741, 2006.
[23] Uzsoy, R., Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research, 32(7), 1615–1635, 1994.
[24] Uzsoy, R., Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685–2708, 1995.
[25] Webster, S., & Baker, K. R., Scheduling groups of jobs on a single machine. In Operations Research (Vol. 43, Issue 4, pp. 692–703),1995.
[26] 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.
[27] Yao, S., Jiang, Z., & Li, N., A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals. Computers and Operations Research, 39(5), 939–951, 2012.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2020-8-18

推文