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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蕭聖勳
研究生(外文):Sheng-Hsun Hsiao
論文名稱:以導引模擬退火法求解不可延遲流程型生產排程問題之研究
論文名稱(外文):Solving No-wait Flow Shop Scheduling Problems by Guided Simulated Annealing
指導教授:葉瑞徽葉瑞徽引用關係
指導教授(外文):Ruey-Huei Yeh
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:62
中文關鍵詞:不可延遲流程型生產排程最大完工時間模擬退火法導引模擬退火法
外文關鍵詞:No-wait flow shop schedulingMakespanSimulated AnnealingGuided Simulated Annealing
相關次數:
  • 被引用被引用:1
  • 點閱點閱:240
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在排程問題領域當中,面對生產環境限制常會有各種不同的問題產生,而不可延遲的限制便是其中之一,不可延遲意謂著工件一旦開始進入製程加工,從進入機器設備到加工結束,每道製程必須緊密的連接,其中不能有任何的暫停或是中斷;例如,煉鋼廠、化學及半導體製程等。本研究主要考慮三機不可延遲流程型生產排程,研究目的為極小化最大完工時間。本研究使用一個新的最佳化演算法─「導引模擬退火法」,來求解此問題,並與傳統模擬退火法比較求解品質及求解效率。結果發現,利用加入導引函數的功能,在求解極小化最大完工時間不可延遲流程型生產排程之中型與大型排程問題上,無論是在求解品質或求解效率,導引模擬退火法皆優於傳統之模擬退火法,顯示加入導引函數後,確實提升了傳統方法之求解品質與效率。
In the field of scheduling problems, a no-wait restriction may occur in the production environment. A no-wait scheduling problem indicates that an operation once started on a machine cannot be interrupted before its completion. There are no buffers allowed within each operation from job release to completion due to some technological constraints. Some examples with the no-wait restriction are the production lines in steel factories, chemical process, semiconductor fabrication facilities, and so on. This study considers three-machine no-wait flow shop scheduling problems. A new optimization algorithm, the Guided Simulated Annealing (GSA) is adopted to solve this problem such that the makespan is minimized. This scheduling problem is solved by using GSA and Simulated Annealing (SA). In order to compare the performance of GSA and traditional SA, we used solution quality and computation efficiency as the measuring criteria. From the numerical examples, we found that GSA is superior to SA in both solution quality and computation efficiency under mid-size and large-size scheduling problems.
摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章、緒論 1
1.1研究背景與動機 1
1.2 研究目的 2
1.3 研究方法與流程 3
1.4 本章架構 6
第二章、文獻探討 7
2.1 不可延遲流程型生產排程相關文獻 7
2.2 模擬退火法相關文獻 9
2.2.1 模擬退火法組成要素與其特性 10
2.2.2 模擬退火法演算步驟 13
2.3 導引模擬退火法文獻 17
2.3.1 導引模擬退火法特點及其限制 19
2.3.2 導引模擬退火法演算步驟 20
第三章、問題描述與研究方法 22
3.1 問題描述 22
3.1.1 問題假設與限制 24
3.2 模式建構 24
3.2.1 舉例驗證 26
3.3 研究方法 28
3.3.1 演算相關參數之設定 29
3.3.2 導引函數取得方式 30
3.3.3 導引函數加權方式 33
3.3.4 導引函數探討 35
3.4 比較法則 37
3.4.1 固定演算次數而比較求解品質 37
3.4.2 固定解之值而比較求解效率 39
第四章、實驗結果與分析 41
4.1 小型排程問題 41
4.1.1 固定演算次數而比較求解品質 42
4.1.2 固定解之值而比較求解效率 44
4.2 中型排程問題 44
4.2.1 固定演算次數而比較求解品質 45
4.2.2 固定解之值而比較求解效率 48
4.3 大型排程問題 50
4.3.1 固定演算次數而比較求解品質 51
4.3.2 固定解之值而比較求解效率 54
4.4 比較與分析 55
4.4.1 平均求解品質 56
4.4.2 平均求解時間 57
第五章、結論與建議 58
5.1 結論 58
5.2 建議 58
參考文獻 60
中文部分
[1] 李世炳、鄒忠毅(2002),「簡介導引模擬退火法及其應用」,中央研究院物理雙月刊,廿四卷二期,頁307-319。
[2] 李宛柔(2007),「以基因演算法求解不可延遲批次排程問題之研究」,台灣科技大學工業管理系碩士論文。
[3] 林政德(2005),「三階段流程工廠在無閒置時間下之排程問題」,中原大學工業工程學系碩士論文。
[4] 張嘉君(2003),「應用模擬退火法求解營建工程專案多重資源排程最佳化之研究」,朝陽科技大學營建工程系碩士論文。
[5] 楊盛發(2006),「雙機連續性流程工廠總延遲時間最小化之排程問題研究」,朝陽科技大學工業工程與管理系碩士論文。
[6] 盧研伯(2003),「混合式模擬退火法應用於具迴流特性流程工廠之研究」,台灣科技大學工業管理系碩士論文。
英文部分
[7] Aldowaisan, T. (2001), “A new heuristic and dominance relations for no-wait flowshops with setups,” Computers and Operations Research, 28 (6), pp. 563-584.
[8] Aldowaisan, T. and A. Allahverdi (2003), “New heuristics for no-wait flowshops to minimize makespan,” Computers & Operations Research, 30 (8), pp. 1219-1231.
[9] Bertolissi, E. (2000), “Heuristic algorithm for scheduling in the no-wait flow-shop,” Journal of Materials Processing Technology, 107 (1-3), pp. 459-465.
[10] Cerny, V. (1985), “Thermo dynamical approach to the traveing salesman problem: An efficient simulated algorithm,” Journal of Optimization Theory and Applications, 45 (1), pp. 41-51.
[11] Gangadharan, R. and C. Rajendran (1993), “Heuristic algorithms for scheduling in the no-wait flowshop,” International Journal of Production Economics, 32 (3), pp. 285-290.
[12] Garey, M.R., D.S. Johnson, and R. Sethi (1976), “Complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research, 1 (2), pp. 117-129.
[13] Gilmore, P.C. and R.E. Gomory (1964), “Sequencing a one state-variable machine: A solvable case of the traveling salesman problem,” Operations Research, 12, pp. 655–679.
[14] Hall, H.G. and C. Sriskandarajah (1996), “A survey of machine scheduling problems with blocking and no-wait in process,” Operations Research, 44 (3), pp. 510-525.
[15] Johnson, S.M. (1954), “Optimal two- and three-stage production schedules with setup times included,” Naval Research Logistics Quarterly, 1 (1), pp. 61-68.
[16] Kirkpatrick, S., C.D. Gelatt Jr., and M.P. Vecchi (1983), “Optimization by simulated annealing,” Science, 220 (4598), pp. 671-680.
[17] Metropolis, N., A.W. Rosenblush, M.N. Rosenblush, A.H. Teller, and E. Teller (1953), “Equation of state calculations by fast computing machines,” The Journal of Chemical Physics, 21 (6), pp. 1087-1092.
[18] Ogbu, F.A. and D.K. Smith (1990). “The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem,” Computers & Operations Research, 17 (3), pp. 243-253.
[19] Osman, I.H. and C.N. Potts (1989). “Simulated annealing for permutation flow-shop scheduling,” Omega, 17 (6), pp. 551-557.
[20] Piehler, J. (1960), “Ein Beitrag zum Reinhenfolge Problem,” Unternehmensforschung Operations Research, 4 (3), pp. 138-142.
[21] Raaymakers, W.H.M. and J.A. Hoogeveen (2000), “Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing,” European Journal of Operational Research, 126 (1), pp. 131-151.
[22] Rajendran, C. (1994), “No-wait flowshop scheduling heuristic to minimize makespan,” Journal of the Operational Research Society, 45 (4), pp. 472–478.
[23] Reddi, S.S. and C.V. Ramamoorthy (1972). “On the flow-shop sequencing problems with no wait in process,” Operational Research Quarterly, 23 (3), pp. 323–331.
[24] Rock, H. and G. Schmidt (1983), “Machine aggregation heuristics in shop-scheduling,” Methods of Operations Research, 45, pp. 303–314.
[25] Rock, H. (1984) “Some new results in flow shop scheduling,” Zeitschrift für Operations Research, 28 (1), pp. 1-16.
[26] Rock, H. (1984), “The three-machine no-wait flow shop is NP-Complete,” Journal of the ACM, 33, pp. 336-345.
[27] Wang, T.-Y., Y.-H. Yang, and H.-J. Lin (2006), “Comparison of scheduling efficiency in two/three-machine no-wait flow shop problem using simulated annealing and genetic algorithm,” Asia-Pacific Journal of Operational Research, 23 (1), pp. 41-59.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