跳到主要內容

臺灣博碩士論文加值系統

(44.192.15.251) 您好!臺灣時間:2024/03/05 01:16
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張瑞炎
研究生(外文):Jui Yen Chang
論文名稱:解開放式工廠排程問題之兩層式基因區域搜尋法
指導教授:曾怜玉曾怜玉引用關係
指導教授(外文):Lin Yu Tseng
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:50
中文關鍵詞:開放式工廠排程問題基因演算法區域搜尋法兩層式基因區域搜尋法
外文關鍵詞:Open Shop Scheduling ProblemGenetic AlgorithmLocal SearchTwo Layered Genetic Local Search Algorithm
相關次數:
  • 被引用被引用:2
  • 點閱點閱:458
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
開放式工廠排程問題(open shop scheduling problem)為作業研究中典型的組合最佳化問題,此問題是NP-hard,本研究將在排程作業不可中斷(non-preemptive)的情況下,求總時程(makespan)最小化的解。
本研究整合基因演算法(Genetic Algorithms, GA)與區域搜尋法(Local Search)為基因區域搜尋法(Genetic Local Search Algorithm),並導入兩層式基因區域搜尋法(Two Layered Genetic Local Search Algorithm),先作全域性的搜尋,再作區域性搜尋,來解開放式工廠排程問題,並以Taillard與Brucker共一百一十二題的標準實例為本研究的測試標準,透過實驗証明兩層式基因區域搜尋法在解決開放式工廠排程問題上有很顯著的成效,以Taillard的標準實例而言,除了有一題解到目前已知最好的解之外,其餘全都達到目標最佳解,在Brucker的標準實例中,平均求解品質也不錯,其中更有一題突破上限值(Upper Bound),亦即比目前最好的解還好。
關鍵字:開放式工廠排程問題,基因演算法,區域搜尋法,兩層式基因區域搜尋法。
The open shop scheduling problem is an NP-hard combinational problem and has long attracted much attention. In this thesis, we propose a two layered genetic local search algorithm for this problem. The first layer acts as the global search and the second layer acts as the local search. We also study the neighborhood structure of a solution and design two kinds of effective local search methods. Combining the genetic algorithm with these local search methods results in our genetic local search algorithm. We test our method on Taillard’s instances and Brucker’s instances. On Taillard’s instances, our method had found the optimal solutions for all instances except one of them. And for this exception, the solution found by our method is the same as the best solution found thus far. On Brucker’s instances, the quality of solutions found is also good and our method had improved the upper bound of one instance.
Key words: Open Shop Scheduling Problem; Genetic Algorithm; Local Search; Two Layered Genetic Local Search Algorithm
中文摘要 iii
Abstract iv
目 錄 v
圖表目錄 vii
第一章 諸論 1
1.1研究背景與動機 1
1.1.1單程工件處理的排程問題 2
1.1.2多程工件處理的排程問題 2
1.1.3排程問題評估準則 3
1.1.4排程問題的解決方法 4
1.2研究目的 5
1.3研究步驟 5
1.4研究範圍與限制 6
1.4.1問題定義 6
1.4.2分離圖模型的數學表示法 6
1.5論文架構 7
第二章 文獻探討 8
2.1開放式工廠問題 8
2.2基因演算法 10
第三章 研究方法 13
3.1問題表示法 13
3.2基因演算法之基本元件 16
3.2.1基因編碼 16
3.2.2評估函數 19
3.2.3繁殖交配機制 20
3.2.4突變機制 24
3.2.5選擇機制 25
3.3區域搜尋法模型 26
3.3.1鄰域結構 26
3.3.1.1關鍵路徑結構 26
3.3.1.2平行部份排程結構 35
3.3.2區域搜尋演算法 36
3.3.2.1以關鍵路徑為基底之區域搜尋演算法 36
3.3.2.2以部份排程為基底之區域搜尋法 37
3.4兩層式基因區域搜尋法模型 38
3.4.1兩層式基因區域搜尋法的概念 38
3.4.2兩層式基因區域搜尋演算法 40
第四章 實例驗證 42
第五章 結論與未來研究方向 48
參考文獻 49
[1] J. O. Achugbue, and F. Y. Chin, “Scheduling The Open Shop To Minimize Mean Flow Time,” SIAM J. COMPUT. , Vol. 11, pp. 709-720 , 1982.
[2] T. Brasel, T. Tautenhahn, and F. Werner, “Constructive Heuristic Algorithms For The Open Shop Problem,” Computing, Vol. 51 pp. 95-110, 1993.
[3] P. Brucker, J. Hurink, B. Jurisch, B. wostmann, “A branch-and-bound algorithm for the open-shop problem,” Discrete Applied Mathematics, Vol. 76, pp. 43-49, 1997.
[4] F. Della Croce, R. Taidei, G. Volta, “A genetic algorithm for the job-shop problem,” Computers and Operations research, Vol. 22, pp. 14-24, 1995.
[5] U. Dorndorf, E. Pesch, and T. Phan Huy,” Solving the open shop scheduling problem,” Journal of Scheduling, Vol. 4, pp. 157-174, 2001.
[6] J. O. Du, Y-T Leung, “Minimizing Mean Flow Time In Two-Machine Open Shops And Flow Shops,” Journal Of Algorithms, Vol. 14, pp. 24-44, 1993.
[7] E. Falkenauer, S. Bouffouix, “A genetic algorithm for job-shop,” in Proc. IEEE International Conference on Robotics and Automation, 1991.
[8] T. Gonzalez, S. Sahni, “Open Shop Scheduling To Minimize Finish Time,” JACM , Vol. 23, No. 4, pp. 665-679, 1976.
[9] B. Giffler, G. L. Thompson,”Algorithm for Solving Production Scheduling Problems, “Operation Research, Vol. 8, pp. 487-503, 1960.
[10] D.E. Goldberg, Genetic Algorithm in Search, Optimization and Machine Learning, Addison-Wesley (1988).
[11] C. Gueret, and C. Prins, “Classical and New Heuristics For The Open-Shop Problem: A Computational Evaluation,” European Journal of Operational Research, Vol. 107, pp.306-314, 1998.
[12] F. Hoffmeister, T. Beack, “Genetic algorithms and evolution strategies: similarities and differences”, Tech. Report no. SYS-1/92, University of Dortmund, 1992.
[13] J. H. Holland. Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
[14] J. H. Holland, and Mitchell, S. Forrest, “The royal road for genetic algorithms: Fitness landscapes and GA performance,” in Proc. First European Conference on Artificial Life, 1991.
[15] E. L. Lawler, L. K. Lenstra, and A.H.G. Rinnooy Kan, ”Minimizing Maximum Lateness In A Two-Machine Open Shop,” Mathematics Of Operations Research, Vol. 6, No 1, pp. 153-158, 1981.
[16] C.F. Liaw, “A hybrid genetic algorithm for the open shop scheduling problem,” European Journal of Operational Research, Vol. 124, No. 1, pp.28-42, 2000.
[17] C.-F Liaw, “A Tabu Search Algorithm For The Open Shop Scheduling Problem,” European Journal Of Operational Research, Vol. 26, No. 2, pp. 109-126, 1999.
[18] C.-F Liaw, “An Iterative Improvement Approach For The Non-preemptive Open Shop Scheduling Problem,” European Journal Of Operational Research, Vol. 111, No. 3, pp. 509-517, 1998.
[19] C.Y. Liu, “A Branch And Bound Algorithm For The Preemptive Open Shop Scheduling Problem,” Journal Of The Chinese Institute Of Industrial Engineers, Vol. 12, No. 1, pp. 25-31, 1995.
[20] D.G. Mayer, J.A. Belward, H. Widell, K. Burrage, Survival of the fittest─genetic algorithms versus evolution strategies in the optimization of systems models, Elsevier Science Ltd (1998).
[21] E. Nowicki, C. Smutnicki, “A fast taboo search algorithm for the job shop problem,” Management Science, Vol. 42, No. 6, pp. 797-813, 1996.
[22] C. Prins, “Competitive genetic algorithms for the open shop scheduling problem,” Mathematical Methods of Operations Research, Vol. 52, No. 3, pp. 389—411, 2000.
[23] I. Rechenberg, Evolutionsstrategie ''94, Frommann-Holzboog Verlag, Stuttgart, 1994.
[24] C.R. Reeves, “A genetic algorithm for flowshop sequencing, computers and Operations Research”, Vol. 22, No. 1, pp. 5-13, 1995.
[25] B. Roy, B. Sussmann, “Les problems d’ordonnancement avec contraintes disjonctives,” SEMA, Note D.S. No. 9, 1964
[26] E. Taillard, ”Benchmarks for basic scheduling problems,” European Journal of Operational Research, Vol. 64, pp. 278-285, 1993.
[27] E. Taillard, “Parallel taboo search techniques for the job shop scheduling problem,” ORSA Journal on Computing, Vol. 6, No. 2, pp. 108-25, 1994.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top