動態平行機雙準則排程啟發式演算法之研究｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	石育榤 Yu-Jie Shi
論文名稱：	動態平行機雙準則排程啟發式演算法之研究 Heuristics for solving dynamic parallel machine bicriteria scheduling problems
指導教授：	邱煥能 Huen-Neng Chin
口試委員:	藍筱蘋 Xiao-Pin Lan 鐘崑仁 kun-Jen Chung
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業管理系 Department of Industrial Management
論文出版年：	2005
畢業學年度：	93
語文別：	中文
論文頁數：	90
中文關鍵詞：	基因演算法、排程、雙準則、動態、平行機、啟發式演算法
外文關鍵詞：	scheduling, parallel, bicriteria, dynamic, genetic algorithms, heuristic
相關次數：	點閱：278 下載：19
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本研究主要探討雙準則動態平行機排程問題，研究中所設定的兩個衡量準則為工作完成時間與到期日之絕對差和以及總流程時間。針對此問題，本研究利用變動加權的概念，發展一個啟發式演算法來求取近似有效邊界，以提供決策者選擇最適的排程。在本研究啟發式演算法中，根據遞迴概念，提出一個動態指標來決定工作的加工順序以及各工作在加工前所需之閒置時間。由於目前雙準則動態平行機排程研究尚未提出求取有效邊界的方法，因此，本研究發展一個基因演算法，並利用它與所提的啟發式演算法作求解績效之比較。
本研究設計兩個實驗，實驗Ⅰ的主要目的為決定最適基因參數組合，實驗結果顯示，當最大執行世代數為200、交配率為0.8以及突變率為0.5時，本研究基因演算法可獲得最好的求解績效。實驗Ⅱ則利用三種評估指標，比較所提出的啟發式演算法與基因演算法之求解績效，結果顯示啟發式演算法能在很短的求解時間內求得與基因演算法非常相近的近似有效邊界，亦即啟發式演算法所需之求解時間僅為基因演算法的0.625%，而平均偏離百分比只有1.6%。最後，本研究將所提的兩個演算法應用至國內某知名電子被動元件製造廠之熱處理作業，並與該廠現行的先進先出法則比較，結果驗證本研究所提方法之優越性及實務適用性。

目    錄

摘要…………………………………………………………………………..	Ⅰ
誌謝…………………………………………………………………………..	Ⅱ
目錄…………………………………………………………………………..	Ⅲ
圖目錄……………………………………………………………………….	Ⅴ
表目錄……………………………………………………………………….	Ⅶ

第一章 緒論………………………………………………………………….	1
1.1 研究背景與目的…………………………………………………….	1
1.2 研究方法與架構…………………………………………………….	3
1.3 相關文獻探討……………………………………………………….	4
1.4 研究範圍與限制…………………………………………….. 	13

第二章 本研究啟發式解法之發展………………………………………	15
2.1符號定義……………………………………………….	         15
2.2問題描述………………………………………	                  17
2.3本研究啟發式演算法之求解原理及步驟……………………….	20
2.4求解範例………………………………………	                  26

第三章 本研究基因演算法之發展………………………………………	32
3.1本研究基因演算法求解程序……………………………..      	32
3.1.1產生起始可行解階段……………………………………..   	32
3.1.2改善階段………………………….	                           35
3.1.3求取最終解階段……………………………………..      	38
3.2 求解範例………………………………………………………	         39

第四章實驗設計與本研究啟發式演算法績效評估	                  48
4.1實驗設計與測試問題之產生………………………….       	48
4.2本研究基因演算法最適參數組合之決定…………………….	         56
4.3本研究啟發式演算法與基因演算法之比較…………………….        58

第五章 應用個案研究與分析………………………….	         64
5.1個案公司簡介	                                              64
5.2個案公司平行機製程說明與資料收集	                            64
5.3個案公司現行平行機製程排程概況	                            66
5.4本研究啟發式演算法與基因演算法之應用	                   66
5.5應用結果分析與建議	                                     67

