成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	陳志偉 Chen, Chih-wei
論文名稱：	以問題縮減與局部搜尋法處理半導體製造業的無關聯平行機台排程問題 Scheduling Unrelated Parallel Machines in Semiconductor Manufacturing by Problem Reduction and Local Search Heuristics
指導教授：	王逸琳 Wang, I-Lin
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業與資訊管理學系 Department of Industrial and Information Management
論文出版年：	2009
畢業學年度：	97
語文別：	英文
論文頁數：	64
中文關鍵詞：	排程、局部搜尋、指派法則、混整數規劃
外文關鍵詞：	dispatching rule, local search, scheduling, mixed integer programming
相關次數：	點閱：73 下載：8
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本論文探討一個半導體製造業常見的困難排程問題，該問題必須考慮順序相關整備時間、釋放時間、截止時間與機台使用限制，以產生最少的延遲工件並縮小總製造時間。本論文首先提出一個混整數規劃模式，然該模式僅能求解非常小規模的排程問題。為獲得更佳的求解效率，我們使用單一機台可能加工件數的上限來縮減整數規劃模式大小，雖然運用此技巧之後的混整數規劃模式可處理稍大的排程問題，但其效率仍與現實的排程需求相去甚遠；因此我們再提出一個結合指派法則與局部搜尋的演算法來進行求解。此指派法則乃以傳統的最早到期日優先之派工法則為基礎，並預先考量突發急件的可能性，以減少機台之整備次數並加速急件的處理。經測試顯示此指派法則能有效的減少整備時間而局部搜尋也能有效的改善排程結果。此演算法在處理小規模排程問題時能提供與最佳解十分接近的排程；而針對混整數規劃無法處理的大規模排程問題，該演算法也可提供優良的排程結果。

We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be solved efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to largely reduce the size of the MIP formulation. In order to effectively handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job with the earliest due date to a machine with least recipe changeover (EDDLC) and try to reoptimize the solution by some local search heuristics which involve interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually give solutions very close to the exact optimum for smaller scheduling problems, and can also produce good solutions for scheduling up to 200 jobs on 40 machines within 10 minutes.

