跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/08/01 13:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳冠廷
研究生(外文):Guan-Ting Chen
論文名稱:具有機台無閒置時間限制之多目標流程型工廠排程
論文名稱(外文):Scheduling a multi-objective flowshop with no-idle time constraint
指導教授:應國卿應國卿引用關係
口試委員:黃乾怡張玉鈍
口試日期:2012-07-16
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:工業工程與管理系碩士班
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:58
中文關鍵詞:流程型工廠無機台閒置時間反覆貪婪演算法
外文關鍵詞:FlowshopNo idle timeIterated Greedy
相關次數:
  • 被引用被引用:2
  • 點閱點閱:152
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
無機台閒置時間的流程型工廠排程問題為具有NP-hard性質的組合最佳化問題,如果以最佳化方法進行求解勢必花費較長的求解時間。因此,近年來傾向於利用啟發式演算法進行求解可兼具求解速度與品質。近年來,許多文獻皆證明反覆貪婪(Iterated Greedy ; IG)演算法對於求解流程型工廠排程問題有著優異的績效。因此,本研究參考Minella等人,提出一個以反覆貪婪演算法為基礎並加入鄰域搜尋及重啟機制的演算法,稱為具重啟機制之反覆貪婪演算法(Restarted Iterated Greedy ; RIG),求解無機台閒置時間之排列式流程型工廠問題並以最大完工時間最小化及總流程時間最小化為目標,利用Taillard測試題庫與Ren等人所提出之混和禁忌搜尋演算法(Hybrid Tabu Search ; HTS)進行比較,經由實驗結果證實,本研究提出之RIG能獲得較佳的求解績效。

The no-idle flowshop problem is combinatorial optimization problem with essentially NP-hard, the optimal methods are not efficient in finding optimal solutions. Recently, there are many scholars develop some meta-heuristics approach to effectively yield a good quality solution. In the literatures, the Iterated Greedy methodology for solving flowshop problem has produced state-of-the-art results.
In this study, we develop revised Iterated Greedy, proposed by Minella to solve the bi-criteria no-idle permutation flowshop problem. The goal is to minimize makespan and minimize total flow time. The results of implementation of our proposed algorithm are compared with Iterated Greedy and Hybrid Tabu Search proposed by Ren, From the experiment results, we show that the solutions obtained by our revised Iterated Greedy better than other two heuristics.


摘 要i
ABSTRACTii
誌 謝iii
目 錄iv
表目錄vi
圖目錄viii
第一章 緒論1
1.1問題背景與動機1
1.2研究目的3
1.3研究範圍與限制3
1.4研究流程4
第二章 文獻探討6
2.1無機台閒置時間限制之排列式流程型工廠排程相關文獻6
2.2多目標流程型工廠排程相關文獻8
2.3多目標最佳化11
2.4 NEH演算法12
2.5反覆貪婪演算法16
2.5.1初始解產生18
2.5.2解構階段18
2.5.3建構階段19
第三章 研究方法20
3.1機台閒置時間探討20
3.2數學符號之定義24
3.3無機台閒置時間流程型工廠問題之數學模式24
3.4 RIG演算法26
3.4.1 RIG演算法之編碼方式29
3.4.2 初始化及選擇運算子29
3.4.3 反覆貪婪31
3.4.4 鄰域搜尋33
3.4.5 重啟機制34
第四章 實驗結果及分析35
4.1實驗設計35
4.2 迭代數分析40
4.3實驗結果及分析45
4.4統計檢定分析47
第五章 結論與建議52
5.1結論52
5.2研究貢獻與建議52
參考文獻54