第六章結論與未來研究方向	                                     69
6.1 結論與建議	                                              69
6.2 未來研究方向	                                              71

參考文獻	                                                       72
附錄一   本研究啟發式演算法程式碼	                            76
附錄二   本研究基因演算法程式碼	                            81
附錄三   本研究實驗相關數據                              	85
附錄四   個案公司相關數據	                                     88
作者簡介	                                                       90

                                

參考文獻

1. 黃瑞文撰，邱煥能指導，「混合二階流程型工廠單階平行機動態排程之研究」，國立台灣科技大學工業管理研究所碩士論文，民國92年。

2. 廖慶榮撰，「多準則之生產排程研究」，行政院國家科學委員會專題研究計畫成果報告，國立台灣科技大學，民國80年。

3. Azizoglu, M., Kondakci, S. and Koksalan, M., “Single machine scheduling with maximum earliness and number tardy,” Computers & Industrial Engineering, Vol. 45, No. 2, 2003, pp. 257-268.

4. Baker, K. R., Introduction to Sequencing and Scheduling, New York: Wiley, 1974.

5. Baker, K. R. and Scudder, G. D., “Sequencing with earliness and tardiness penalties: A review,” Operations Research, Vol. 38, No. 1, 1990, pp. 22-36.

6. Campbell, H. G., Dudek, R. A. and Smith, M., “A heuristic algorithm for the n job m machine sequencing problem,” Management Science, Vol. 16, No. 10, 1970, pp. 630-637.

7. Cochran, J. K., Horng, S. M. and Fowler, J. W., “A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines,” Computers & Operations Research, Vol. 30, No. 7, 2003, pp. 1087-1102.

8. Dewan, P. and Joshi, S., “Dynamic single-machine scheduling under distributed decision-making,” International Journal of Production Research, Vol. 38, No. 16, 2000, pp. 3759-3777.

9. Feldmann, M. and Biskup, D., “Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches,” Computers & Industrial Engineering, Vol. 44, No. 2, 2003, pp. 307-323.

10. French, S., Sequencing and scheduling: An Introduction to the Mathematics of the Job Shop, England: Ellis Horwood Limited, Chichester, 1982.

11. Fry, T. D., Armstrong, R. D. and Blackstone, J. H., “Minimizing weighted absolute deviation in single machine scheduling,” IIE Transactions, Vol. 19, No. 4, 1987, pp. 445-450.

12. Gupta, J. N. D., Hennig, K. and Werner, F., “Local search heuristics for two-stage flow shop problems with secondary criterion,” Computers & Operations Research, Vol. 29, No. 2, 2002, pp. 123-149.

13. Gupta, J. N. D. and Ho, J. C., “Minimizing makespan subject minimum flowtime on two identical parallel machines,” Computers & Operations Research, Vol. 28, No. 7, 2001, pp. 705-717.

14. Heck, H. and Roberts, S., “A note on the extension of a result on scheduling with secondary criteria,” Naval Research Logistics Quarterly, Vol. 19, No. 2, 1972, pp. 403-405.

15. Ho, J. C. and 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.

16. Ignall, E. and Schrage, L., “Applications of the branch and bound technique to some flow-shop scheduling problems,” Operations Research, Vol. 13, No. 3, 1965, pp. 400-412.

17. Johnson, S. M., “Optimal two and three-stage production scheduling with setup times included,” Naval Research Logistics Quarterly, Vol. 1, No. 1, 1954, pp. 61-68.

18. Kindt, V. T., Gupta, N. D. and Billaut, J. C., “Two-machine flowshop scheduling with a secondary criterion,” Computers & Operations Research, Vol. 30, No. 4, 2003, pp. 505-526.

19. Koksalan, M. and Keha, A. B., “Using genetic algorithms for single-machine bicriteria scheduling problems,” European Journal of Operational Research, Vol. 145, No. 3, 2003, pp. 543-556.

