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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:吳思農
研究生(外文):Si-Nong Wu
論文名稱:模擬退火法於有限資源下不相關平行機台排程問題
論文名稱(外文):A Simulated Annealing Algorithm for Unrelated Parallel-Machine Scheduling Problem with Constrained resources
指導教授:蔡啟揚
指導教授(外文):Chi-yang Tsai
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:67
中文關鍵詞:模擬退火法不相關平行機台總時程最小化
外文關鍵詞:Simulation annealingUnrelated parallel-machinesMinimum makespan
相關次數:
  • 被引用被引用:9
  • 點閱點閱:180
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
以往有關不相關平行機台的問題還是都著眼於資源是無限的情況下,但實業界的情況中各機台可使用的資源是有限的,這類問題在學術上是熟知困難度極高的組合最佳化問題,除了少數特例外,此類問題皆屬於NP-hard問題,因此本研究期望能夠在有限的資源與考量機台的整備時間限制下,建構一個在有限資源下的不相關平行機台排程之模式,績效衡量指標為總時程時間最小化,本研究嘗試使用模擬退火法能夠跳脫局部最佳解的機制,進而搜尋到全域最佳解的優點,來求解不相關平行機台之排程問題。
本研究探討模擬退火法的最佳參數組合,以小型、中型和大型測試例題,並結合實業界的實例驗證,於求解時間與求解品質上做一分析,並在資源有無的鬆緊度上做一探討,結果顯示無限的擴充資源,只會造成多餘的浪費,最後結果也顯示本研究所建構的排程指派演算法確實能對傳統的簡易派工法則上有一定的改善績效,且能有效的降低總時程時間,並對於有限資源下的不相關平行機台的排程問題建立一個排程指派演算法,結果也顯示此排程指派演算法在求解總時程時間上有良好的績效。
The study on unrelated parallel-machine scheduling problems has been assuming unconstrained resources. However, the resources in scheduling problems are usually limited in practice. It is well known that most of the unrelated parallel-machine scheduling problems alone are NP-hard. Therefore, utilizing its ability to escape local optimal points, the study applies simulated annealing method and attempts to develop an algorithm for unrelated parallel-machine scheduling problems. The objective considered in this study is to minimize the machines completing time.
In order to evaluate the performance of the proposed algorithm, numerical experiments are conducted and the algorithm is tested on three numerical examples of different sizes, as well as, practical cases. The results show that it performs well compared to simple dispatching rules.
摘要 i
Abstract ii
誌 謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 2
1.2 研究目的 3
1.3 研究問題描述 4
1.4 研究步驟與架構 4
第二章 文獻探討 7
2.1 排程問題之概述 7
2.1.1 排程之技術 7
2.2 平行機台排程問題之探討 9
2.2.1 平行機台的類型 9
2.2.2 不相關平行機台之相關文獻整理 10
2.3 模擬退火法 12
2.3.1 模擬退火法起源與原理 12
2.3.2 模擬退火法的應用與演算流程 14
2.4 本章總結 16
第三章 研究方法 17
3.1 不相關平行機台排程模式 17
3.1.1 問題定義 17
3.1.2 限制與假設條件 18
3.1.3 相關變數說明 19
3.1.4 不相關平行機台排程模式建立 20
3.2 不相關平行機台排程模式 21
3.3 模擬退火法之內容 24
3.3.1 參數設定 24
3.3.2 移步結構 25
3.3.3 起始群體的產生 25
3.3.4 指派法則之設計 26
3.3.5 終止條件 28
3.4 本章總結 28
第四章 測試例題與參數設定 29
4.1 測試例題說明 29
4.2 最佳化參數設計方法 31
4.2.1 田口實驗設計 31
4.2.2 特性要因分析 31
4.2.2.1 特性確認 31
4.2.2.2 控制因子與水準設定 31
4.2.3 模擬退火法參數分析 32
4.3 實驗設計與分析 33
4.3.1 例題一 33
4.3.2 例題二之排程模式參數設計 35
4.3.3 例題三之排程模式參數設計 40
4.4 參數分析結語 46
第五章 例題結果與分析 47
5.1 排程指派模式指派結果 47
5.2 不同簡易派工法則下對於排程指派模式之績效評估 49
5.2.1 例題二 49
5.2.2 例題三 52
5.3 不同機台數與工件數之績效評估 53
5.4 功能卡的資源鬆緊度之績效評估 55
5.5 實例驗證與分析 56
5.5.1 實例驗證一 56
5.5.2 實例驗證二 60
第六章 結論與未來研究建議 63
6.1 研究結論 63
6.2 未來研究建議 64
參考文獻 66
1. Adenso-Diaz, B., “An SA/TS mixture algorithm for the scheduling tardiness Problem, “European journal of operational research, 88, 516-524, (1996).
2. Anagnostopoulos and Rabadi, G.., “A simulated annealing algorithm for the unrelated parallel machine scheduling problem”, Proceeding of the world automation congress, Orlando, Florida, June 9-13, (2002).
3. Baker, K. R., Introduction to Sequencing and Scheduling (John Wiley &Sons, New York, NY, (1974).
4. Bank, F., “Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties”, Mathematical and computer modeling 33, 363-383., (2001).
5. Ben-Daya, M. and Al-Fawzan, M., “ A simulated annealing approach for the one-machine mean tardiness scheduling problem, “ European Journal of operational Research 93, 61-67, (1996).
6. Ghedjati, F., “Genetic algorithms for the job-shop scheduling problem with parallel constraints: heuristic mixing method machines and precedence”, Computer & industrial engineering 37, 39-42, (1999).
7. Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G., “Optimization and approximation in deterministic sequence and scheduling theory: a survey”, Annals of discrete mathematics, 5, 287-326., (1979).
8. Hisao, I., Shinta, M., and Hideo T., “Modefied simulated annealing algorithm for the flow shop sequencing problem”, European journal of operational research, 81, 388-398. , (1995).
9. Kim, D., Na, D., and Chen, F., “Unrelated parallel machines scheduling with setup times and a total weighted tardiness Objective”, Robotics and computer integrated manufacturing 19, 173-181, (2003).
10. Kim, D., Kim, K., Jang, W., and Chen, F., “Unrelated parallel machine scheduling with setup times using simulated annealing”, Robotics and computer integrated manufacturing 18, 223-231, (2002).
11. Kirkpatric, S., Gelatt, Jr., and Cd,V., “Optimization by simulated annealing”, Science; 107:354-70., (1983).
12. Lee, Y. and Pinedo, M., “Scheduling jobs on parallel machines with sequence-dependent setup times”, European journal of operational research 100, 464-474., (1997).
13. Liaw, C., Lin, Y., Cheng, C., and Minchin C., ”Scheduling unrelated parallel machines to minimize total weighted tardiness”, Computer & operations research 30, 1777-1789, (2003).
14. Lee, H. and Guignard, M., “A hybrid bounding procedure for the workload allocation problem on parallel unrelated machines with setups”, Journal of the operational research society, 47, 1247-1261., (1996).
15. Martello, S., Soumis, F., and Toth, P., “Exact and approximation algorithms for makespan minimization on unrelated parallel machines”, Discrete applied mathematics 75, 169-188., (1997).
16. Piersma, N. and Dijk, W.,”A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search”, Mathematical and computer modeling, Vol. 24, 11-19, (1996).
17. Rabadi, G.., Anagnostopoulos, G., and Mollaghasemi, M., “A new heuristic for the just-in-time single machine scheduling problem with setups: a comparison with a simulated annealing approach”, A chapter in an edited book published by springer verlag through their lecture notes in computer science (LNCS), (2001).
18. Srivastava, B., “An effective heuristic for minimizing makespan on unrelated parallel machines”, The journal of the operational research society, Vol. 49, 886-894, (1998).
19. Schutten, J. M. J. and Leussink, R. A. M., “Parallel machines scheduling with release dates, due dates and family setup times”, International journal of Production economics 49-47, 119-125. , (1996).
20. Stevenson, “Operations management”, seventh edition., (2002).
21. X.Weng, M., Lu, J., and Ren, H., “Unrelated parallel machines scheduling with setup consideration and a total weighted completion time objective”, International journal of Production economics 70, 215-226., (2001).
22. 林長春,「處理單元形成中例外元素問題之最佳化──以模擬退火法求解」,國立成功大學,工業管理研究所碩士論文,(1998)。
23. 林淳菁,「應用遺傳基因演算法求解不相關平行機台之排程問題」,朝陽科技大學,碩士論文,(2001)。
24. 林暘桂,「不相關平行機總加權延遲最小化之排程問題」,朝陽科技大學,碩士論文,(2000)。
25. 游擱鴻, 「以啟發式方法求解不相關平行機台排程問題」,朝陽科技大學,碩士論文,(1997)。
26. 柯惠雯,「結合模擬退火法與禁忌搜尋法解決流程式排程問題」,大葉大學,碩士論文,(2000)。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