Contents
List of Tables ................................ iii
List of Figures ................................ v
Chapter 1.   INTRODUCTION ................................ 1
1.1.   Background and motivation ................................ 1
1.2.   Objectives and proposed approaches ................................ 2
1.3.   Scope and limitations ................................ 3
1.4.   Overview of thesis ................................ 6
Chapter 2.   LITERATURE REVIEW ................................ 7
2.1.   Scheduling problems ................................ 7
2.2.   Complexity of scheduling parallel machines with sequence dependent setup time ................................ 8
2.3.   Mixed integer programming formulations ................................ 9
2.4.   Dispatching rules ................................ 10
2.5.   Parallel machine scheduling ................................ 11
2.6.   Summary ................................ 14
Chapter 3.   PROBLEM DEFINITIONS AND MIP FORMULATIONS ................................ 16
3.1.   Assumptions ................................ 16
3.2.   Notations ................................ 16
3.3.   A mixed integer programming formulation ................................ 17
3.4.   A heuristic to reduce the size of MIP formulation ................................ 20
3.5.   Summary ................................ 23
Chapter 4.   HEURISTICS OF DISPATCHING RULES AND REOPTIMIZATION ................................ 24
4.1.   A dispatching rule considering least changeover time ................................ 24
4.2.   Reoptimization heuristics ................................ 28
4.3.   Tabu search ................................ 32
4.4.   Summary ................................ 33
Chapter 5.   COMPUTATIONAL EXPERIMENTS AND ANALYSES ................................ 34
5.1.   Settings for computational experiments ................................ 34
5.2.   Sensitivity analyses ................................ 35
5.3.   Results of computational experiments ................................ 35
5.4.   Computational testings on cases of long job lists ................................ 42
5.5.   Summary ................................ 42
Chapter 6.   CONCLUSIONS AND SUGGESTIONS ................................ 45
6.1.   Summary and contributions ................................ 45
6.2.   Suggestions for future research ................................ 47
References ................................ 48
Appendix A.   Pseudocode of EDDLC ................................ 50
Appendix B.   Results of pre-test of tabu search ................................ 52
Appendix C.   Results of scenario 2 ................................ 53
Appendix D.   Results of scenario 3 ................................ 55
Appendix E.   Results of scenario 4 ................................ 57
Appendix F.   Results of scenario 6 ................................ 59
Appendix G.   Results of scenario 7 ................................ 61
Appendix H.   Results of scenario 8 ................................ 63
List of Tables
1.1   Settings of example 1. ................................ 4
1.2   Settings of example 2. ................................ 4
1.3   Settings of example 3. ................................ 4
2.1   Classification of machine configuration. ................................ 7
2.2   Classification of processing restrictions. ................................ 8
2.3   Classification of objective. ................................ 8
2.4   Summary of dispatching rules. ................................ 12
2.5   References about parallel machine scheduling. ................................ 12
3.1   Indices and sets about model. ................................ 17
3.2   Given constants about model. ................................ 17
3.3   Decision variables about model. ................................ 17
3.4   Problem description of example. ................................ 20
5.1   Characteristic of each scenario. ................................ 35
5.2   Changeover rate. ................................ 37
5.3   Running time in scenario 1. ................................ 37
5.4   Proportion of tardy jobs in scenario 1. ................................ 39
5.5   Makespan in scenario 1. ................................ 39
5.6   Running time in scenario 5. ................................ 40
5.7   Proportion of tardy jobs in scenario 5. ................................ 40
5.8   Makespan in scenario 5. ................................ 42
C.1   Running time in scenario 2. ................................ 54
C.2   Proportion of tardy jobs in scenario 2. ................................ 54
C.3   Makespan in scenario 2. ................................ 54
D.1   Running time in scenario 3. ................................ 56
D.2   Proportion of tardy jobs in scenario 3. ................................ 56
D.3   Makespan in scenario 3. ................................ 56
E.1   Running time in scenario 4. ................................ 58
E.2   Proportion of tardy jobs in scenario 4. ................................ 58
E.3   Makespan in scenario 4. ................................ 58
F.1   Running time in scenario 6. ................................ 60
F.2   Proportion of tardy jobs in scenario 6. ................................ 60
F.3   Makespan in scenario 6. ................................ 60
G.1   Running time in scenario 7. ................................ 62
G.2   Proportion of tardy jobs in scenario 7. ................................ 62
G.3   Makespan in scenario 7. ................................ 62
H.1   Running time in scenario 8. ................................ 64
H.2   Proportion of tardy jobs in scenario 8. ................................ 64
H.3   Makespan in scenario 8. ................................ 64
List of Figures
3.1   A possible schedule and its corresponding variables. ................................ 19
3.2   Result of a small scheduling example. ................................ 20
3.3   A tool group example to illustrate our proposed heuristic to reduce the number of positions for job assignment in a single machine. ................................ 22
4.1   Flow chart of EDDLC. ................................ 25
4.2   Flow chart of the EDDLC job selection mechanism. ................................ 26
4.3   The proposed interchange mechanism. ................................ 28
4.4   The proposed translocation mechanism. ................................ 29
4.5   The proposed transposition mechanism. ................................ 29
4.6   Pseudocodes of EffROP. ................................ 31
4.7   Proportion of successful interchange length. ................................ 32
4.8   Pseudocodes of tabu search. ................................ 33
5.1   Running time in scenario 1. ................................ 38
5.2   Proportion of tardy jobs in scenario 1. ................................ 38
5.3   Makespan in scenario 1. ................................ 39
5.4   Running time in scenario 5. ................................ 40
5.5   Proportion of tardy jobs in scenario 5. ................................ 41
5.6   Makespan in scenario 5. ................................ 41
5.7   Running time with long job lists. ................................ 43
5.8   Proportion of tardy jobs with long job lists. ................................ 43
5.9   Makespan with long job lists. ................................ 44
A.1   Step 1 of EDDLC. ................................ 50
A.2   Step 2 of EDDLC. ................................ 50
A.3   Step 3 of EDDLC. ................................ 50
A.4   Step 4 of EDDLC. ................................ 51
A.5   Step 5 of EDDLC. ................................ 51
A.6   Step 6 of EDDLC. ................................ 51
B.1   Running time in pre-test of tabu search. ................................ 52
B.2   Proportion of tardy jobs in pre-test of tabu search. ................................ 52
B.3   Makespan in pre-test of tabu search. ................................ 52
C.1   Running time in scenario 2. ................................ 53
C.2   Proportion of tardy jobs in scenario 2. ................................ 53
C.3   Makespan in scenario 2. ................................ 53
D.1   Running time in scenario 3. ................................ 55
D.2   Proportion of tardy jobs in scenario 3. ................................ 55
D.3   Makespan in scenario 3. ................................ 55
E.1   Running time in scenario 4. ................................ 57
E.2   Proportion of tardy jobs in scenario 4. ................................ 57
E.3   Makespan in scenario 4. ................................ 57
F.1   Running time in scenario 6. ................................ 59
F.2   Proportion of tardy jobs in scenario 6. ................................ 59
F.3   Makespan in scenario 6. ................................ 59
G.1   Running time in scenario 7. ................................ 61
G.2   Proportion of tardy jobs in scenario 7. ................................ 61
G.3   Makespan in scenario 7. ................................ 61
H.1   Running time in scenario 8. ................................ 63
H.2   Proportion of tardy jobs in scenario 8. ................................ 63
H.3   Makespan in scenario 8. ................................ 63
                                    

