基因演算法解算交期限制零工型排程問題之效果分析

Analysis of Genetic Algorithms for Job Shop Scheduling Problem with Set-up Time and Time Interval Due-date

韓駿逸

指導教授 ： 徐旭昇博士

元智大學/工程學院/工業工程與管理學系/碩士(2002年)

摘要

零工型排程問題(Job Shop Scheduling Problem, JSP)一直為學術界及產業界熱門的研究課題。在過去的研究中，一般皆不考慮機器的設置時間，目標是生產時間為最短。當產品有交期限制時，目標則為總延遲時間最短，這些問題之交期時間皆限制在某一時點。本文針對JSP問題作進一步之研究，將機器設置時間納入考量，同時放寬各產品之交期時間限制為一時段。
本研究運用基因演算法(Genetic Algorithms)求解所提出之JSP問題，並建立問題的一般數學模式與整數規劃模式。在演算法的設計上則提出一種編碼方式，配合以前學者所提出的一種編碼方法、四種交配方法與四種突變方法，共產生32種演算方法組合。本研究產生三個例題來測試這些演算組合，並依據題目大小各提出二種最佳之演算方法進行評估實驗。評估的方式將依二方面進行: (一)與套裝軟體(Lingo)比較求解題目大小為4*4之績效，(二)產生測試題庫將改善解與初始解比較其改善率。
上述的第一部份中，本研究產生十題例題以設計之程式與Lingo之結果相比，在10題當中有2題優於Lingo之結果，有6題與Lingo的結果相同，有2題結果劣於Lingo之結果。第二部份的改善績效測試上，本研究設計之程式在搜尋110000個解的情況下，求解30*30的問題時，能有22%的改善率，在求解20*20的題目時，能有22%~26%的改善率，在求解10*10的題目時，能有30%~45%的改善率。在進一步的題組測試中，兩組題目均能有20%~40%的改善率。

關鍵字

基因演算法 ； 零工型排程問題 ； 交期限制

並列摘要

Job shop scheduling problem (JSP) is an NP-hard problem that has been discussed by many researchers. Previous literature regarding JSP rarely concerns the constraints of machine set-up times and time interval due dates. The objective of this study is to develop solution procedures with the goal to minimize the total penalty cost due to earliness and tardiness of the production completion time for the JSP added with the above two constraints.
A linear integer programming model to the target problem is presented in the thesis and can be solved by LINGO software when the problem size is small. For large size problems, 32 heuristics encoded by Visual Basic 6.0 and based on genetic algorithms using different combination of methods of encoding, crossover, and mutation are developed to find acceptably good solution to the target problem. Experiments are performed in order to make suggestion on which of these heuristics is the best choice for finding good solutions with regard to problem size. As a result, we conclude that heuristics 6 and 31 are best for problem size of 10*10, heuristics 14 and 18 are best for problem size of 20*20, and heuristics 3 and 18 are best for problem size of 30*30.

並列關鍵字

Genetic Algorithms ； JSP ； Job Shop Scheduling Problem ； Time interval due-date

參考文獻

3. 錢明淦，「遺傳演算法應用於具有多種資源組態及資源限制專案計畫排程問題之研究」，私立元智大學工業工程所，碩士論文，1999。

7. 廖雯慈，「應用基因演算法求解優先順序旅行推銷員問題之研究」，私立元智大學工業工程所，碩士論文，1999。

8. 蕭義梅，「遺傳演算法應用在零工式工廠生產排程之應用」，私立元智大學工業工程所，碩士論文，1999。

11. Cheng, R., M. Gen and Y. Tsujimura, “A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms, Part I: Representation” International Journal of Computers & Industrial Engineering, Vol. 30, pp. 983-997, Spring 1996.

12. Cheng, R., M. Gen and Y. Tsujimura, “A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms, Part II: Hybrid Genetic Search Strategies” International Journal of Computers & Industrial Engineering, Vol. 36, pp. 343-364, Spring 1999.