臺灣博碩士論文加值系統

本研究針對具時窗限制的併批暨排程優化問題提出三種蟻拓演算求解方法，並詳細定義此種問題的數學模式。求解目標是在加工型別、加工先後順序、批次容量、及時窗限制之下得到最大化機台利用率。三種求解方法分別是: (1) 視時窗為軟式限制的TW-SOFT, (2) 視時窗為硬式限制的TW-HARD, 以及(3) 視時窗為軟式限制，但候選清單建構考量時窗為硬式限制的TW-semiHARD方法。本研究同時設計四種蟻拓演算流程中的啟發項計算式，以引導蟻拓求解。這四種啟發項分別是: (1) MSD， 期許一個加工作業完工之後，其接續加工步驟可立即開始加工；(2) MPD，加工時間相近的加工步驟併成一批可提高機台利用率；(3) MSPD，是MSD和MPD的混合值； 及(4) MSCmax，最小化相同加工型別的機台的最晚結束時間。本研究並研擬多個範例問題進行測試。內容比較五種不同的蟻拓法 (AS；ACS；ASelite；ASrank；及SDAS) 的求解效能同時設立不同求解模式和啟發項的組合。本研究開發一軟體系統實作提出的求解模式和啟發項。數據驗證結果顯示在求解具時窗限制的併批暨排程優化問題時結合TW-semiHARD模式和MSCmax 啟發項可以得到較好的結果。另外，使用ACS、SDAS、 ASelite、及ASrank等在仲裁者行動時針對求解至今最佳解額外添加費洛蒙的蟻拓最佳化演算法，可以得到較好的解 。

The mathematical model of a time window constrained batching and scheduling problem is rigorously defined. This problem is subject to process type constraints between operations and machines, precedence constraints between operations of a job, machine batch capacity limits, and the time window constraints between two successive operations. Three Ant Colony Optimization (ACO) solution construction procedures are developed for finding the maximum machine utilization in the time window constrained batching and scheduling problem. The first is the TW-SOFT computation mode that regards time window constraints as soft constraints. The second is the TW-HARD computation mode that regards time window constraints as hard constraints. The third is the TW-semiHARD computation mode that treats time window constraints as soft constraint, but considers them hard constraints in candidate set construction process. Four heuristic terms are proposed to guide the ACO solution search. Among them, the MSD aims to start an operation right after its predecessor is completed; the MPD aims to fully utilize time capacities of machines; the MSPD is a hybrid of the MSD and MPD; and the MSCmax aims to minimize the maximum completion time of machines. A software prototype system is developed to implement the proposed computation modes and heuristic terms. In the system, five ACO methods are implemented with the proposed ACO technique for the discussed problem. Several numerical tests are conducted to evaluate performances of the five implemented ACO methods, including the AS, ACS, ASelite, ASrank, and SDAS. Combinations of the proposed computation modes and heuristic terms are tested to evaluate their performances. Numerical results show that the TW-semiHARD mode and MSCmax heuristic term outperforms others. In addition, the ACS, SDAS, ASelite, and ASrank are better choices for the problem.

List of Figures iii
List of Tables vi
Glossary And Notations vii
Chapter 1 Introduction 1
1.1 Background And Motivation 1
1.2 Research Objective 2
1.3 Research Procedure 3
1.4 Organization Of This Research 3
Chapter 2 Literature Review 5
2.1 Time Window Constraints 5
2.2 Batching Scheduling Problems 7
2.2.1 Scheduling of batch processor, SBP 7
2.3 Ant Colony Optimization, ACO 11
2.2.1 Solution Construction in the ACO 16
2.2.2 The Algorithmic Flow of Ant Colony Optimization 19
2.2.3 Evolution of Ant Colony Optimization 20
2.2.4 Comparison of ACO Algorithms 30
2.4 Summary Of Literature Reviews 31
Chapter 3 Ant Colony Optimization For Solving Time Window Constrained Batching And Scheduling Problem 33
3.1 Mathematical Model 38
3.1.1 Notations and Parameters 39
3.1.2 Objective Function 48
3.1.3 Constraints 50
3.2 Ant Colony Optimization Method For The Time Constrained Batching And Scheduling Problem 52
3.2.1 Object Link, Pheromone Matrix, Heuristic Term, and Normalized Objective Value Used in Pheromone Update 53
3.2.2 Overview of the Solution Construction Procedure 58
3.2.3 Ant Colony Optimization Process in the TW-SOFT Computation Mode for Time Window Constrained Batching and Scheduling Problems 60
3.3.4 Ant Colony Optimization Process in the TW-HARD Computation Mode for Time Window Constrained Batching and Scheduling Problems 76
3.3.5 Ant Colony Optimization Process in the TW-semiHARD Mode for Solving Time Window Constrained Batching and Scheduling Problem 81
3.3.6 A Candidate Set Update Example for the Proposed Three Modes 84
3.3.7 Summary of this chapter 91
Chapter 4 Applying ACO Techniques To Solve Time Constrained Batching And Scheduling Problem 92
4.1 Description Of The Test Problems 92
4.1.2 Test Problems Whose Optimal Solutions are Unknown 92
4.1.3 Problems with Known Optimal Solutions 94
4.2 Computation Result Of The Testing Problems Without Known Optima 96
4.3 Computation Result Of The Testing Problems With Known Optima 100
4.4 Discussion 102
4.4.1 Comparison on the ACO Methods 103
4.4.2 Comparison of the Solving Combinations 103
4.4.3 Comparison on Different Time Window Constraint Modes 104
4.4.4 Summaries 105
Chapter 5 Conclusion And Suggestions For Future Work 106
5.1 Conclusion 106
5.2 Suggestions For Future Work 107
References 108
APPENDIX A Problem TS34 110
APPENDIX B Problem TSr53 112
APPENDIX C Best Schedules Obtained For The Problems Listed In Table 4-1 And Problem C 115

