# 臺灣博碩士論文加值系統

(44.220.247.152) 您好！臺灣時間：2024/09/10 22:27

:::

### 詳目顯示

:

• 被引用:0
• 點閱:190
• 評分:
• 下載:0
• 書目收藏:0
 本研究針對具時窗限制的併批暨排程優化問題提出三種蟻拓演算求解方法，並詳細定義此種問題的數學模式。求解目標是在加工型別、加工先後順序、批次容量、及時窗限制之下得到最大化機台利用率。三種求解方法分別是: (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 iiiList of Tables viGlossary And Notations viiChapter 1 Introduction 11.1 Background And Motivation 11.2 Research Objective 21.3 Research Procedure 31.4 Organization Of This Research 3Chapter 2 Literature Review 52.1 Time Window Constraints 52.2 Batching Scheduling Problems 72.2.1 Scheduling of batch processor, SBP 72.3 Ant Colony Optimization, ACO 112.2.1 Solution Construction in the ACO 162.2.2 The Algorithmic Flow of Ant Colony Optimization 192.2.3 Evolution of Ant Colony Optimization 202.2.4 Comparison of ACO Algorithms 302.4 Summary Of Literature Reviews 31Chapter 3 Ant Colony Optimization For Solving Time Window Constrained Batching And Scheduling Problem 333.1 Mathematical Model 383.1.1 Notations and Parameters 393.1.2 Objective Function 483.1.3 Constraints 503.2 Ant Colony Optimization Method For The Time Constrained Batching And Scheduling Problem 523.2.1 Object Link, Pheromone Matrix, Heuristic Term, and Normalized Objective Value Used in Pheromone Update 533.2.2 Overview of the Solution Construction Procedure 583.2.3 Ant Colony Optimization Process in the TW-SOFT Computation Mode for Time Window Constrained Batching and Scheduling Problems 603.3.4 Ant Colony Optimization Process in the TW-HARD Computation Mode for Time Window Constrained Batching and Scheduling Problems 763.3.5 Ant Colony Optimization Process in the TW-semiHARD Mode for Solving Time Window Constrained Batching and Scheduling Problem 813.3.6 A Candidate Set Update Example for the Proposed Three Modes 843.3.7 Summary of this chapter 91Chapter 4 Applying ACO Techniques To Solve Time Constrained Batching And Scheduling Problem 924.1 Description Of The Test Problems 924.1.2 Test Problems Whose Optimal Solutions are Unknown 924.1.3 Problems with Known Optimal Solutions 944.2 Computation Result Of The Testing Problems Without Known Optima 964.3 Computation Result Of The Testing Problems With Known Optima 1004.4 Discussion 1024.4.1 Comparison on the ACO Methods 1034.4.2 Comparison of the Solving Combinations 1034.4.3 Comparison on Different Time Window Constraint Modes 1044.4.4 Summaries 105Chapter 5 Conclusion And Suggestions For Future Work 1065.1 Conclusion 1065.2 Suggestions For Future Work 107References 108APPENDIX A Problem TS34 110APPENDIX B Problem TSr53 112APPENDIX 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-1477Dorigo, 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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 具時窗限制的併批暨排程優化問題及其遺傳演算法

 1 張伯宇（2000）汐止的地形、地質與水土災害，北縣文化，67: 4-13。 2 洪幸妙、張金鶚（1993）住宅管理維護對住宅品質之影響研究，都市與計劃，20(1): 1-22。 3 侯錦雄、宋念謙（1998）台中市黎明住宅社區居民社區意識之研究，建築學報，24: 51-65。 4 林瑞穗（1985）蛻變中的都市的都市社區與鄰里生活，思與言，23(3): 73-80。 5 林瑞欽（1994）社區意識的概念、測量與提振策略，社會發展研究學刊，1: 1-21。 6 陳覺惠（2000）台灣地區集合住宅形態發展趨勢與當前社區經營管理議題，東海學報，41: 97-113。 7 蔡祈賢（1995）社區意識與社區發展，社會福利，124: 21-26。

 1 具時窗限制的併批暨排程優化問題及其遺傳演算法 2 利用光柵結構以增強拉曼散射之研究 3 大腸桿菌中Grx4蛋白質之研究 4 適用於點對點隨按即說服務之網路位址轉換器穿越機制 5 利用雙光子螢光及二倍頻顯微術觀察綠膿桿菌對角膜的感染作用 6 單層奈米碳管電子結構之理論探討 7 聚乙二醇接枝聚乙烯亞胺修飾聚電解質多層膜對纖維母細胞貼附研究 8 中風出院病人後續醫療照護之研究 9 仿生撲翼之二維流場與受力量測 10 倒單擺系統模型之建立與控制 11 毫米波多層基板合成波導帶通濾波器之研製 12 造林獎勵與碳吸存補貼對台灣造林與社會福利的影響 13 堆肥製作過程二氧化碳及甲烷排放量測 14 臺灣心導管企業建構全球化策略之研究 15 應用層級式預測方法於季節性資料分析之研究─以家電製造商之出貨量為例

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室