20. Mokotoff, E., “Parallel machine scheduling problems: A survey,” Asia-Pacific Journal of Operational Research, Vol. 18, No. 2, 2001, pp. 193-242.

21. Mosheiov, G., “Simultaneous minimization of total completion time and total deviation of job completion times,” European Journal of Operational Research, Vol. 157, No. 3, 2004, pp. 296-306.

22. Murata, T., Ishibuchi, H. and Tanaka, H., “Multi-objective genetic algorithm and its application to flowshop scheduling,” Computers & Industrial Engineering, Vol. 30, No. 4, 1996, pp. 957-968.

23. Nagar, A., Haddock, J. and Heragu, S., “Multiple and bicriteria scheduling: A literature survey,” European Journal of Operational Research, Vol. 81, No. 1, 1995, pp. 88-104.

24. Pinedo, M., Scheduling Theory, Algorithms, and Systems, second edition, New Jersey: Prentice Hall, 2002.

25. Radhakrishnan, S. and Ventura, J. A., “Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times,” International Journal of Production Research, Vol. 38, No. 10, 2000, pp. 2233-2252.

26. Rajendran, C., “Heuristics for scheduling in flowshop with multiple objectives,” European Journal of Operational Research, Vol. 82, No. 3, 1995, pp. 540-555.

27. Schaffer, J. D., “Multiple objective optimization with vector evaluated genetic algorithms,” Proceedings of the First ICGA, 1985, pp. 93-100.

28. Serifoglu, F. and Ulusoy, G., “A bicriteria two-machine permutation flowshop,” European Journal of Operational Research, Vol. 107, No. 2, 1998, pp. 414-430.

29. Sevaux, M. and Peres, S. D., “Genetic algorithms to minimize the weighted number of late jobs on a single machine,” European Journal of Operational Research, Vol. 151, No. 2, 2003, pp. 296-306.

30. Shafaei, R. and Brunn, P., “Workshop scheduling using practical inaccurate data Part1： The performance of heuristic scheduling rules in a dynamic job shop environment using a rolling time horizon approach,” International Journal of Production Research, Vol. 37, No. 17, 1999, pp. 3913-3925.

31. Sidney, J. B., “Optimal single-machine scheduling with earliness and tardiness penalties,” Operations Research, Vol. 26, No. 6, 1978, pp. 1079-1082.

32. Smith, W. E., “Various optimizers for single stage production,” Naval Research Logistics Quarterly, Vol. 3, No. 1-2, 1956, pp. 59-66.

33. Sridharan, V. and Zhou, Z., “A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems,” European Journal of Operational Research, Vol. 94, No. 2, 1996, pp. 292-301.

34. Su, L. H. and Chou, F. D., “Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated,” Production Planning & Control, Vol. 11, No. 8, 2000, pp. 806-819.

35. Su, L. H. and Chou, F. D., “Heuristic for scheduling in a bicriteria single machine problem,” Journal of the Chinese Institute of Industrial Engineers, Vol. 18, No. 5, 2001, pp. 39-46.

36. Sung, C. S. and Kim, Y. H., “Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed,” Computers & Operations Research, Vol. 29, No. 3, 2002, pp. 275-294.

37. Sun, H. and Wang, G., “Parallel machine earliness and tardiness scheduling with proportional weights,” Computers & Operations Research, Vol. 30, No. 5, 2003, pp. 801-808.

38. Torres, A. J., Enscore, E. E. and Barton, R. R., “Simulated annealing heuristics for average flow-time the number of tardy jobs bi-criteria parallel machine problem,” Computers & Industrial Engineering, Vol. 33, No. 2, 1997, pp. 257-260.

39. Van Wassenhove, L. N. and Gelders, L. F., “Solving a bicriterion scheduling problem,” European Journal of Operational Research, Vol. 4, No. 1, 1980, pp. 42-48.

簡易檢索 / 詳目顯示

相關論文