[1]Altendorfer, K., B. Kabelka, and W. Stöher. "A New Dispatching Rule for Optimizing Machine Utilization at a Semiconductor Test Field", Advanced Semiconductor Manufacturing Conference, 2007 IEEE/SEMI, 188-193, 2007.
[2]Ariz, Y., and D. Raviv. "Dispatching in a Workstation Belonging to a Re-Entrant Production Line under Sequence-Dependent Set-up Times", Production Planning & Control Vol. 9, No. 7, 690-699, 1998.
[3]Balakrishnan, N., J. J. Kanet, and S. V. Sridharan. "Early/Tardy Scheduling with Sequence Dependent Setups on Uniform Parallel Machines", Computers & Operations Research Vol. 26, No. 2, 127-141, 1999.
[4]Bank, J., and F. Werner. "Heuristic Algorithms for Unrelated Parallel-Machine Scheduling with a Common Due Date, Release Dates, and Linear Earliness and Tardiness Penalties", Mathematical and Computer Modelling Vol. 33, 363-383, 2001.
[5]Bilge, Ü., F. Kirac M. Kurtulan, and P. Pekgün. "A Tabu Search Algorithm for Parallel Machine Total Tardiness Problem", Computers & Operations Research Vol. 31, No. 3, 397-414, 2004.
[6]Blackstone, J. H., D. T. Phillips, and G. L. Hogg. "A State-of-the-Art Survey of Dispatching Rules for Manufacturing Job Shop Operations", International Journal of Production Research Vol. 20, No. 1, 27-45, 1982.
[7]Carlier, J. "Scheduling Jobs with Release Dates and Tails on Identical Machines to Minimize the Makespan", European Journal of Operational Research Vol. 29, No. 3, 298-306, 1987.
[8]Haupt, R. "A Survey of Priority Rule-Based Scheduling", OR Spectrum Vol. 11, No. 1, 3-16, 1999.
[9]Kim, C. O., and H. J. Shin. "Scheduling Jobs on Parallel Machines: A Restricted Tabu Search Approach", The International Journal of Advanced Manufacturing Technology Vol. 22, No. 3, 278-287, 2003.
[10]Kim, S. S., H. J. Shin, D. H. Eom, and C. O. Kim. "A Due Date Density-Based Categorising Heuristic for Parallel Machines Scheduling", The International Journal of Advanced Manufacturing Technology Vol. 22, No. 9, 753-760, 2003.
[11]Kurz, M. E., and R. G. Askin. "Heuristic Scheduling of Parallel Machines with Sequence-Dependent Set-up Times", International Journal of Production Research Vol. 39, No. 16, 3747-3769, 2001.
[12]Lee, Y. H., K. Bhaskaran, and M. Pinedo. "A Heuristic to Minimize the Total Weighted Tardiness with Sequence Dependent Setups", IIE transactions Vol. 29, 45-52, 1997.
[13]Logendran, R., B. McDonell, and B. Smucker. "Scheduling Unrelated Parallel Machines with Sequence-Dependent Setups", Computers & Operations Research Vol. 34, No. 11, 3420-3438, 2007.
[14]Ovacik, I. M., and R. Uzsoy. "Rolling Horizon Procedures for Dynamic Parallel Machine Scheduling with Sequence-Dependent Setup Times", International Journal of Production Research Vol. 33, No. 11, 3173-3192, 1995.
[15]Pinedo, M. Scheduling Theory Algorithm and Systems, Prentice Hall Englewood Cliffs, New Jersey, 1995.
[16]Schutten, J. M. J. "List Scheduling Revisited", Operations Research Letters Vol. 18, No. 4, 167-170, 1996.
[17]Sivrikaya-Serifoglu, F., and G. Ulusoy. "Parallel Machine Scheduling with Earliness and Tardiness Penalties", Computers & Operations Research Vol. 26, No. 8, 773-787, 1999.
[18]Wang, C., H. Ghenniwa, and W. Shen. "Heuristic Scheduling Algorithm for Flexible Manufacturing Systems with Partially Overlapping Machine Capabilities", Mechatronics and Automation, 2005 IEEE International Conference Vol. 3, 1139-1144, 2005.
[19]Zhu, X., and W. E. Wilhelm. "Scheduling and Lot Sizing with Sequence-Dependent Setup: A Literature Review", IIE transactions Vol. 38, No. 11, 987-1007, 2006.

校內：2011-08-11公開
校外：2011-08-11公開

簡易檢索 / 詳目顯示

相關論文