(3.235.245.219) 您好!臺灣時間:2021/05/10 02:02
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林鈺哲
研究生(外文):Yu-Zhe Lin
論文名稱:雙目標機台無閒置流程型工廠排程問題
論文名稱(外文):Bi-criteria No-idle Flowshop Scheduling Problems
指導教授:應國卿應國卿引用關係
指導教授(外文):Kuo-Ching Ying
口試委員:林詩偉黃乾怡
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:工業工程與管理系所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
畢業學年度:104
中文關鍵詞:延伸型反覆貪婪演算法雙目標機台無閒置排程
外文關鍵詞:Extendede Iterated Greedy algorithmBi-criteriaNo-idleScheduling
相關次數:
  • 被引用被引用:0
  • 點閱點閱:107
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
機台無閒置流程型工廠在排程領域中一直是個備受討論的重要話題,機台不可因前後加工工件的替換,而造成閒置。然而,雙目標求解的機台無閒置流程型工廠問題卻鮮少被討論,例如:同時考慮最大完工時間(Makespan)及總流程時間(Total flow time; TFT)。本研究針對此一重要排程問題,提出一個延伸型的反覆貪婪演算法(Extended Iterated Greedy; EIG),即結合修改型的建構機制及鄰域搜尋(Local Search)的擾動機制,與Ren等人所提出之混合禁忌搜尋演算法(Hybrid Tabu Search; HTS)進行比較,另外也提出了三種版本的反覆貪婪(Iterated Greedy; IG)演算法(IG1、IG2、IG3)來求解具機台無閒置之流程型工廠排程問題,其目標函數為最小化加權最大完工時間及總流程時間,其中IG1為沿用原始IG的架構;IG2為加入鄰域搜尋(Local Search)擾動機制;IG3則為加入修改型的建構機制,經由實驗結果證實本研究所提出的EIG演算法之求解品質皆顯著優異於IG1、IG2、IG3及HTS演算法。
The no-idle flowshop scheduling problem (NIFSP) has been sufficiently investigated in the field of scheduling. In a no-idle flowshop, machines cannot be idled after finishing one job and before starting the next one. However, bi-objectives NIFSPs are rarely discussed in the past studies, e.g., the maximum completion time (Makespan) and the total flow time (TFT).In this study, I propose an Extended Iterated Greedy (EIG) algorithm, which integrates a revised construction method, and a local search to solve the bi-criteria NIFSP. The goal is to minimize the total weighted makespan and total flow time. The performance of the proposed EIG algorithm is compared with a hybrid Tabu search (HTS) algorithm proposed by Ren. In addition, I propose three versions of the Iterated Greedy (IG) algorithm, namely IG1, IG2, and IG3, which contain an original architecture from IG, a local search, and a revised construction method, respectively, to solve this problem. The results show that the proposed EIG algorithm is significantly superior to the IG1, IG2, IG3 and HTS algorithms.
摘 要 i
ABSTRACT ii
誌 謝 iv
目 錄 v
表目錄 vii
圖目錄 ix
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與限制 3
1.4 研究流程 4
第二章 文獻探討 6
2.1 排列式流程型工廠排程相關文獻 6
2.1.1 流程型工廠排程問題 6
2.1.2 排列式流程型工廠排程問題 6
2.2 無機台閒置時間限制之排列式流程型工廠排程相關文獻 7
2.3 多目標流程型工廠排程相關文獻 9
2.3.1 多目標最佳化問題 9
2.3.2 多目標流程型工廠排程相關文獻 11
2.4 混合式禁忌搜尋演算法 12
2.5 反覆貪婪演算法 13
2.5.1 NEH演算法步驟 13
2.5.2 IG演算法步驟 17
第三章 研究方法 19
3.1數學符號之定義 19
3.2機台無閒置流程型工廠問題之數學模式 20
3.3延伸型反覆貪婪(Extended-IG;EIG)演算法 21
3.3.1初始排序 23
3.3.2解構與加強型FRB4式建構 23
3.3.3鄰域搜尋(Local Search) 25
3.3.4降溫機制 26
3.3.5機台無閒置計算之探討 27
3.3.6 IG1、IG2、IG3及EIG演算法流程 29
第四章 實驗結果與分析 30
4.1測試題庫說明 30
4.2參數設計 30
4.3 實驗結果與求解績效 34
4.3.1 EIG與HTS演算法檢定結果 34
4.3.2 EIG與IG1、IG2及IG3演算法檢定結果 36
4.3.3 工件角度分析平均RPD 39
4.3.4 機台角度分析平均RPD 43
第五章 結論與未來展望 48
5.1結論 48
5.2研究貢獻 49
5.3未來展望 49
參考文獻 51
[1]Taillard, E, "Benchmarks for basic scheduling problems, "European Journal of Operational Research, vol.64, no.2, 1993, pp. 278-285.
[2]Ren, W.-J., Duan, J.-H., Zhang, F.-r., Han, H.-y., & Zhang, M, "Hybrid Tabu Search Algorithm for bi-criteria No-idle permutation flow shop scheduling problem, "Control and Decision Conference (CCDC), vol.1, no.1, 2011, pp. 1699-1702.
[3]Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R, "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey, "Annals of Discrete Mathematics, vol.5, no.1, 1979, pp. 287-326.
[4]Johnson, S. M, "Optimal two‐and three‐stage production schedules with setup times included, "Naval Research Logistics Quarterly, vol.1, no.1, 1954, pp. 61-68.
[5]Bansal, S, "Minimizing the sum of completion times of n jobs over m machines in a flowshop—a branch and bound approach, "AIIE Transactions, vol.9, no.3, 1977, pp. 306-311.
[6]Campbell, H. G., Dudek, R. A., & Smith, M. L, "A heuristic algorithm for the n job, m machine sequencing problem, "Management Science, vol.16, no.10, 1970, pp. 630-637.
[7]Nawaz, M., Enscore, E. E., & Ham, I, "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, "Omega, vol.11, no.1, 1983, pp. 91-95.
[8]Framinan, J., & Leisten, R, "An efficient constructive heuristic for flowtime minimisation in permutation flow shops, "Omega, vol.31, no.4, 2003, pp.311-317.
[9]Ho, J. C., & Chang, Y.-L, "A new heuristic for the n-job, M-machine flow-shop problem, "European Journal of Operational Research, vol.52, no.2, 1991, pp. 194-202.
[10]Suliman, S, "A two-phase heuristic approach to the permutation flow-shop scheduling problem, "International Journal of production economics, vol.64, no.1, 2000, pp. 43-152.
[11]Osman, I. H., & Potts, C, "Simulated annealing for permutation flow-shop scheduling, "Omega, vol.17, no.6, 1989, pp. 551-557.
[12]Ruiz, R., Maroto, C., & Alcaraz, J, "Two new robust genetic algorithms for the flowshop scheduling problem, "Omega, vol.34, no.5, 2006, pp. 461-476.
[13]Nowicki, E., & Smutnicki, C, "A fast tabu search algorithm for the permutation flow-shop problem, "European Journal of Operational Research, vol.91, no.1, 1996, pp. 160-175.
[14]Grabowski, J., & Wodecki, M, "A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, "Computers & Operations Research, vol.31, no.11, 2004, pp. 1891-1909.
[15]Tasgetiren, M. F., Liang, Y.-C., Sevkli, M., & Gencyilmaz, G, "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, "European Journal of Operational Research, vol.177, no.3, 2007, pp. 1930-1947.
[16]Onwubolu, G., & Davendra, D, "Scheduling flow shops using differential evolution algorithm, "European Journal of Operational Research, vol.171, no.2, 2006, pp. 674-692.
[17]Ruiz, R., & Stützle, T, "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, "European Journal of Operational Research, vol.177, no.3, 2007, pp. 2033-2049.
[18]Adiri, I., & Pohoryles, D, "Flowshop/no‐idle or no‐wait scheduling to minimize the sum of completion times, "Naval Research Logistics Quarterly, vol.29, no.3, 1982, pp. 495-504.
[19]Garey, M. R., Johnson, D. S., & Sethi, R, "The complexity of flowshop and jobshop scheduling, "Mathematics of Operations Research, vol.1, no.2, 1976, pp. 117-129.
[20]Baptiste, P., & Hguny, L, "A branch and bound algorithm for the F/no− idle/Cmax, "Proceedings of The International Conference on Industrial Engineering And Production Management, IEPM, vol.10, no.1, 1997, pp. 429-438.
[21]Woollam, C, "Flowshop with no idle machine time allowed, "Computers & Industrial Engineering, vol.10, no.1, 1986, pp. 69-76.
[22]Saadani, N. E. H., Guinet, A., & Moalla, M, "A travelling salesman approach to solve the F/no-idle/C max problem, "European Journal of Operational Research, vol.161, no.1, 2005, pp. 11-20.
[23]Saadani, N. E. H., Guinet, A., & Moalla, M, "Three stage no-idle flow-shops, "Computers & Industrial Engineering, vol.44, no.3, 2003, pp. 425-434.
[24]Kamburowski, J, "More on three-machine no-idle flow shops, "Computers & Industrial Engineering, vol.46, no.3, 2004, pp. 461-466.
[25]Kalczynski, P. J., & Kamburowski, J, "A heuristic for minimizing the makespan in no-idle permutation flow shops, "Computers & Industrial Engineering, vol.49, no.1, 2005, pp. 146-154.
[26]Kalczynski, P. J., & Kamburowski, J, "On no-wait and no-idle flow shops with makespan criterion, "European Journal of Operational Research, vol.178, no.3, 2007, pp. 677-685.
[27]Baraz, D., & Mosheiov, G, "A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time, "European Journal of Operational Research, vol.184, no.2, 2008, pp. 810-813.
[28]Pan, Q.-K., & Wang, L, "No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm, "The International Journal of Advanced Manufacturing Technology, vol.39, no.7-8, 2008, pp. 796-807.
[29]Pan, Q.-K., & Wang, L, "A novel differential evolution algorithm for no-idle permutation flow-shop scheduling problems, "European Journal of Industrial Engineering, vol.2, no.3, 2008, pp. 279-297.
[30]Loukil, T., Teghem, J., & Tuyttens, D, "Solving multi-objective production scheduling problems using metaheuristics, "European Journal Of Operational Research, vol.161, no.1, 2005, pp. 42-61.
[31]Liao, C.-J., Tseng, C.-T., & Luarn, P, "A discrete version of particle swarm optimization for flowshop scheduling problems, "Computers & Operations Research, vol.34, no.10, 2007, pp. 3099-3111.
[32]Nagar, A., Haddock, J., & Heragu, S, "Multiple and bicriteria scheduling: A literature survey, "European Journal of Operational Research, vol.81, no.1, 1995, pp. 88-104.
[33]Daniels, R. L., & Chambers, R. J, "Multiobjective flow‐shop scheduling, "Naval Research Logistics (NRL), vol.37, no.6, 1990, pp. 981-995.
[34]Murata, T., Ishibuchi, H., & Tanaka, H, "Multi-objective genetic algorithm and its applications to flowshop scheduling, "Computers & Industrial Engineering, vol.30, no.4, 1996, pp. 957-968.
[35]Schaffer, J. D, "Multiple objective optimization with vector evaluated genetic algorithms, "Proceedings of The 1st International Conference on Genetic Algorithms, vol.1, no.1, 1985, pp. 93-100.
[36]Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T, "A fast and elitist multiobjective genetic algorithm: NSGA-II, "Evolutionary Computation, IEEE Transactions on, vol.6, no.2, 2002, pp. 182-197.
[37]Lei, D., & Wu, Z, "Crowding-measure-based multiobjective evolutionary algorithm for job shop scheduling, "The International Journal of Advanced Manufacturing Technology, vol.30, no.1-2, 2006, pp. 112-117.
[38]Chakravarthy, K., & Rajendran, C, "A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization, "Production Planning & Control, vol.10, no.7, 1999, pp. 707-714.
[39]Yagmahan, B., & Yenisey, M. M, "A multi-objective ant colony system algorithm for flow shop scheduling problem, "Expert Systems with Applications, vol.37, no.2, 2010, pp. 1361-1368.
[40]Sha, D., & Lin, H. H, "A particle swarm optimization for multi-objective flowshop scheduling, "The International Journal of Advanced Manufacturing Technology, vol.45, no.7-8, 2009, pp. 749-758.
[41]Glover, F, "Heuristics for integer programming using surrogate constraints, "Decision Sciences, vol.8, no.1, 1977, pp. 156-166.
[42]De Backer, B., & Furnon, V, "Meta-heuristics in constraint programming experiments with tabu search on the vehicle routing problem, "The Second International Conference on Metaheuristics (MIC 97), Sophia Antipolis, France, vol.1, no.1, 1997, pp. 1-14.
[43]Ruiz, R., Vallada, E., & Fernández-Martínez, C, "Scheduling in flowshops with no-idle machines, "Computational Intelligence in Flow Shop and Job Shop Scheduling, vol.1, no.1, 2009, pp. 21-51.
[44]Tasgetiren, M. F., Buyukdagli, O., Pan, Q.-K., & Suganthan, P. N, "A General Variable Neighborhood Search Algorithm for the No-Idle Permutation Flowshop Scheduling Problem Swarm, "Evolutionary, and Memetic Computing, vol.1, no.1, 2013, pp. 24-34.
[45]Pan, Q.-K., & Ruiz, R, "An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem, "Omega, vol.44, no.1, 2014, pp. 41-50.
[46]García-Martínez, C., Rodriguez, F. J., & Lozano, M, "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem, "European Journal of Operational Research, vol.232, no.3, 2014, pp. 454-463.
[47]Rad, S. F., Ruiz, R., & Boroojerdian, N, "New high performing heuristics for minimizing makespan in permutation flowshops, "Omega, vol.37, no.2, 2009, pp. 331-345.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