Bullnheimer, B., R. F. Hartl and C. Strauss (1997). "A new rank based version of theAnt System."
Dorigo, M. and G. Di Caro (1999). "Ant colony optimization: a new meta-heuristic." Proceedings of the 1999 Congress on Evolutionary Computation, 1999. CEC 99..2: 1470-1477
Dorigo, M. and L. M. Gambardella (1997). "Ant colony system: a cooperative learning approach to the traveling salesman problem." IEEE Transactions on Evolutionary Computation, 1(1): 53-66.
Dorigo, M., V. Maniezzo and A. Colorni (1991). "Ant System: An Autocatalytic Optimizing Process." Dipartimento di Elettronica e Informazione, Politecnico di Milano.
Dorigo, M., V. Maniezzo and A. Colorni (1996). "Ant system: optimization by a colony of cooperating agents." IEEE Transactions on Systems, Man and Cybernetics, Part B, 26(1): 29-41.
Gambardella, L. M., E. D. Taillard and M. Dorigo (1999). "Ant colonies for the quadratic assignment problem." Journal of the Operational Research Society 50(2): 167-176.
Lee, C. Y., R. Uzsoy and L. A. Martin-Vega (1992). "Efficient Algorithms for Scheduling Semiconductor Burn-In Operations." Operations Research 40(4): 764-775.
Lee, S., T. Jung and T. Chung (2001). "Improved ant agents system by the dynamic parameter decision." IEEE Transactions on Fuzzy Systems2: 666-669 vol.3.
Lin, D. H. (2004). “Added to the superior segments and subtracted from inferior segments Ant System for Combinatorial Optimization Problems.” Industrial Engineering. Taipei, Taiwan, National Taiwan University. Master.
Mason, S. J., J. W. Fowler and M. Carlyle (2002). "A modified shifting bottleneck heuristic for minimizing total weighted tardness in complex job shops." Journal of Scheduling 5: 247-262.
Mathirajan, M. and A. I. Sivakumar (2006). "A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor." The International Journal of Advanced Manufacturing Technology V29(9): 990-1001.
Ovacik, I. M. and R. Uzsoy (1997). "Decomposition methods for complex factory scheduling problems." Kluwer Academic Publishers.
Scholl, W. and J. Domaschke (2000). "Implementation of modeling and simulation in semiconductor wafer fabrication with time constraints between wet etch and furnace operations." Semiconductor Manufacturing, IEEE Transactions on 13(3): 273-277.
Schoofs, L. and B. Naudts (2000). "Ant colonies are good at solving constraint satisfaction problems."2: 1190-1195 vol.2.
Stuetzle, T. and H. Hoos (1997). "MAX-MIN Ant System and local search for the traveling salesman problem." Indianapolis, IN, USA, IEEE, Piscataway, NJ, USA: 309-314.
Tan, K., Y. Chew and L. Lee (2006). "A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows." Computational Optimization and Applications 34(1): 115-151.
Tu, Y. M. and C. H. Liou (2006). "Capacity determination model with time constraints and batch processing in semiconductor wafer fabrication." Journal of the Chinese Institute of Industrial Engineers 23(3): 192-199.
Wang, C. S. and R. Uzsoy (2002). "A genetic algorithm to minimize maximum lateness on a batch processing machine." Comput. Oper. Res. 29(12): 1621-1640.
Zwaan, S. v. d. and C. Marques (1999). "Ant Colony Optimisation for Job Shop Scheduling " Proceedings of the ''99 Workshop on Genetic Algorithm and Artificial Life.