[1]汪玉柏,運用基因演算法求解流程型工廠之多目標排程,碩士論文,國立台灣科技大學,台北,1999。
[2]許民聖,運用模擬退火法求解流程型工廠之多目標排程,碩士論文,國立台灣科技大學,台北,2000。
[3]王治元,智慧型基因演算法於多目標排程之發展與應用─以PCB鑽孔為例,碩士論文,元智大學,桃園,2004。
[4]J. A. Hoogeveen, "Invited review: multicriteria scheduling," European Journal of Operational Research,Vol. 167, Issue 3, 2005, pp. 592–623.
[5]C. L. Chen, R. L. Bulfin, "Complexity of a single machine multi-criteria scheduling problem," European Journal of Operational Research, Vol. 70, Issue 1, 1993, pp. 115–125.
[6]P. Brucker, "Sceduling algorithms," Springer,Berlin,1998.
[7]T. Loukil, J. Teghem and D. Tuytten, "Solving multi-objective production scheduling problem using metaheuristics." European Journal of Operational Research, Vol. 161, 2005, pp. 42–61.
[8]E. Taillard, "Benchmarks for basic scheduling problems," European Journal of Operational Research, Vol. 64, Issue 2, 1993, pp. 278–285.
[9]W. J. REN, J. H. DUAN, F. R. Zhang, H. Y. Han and M. Zhang, "Hybrid Tabu Search algorithm for bi-criteria No-idle permutation Flow Shop," Control and Decision Conference (CCDC), Chinese, 2011, pp. 1699–1702.
[10]R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, 1979, pp. 287–325.
[11]I. Adiri, D. Pohoryles, "Flowshop no-idle or no-wait scheduling to minimize the sum of completion times," Naval Research Logistics, Vol. 29, Issue 3, 1982, pp. 495–504.
[12]S. M. Johnson,"Optimal two- and three-stage production schedules with setup times included," Naval Research Logistics, Vol. 1, Issue 1, 1954, pp. 61–68.
[13]M. R. Garey, D. S. Johnson and R, Sethi, "The complexity of flowshop and jobshop scheduling," Math Oper Res, 1976, pp. 117–129.
[14]P. Baptiste, and K. H. Lee, "A branch and bound algorithm for the F/no-idle/Cmax," In:Proceedings of the International Conference on Industrial Engineering and Production Management, Lyon, France, 1997, pp. 429–438.
[15]C. R. Woollam, "Flowshop with no-idle machine time allowed," Comput Ind Eng, 1986, pp. 69–76.
[16]M. Nawaz, E. E. E. Jr and I. Ham, "A heuristic algorithm for the m-machine, n-job flow shop sequencing problem," International Journal of Management Science, Vol.11, 1983, pp. 91–95.
[17]N. E. H. Saadani, A. Guinet and M. Moalla, "A travelling salesman approach to solve the F/no-idle/Cmax problem," European Journal of Operational Research, Vol. 1, Issue 1, 2005, pp. 11–20.
[18]N. E. H. Saadani, A. Guinet and M. Moalla, "Three stage no-idle flow-shops," Comput Ind Eng, Vol. 44, Issue 3,2003, pp. 425–434.
[19]J. Kamburowski, "More on three-machine no-idle flow shops," Comput Ind Eng , Vol. 46, Issue 3,2004, pp. 461–466.
[20]P. J. Kalczynski and J. Kamburowski, "A heuristic for minimizing the makespan in no-idle permutation flow shop," Comput Ind Eng, Vol. 49, Issue 1, 2005, pp. 146–154.
[21]P. Baptiste and K. H. Lee, "A branch and bound algorithm for the F/no-idle/Cmax," In:Proceedings of the International Conference on Industrial Engineering and Production Management, Lyon, France, 1997, pp. 429–438.
[22]P. J. Kalczynski and J. Kamburowski, "On no-wait and no-idle flow shops with makespan criterion," European Journal of Operational Research, Vol. 178, Issue 3, 2007, pp. 677–685.
[23]D. Baraz and G. Mosheiov, "A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time," European Journal of Operational Research, 2008 , pp. 810–813.
[24]Q. K. Pan and L. Wang,"No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm," Int J Adv Manuf Tech, Vol. 39, No.7–8, 2008, pp. 796–807.
[25]Q. K. Pan and L. Wang,"A novel differential evolution algorithm for no-idle permutation flow-shop scheduling problems," Eur J Ind Eng , Vol. 2, No.3, 2008, pp. 279–297.
[26]R. Ruiz and T. Stutzle,"A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," Eur J Oper Res, Vol. 177, Issue 3, 2007, pp. 2033–2049.
[27]R. Gangadharan and C. Rajendran,“A simulated annealing heuristic for scheduling in a flowshop with bicriteria,” Computers & Industrial Engineering, Vol. 277, Issue 1¬–4, 1994, pp. 437–476.
[28]F. A. Ogbu and D. K. Smith, "Application of the simulated annealing algorithm to the solution of the n/m/C flowshop problem," Computers & Operations Research, Vol. 17, Issue 3, 1990, pp. 243–253.
[29]M. Hapke, A. Jaszkiewicz and R. Slowinski, "Interactive analysis of multiple-criteria project scheduling problems," European Journal of Operational Research, Vol. 107, Issue 2, 1998, pp. 315–324.
[30]J. C. Ho and Y. L. Chang, "A new heuristic for the n-job, m-machine flow-shop problem," European Journal of Operational Research, Vol. 52, Issue 2, 1991, pp. 194-202.
[31]A. Nagar, J. Haddock and S. S. Heragu, "Multiple and bicriteria scheduling: a literature survey," European Journal of Operational Research, Vol. 81, Issue 1, 1995, pp. 88–104.
[32]A. Nagar, S. S. Heragu and J. Haddock, "A branch and bound approach for a two-machine flowshop scheduling problem," Journal of the Operational Research Society, Vol. 46, No.6, 1995, pp. 721–734.
[33]T. Murata, H. Ishibuchi and H. Tanaka, "Multi-objective genetic algorithm and its applications to flowshop scheduling," International Journal of Computers and Industrial Engineering, Vol. 30, Issue 4, 1996, pp. 957-968.
[34]V. R. Neppali, C. L. Chen and J. N. D. Gupta, "Genetic algorithms for the Two-stage bicriteria flowshop problem," European Journal of Operational Research, Vol. 95, Issue 2, 1996, pp. 356–373.
[35]E. L. Ulungu, J. Teghem, P. H. Fortemps and D. Tuyttens, "MOSA Method: A tool for solving Multi-objective combinatorial optimization problems," Journal of Multi-Criteria Decision Analysis, 1999, 8, pp. 221-236.
[36]T. Loukil, J. Teghem and P. Fortemps, "Solving Multi-objective production scheduling problems with tabu search," Control and Cybernetics, Vol. 46, No.6, 2000, pp.819–828.
[37]S. G. Ponnambalam, H. Jagannathan, M. Kataria and A. Gadicherla, "A TSP-GA Multi-objective algorithm for Flow-shop scheduling," The International Journal of Advanced Manufacturing Technology, Vol. 23, No.11–12, 2004, pp. 909–915.
[38]D. Lei, and Z. Wu, "Crowding-measure-based multiobjective evolutionary algorithm for job shop scheduling," The International Journal of Advanced Manufacturing Technology, Vol. 30, No.1–2, 2005, pp. 112–117
[39]T. Pasupathy, C. Rajendran and R. K. Suresh, "A Multi- objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs, " International Journal of Advanced Manufacturing Technology, Vol. 27, No.7–8, 2006, pp. 804–815.
[40]C. J. Liao, R. H. Huang and S. T. Tseng, "Use of variable range in solving multiple criteria scheduling problem," Computer & Operations Research, Vol.19, 1992, pp. 453–460.
[41]R. Ruiz, E.Vallada and F. M. Carlos,"Scheduling in flowshops with no-idle machines," In: Chakraborty U.K, editor. Computational intelligence in flow shop and job shop scheduling, Berlin: Springer, 2009, pp. 21–51.
[42]K. Deb,"A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation, 2002, pp. 182–197.
[43]G. Minella, R. Ruiz and M. Ciavotta, "Restarted Iterated Pareto Greedy algorithm for multi-objective flowshop scheduling problems," Computers & Operations Research, Vol. 38, Issue 11, 2011, pp.1521–1533.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top