臺灣博碩士論文加值系統

在生產排程問題中，零工式生產排程問題(Job-shop scheduling problem，JSP)占了相當重要的地位，許多產業的排程類型皆屬於此類，綜觀目前高科技產業，例如：半導體產業、TFT-LCD產業等，大多數都是屬於零工式生產的範疇，而JSP問題由於變化性大，在排程中的組合最佳化問題是公認最為複雜困難的NP-hard問題之一。許多專家學者利用通用演算法來求解JSP問題，其中基因演算法(Genetic algorithm, GA)由於具有強大的全域搜尋能力，廣泛的被運用到排程問題上。但因基因演算法在局部區域搜尋能力的不足，使得演化搜尋過程容易陷入局部最佳解中，降低了求解的效率。本研究針對此現象，將基因演算法結合模擬退火法(Simulated Annealing algorithm，SA)中的波茲曼函數，利用其不易陷入局部最佳解之特性，進而發展出波茲曼基因演算法(Boltzmann Genetic Algorithm，BGA)，並在所選定的零工式排程問題中針對求解品質與求解效率上與傳統基因演算法進行求解極小化最大總完工時間的比較測試，實驗結果顯示以波茲曼基因演算法求解JSP問題，在求解效率上明顯比傳統基因演算法來的優異，對於企業在規劃生產排程決策上，能有效的節省生產時間成本，達到更佳的效益。

Job-shop scheduling problem (JSP), which was wildly used in industries, plays a vital role in manufacture scheduling. Many of the high-tech industries such as semiconductor industries, TFT-LCD industries belong to the Job-shop scheduling. Nevertheless, due to the variation of JSP, its combinatorial optimization problem in scheduling is recognized as one of the most complicated NP-hard problems. Many experts and scholars use the Generic algorithm to seek out the JSP problem, and its powerful searching ability of Genetic algorithm (GA) was widely applied in scheduling problem. However, the insufficiency of searching partial area in GA makes the process of evolutionary searching easily fall into the local optimal solution, lowering the efficiency of seeking out the optimal solution. Based on this phenomenon, this study combines GA with Boltzmann function in Simulated Annealing algorithm, which is characterized as not easily fall into local optimal solution, developing Boltzmann Genetic Algorithm (BGA), and aims to compare the quality and efficiency between BGA and traditional GA in minimum makespan in JSP. The result of this study indicates the advantageous of BGA over traditional GA in seeking out JSP, suggesting that the BGA can save extra time and cost, and benefit industries in planning manufacturing scheduling.

摘要 I
ABSTRACT II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究方法 3
1.4 研究架構 3
第二章 文獻探討 5
2.1 零工式生產排程相關文獻 5
2.1.1 績效衡量準則 6
2.1.2 派工法則(Dispatching) 7
2.2 基因演算法 9
2.3 模擬退火法 16
2.3.1 模擬退火法組成要素 16
2.3.2 模擬退火法演算步驟 17
2.4 改良型演算法 20
第三章 研究方法 21
3.1 波茲曼函數 21
3.2 波茲曼基因演算法 22
3.3 研究方法 26
3.3.1 編碼方式 26
3.3.2 產生初始族群 29
3.3.3 零工式生產排程限制條件 30
3.3.4 績效衡量標準及適應函數 30
3.3.5 參數設定 30
3.4 測試之問題 31
第四章 實驗結果與分析 35
4.1 實驗結果 35
4.1.1 固定演算次數而比較求解品質 35
4.1.2 固定解之值而比較求解效率 44
4.2 比較與分析 48
4.3 突變率之敏感度分析 51
第五章 結論與建議 53
5.1 研究結論 53
5.2 未來研究方向 53
參考文獻 55

中文文獻
【1】周鵬程，「遺傳演算法原理與應用-活用Matlab」，全華圖書股份有限公司，2007。
【2】莊元明，「建立退火基因演算法反算海底地音參數」，國立臺灣大學學造船及海洋工程學研究所碩士論文， 2001。
【3】張百棧、許如欽，「模擬退火法應用於並行處理器上之排程問題探討」，中國工程學刊，第17期，第4卷，第458-497頁，1994。
【4】張嘉君，「應用模擬退火法求解營建工程專案多重資源排程最佳化之研究」，朝陽科技大學營建工程系碩士論文，2003。
【5】陳宜欣，「遺傳演算法應用在Job Shop 排程問題上的研究」，國立中央大學資訊管理系碩士論文，1997。
【6】鄭琦龍，「應用改良式遺傳基因演算法求解流程型平行機台之排程問題探討~以電子組裝SMT製程為例」，雲林科技大學工業工程與管理系碩士論文，2004。
【7】盧研伯，「混合式模擬退火法應用於具迴流特性流程工廠之研究」台灣科技大學工業管理系碩士論文，2003。
【8】蘇義梅，「遺傳演算法應用在零工式工廠生產排程之應用」，元智大學工業工程系碩士論文，1998。
【9】蘇恆磊，「遺傳演算法於零工式生產排程系統問題之應用」，海洋大學系統工程暨造船學系碩士論文，2002。

英文文獻
【10】Al-Hakim, L.“An Analogue Genetic Algorithm for Solving Job Shop Scheduling Problems,” International Journal of Production Research, Vol. 39, No. 7, pp. 1537-1548, 2001.
【11】Carlier, J. and E. Pinson,“An Algorithm for Solving the Job-Shop Problem,” Management science, Vol. 35, No. 2, pp. 164-176, 1989.
【12】Coello, C. C. A., D. C. Rivera, and N. C. Cortes,“Use of an Artificial Immune System for Job Shop Scheduling,”Lecture Notes in Computer Science, Vol. 2787, pp. 1-10, 2003.
【13】Dorndorf, U. and E. Pesch,“Evolution based learning in a job shop scheduling environment,” Computers & Operations Research, Vol. 22, No. 1, pp. 25-40, 1995.
【14】Gen, M., Y. Tsujimura, and E. Kubota, “Solving Job-Shop Scheduling Problems by Genetic Algorithm,” IEEE International Conference, Vol. 2, pp. 1577-1582, 1994.
【15】Gonçalves, J. F., J. J. de Magalhães, and M. G. C. Resende,“A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem,” AT&T Labs Research Technical Report TD-5EAL6J, 2002.
【16】Holland, J. H., Adaptation in Natural and Artificial System, Ann Arbor: The University Michigan Press, 1975.
【17】Holloway, C. A. and R. T. Nelson,“Job shop scheduling with due dates and overtime capability,” Management science, Vol. 21, No. 1, pp. 68-78, 1974.
【18】Ishibuchi, H. and T. Murata, “A multi-objective genetic local search algorithm and its application to flowshop scheduling,” IEEE Transactions on System, Man, and Cybernetics-Part C : Application and Review, Vol. 28, No. 3, pp392-403, 1998.
【19】Jeffcoat, D.E. and R.L. Bulfin, “Simulated Annealing for Resource -Constrained Scheduling,” European Journal of Operational Research, Vol.70, pp.43-51. 1993.
【20】Kim, G. H. and C. S. G. Lee, “An evolutionary approach to the job-shop scheduling problem,” Proceedings IEEE International Conference on Robotics and Automation, Vol.1, pp501-506, 1994.
【21】Kirkpatrick, S., C.D. Gelatt Jr., and M.P. Vecchi, “Optimization by simulated annealing,” Science, Vol. 220, No. 4589, pp.670-680,1983.
【22】Lawler E. L., J. K. Lenstra, K. A. H. G. Rinnooy, and D. B. Shmoys, “Sequencing and scheduling: algorithms and complexity,” Handbooks in Operations Research and Management Science, Vol. 4, 1993.
【23】Lenstra, J. K., K. A. H. G. Rinnooy, R. L. Graham, and E.L. Lawler, “Optimization and approximation in deterministic sequencing and scheduling: a survey,” Annals of Discrete Mathematics, Vol. 5, pp. 287-326, 1979.
【24】Mattfeld, D. C. and R. J. M. Vaessens, “Job Shop Problem Test Instances Set”, 2003.
【25】Metropolis, N., A.W. Rosenblush, M.N. Rosenblush, A.H. Teller, and E. Teller, “Equation of state calculations by fast computing machines,” The Journal of Chemical Physics,Vol. 21,No. 6, pp. 1087-1092, 1953.
【26】Muth, J. F. and G. L. Thompson, Industrial Scheduling, Prentice Hall, Englewood Cliffs , 1963.
【27】 Ponnambalam, S. G., P. Aravindan, and S. V. Rajesh,“A Tabu Search Algorithm for Job Shop Scheduling,” The International Journal of Advanced Manufacturing Technology, Vol. 16, No. 10, pp.765-771, 2000.
【28】Wang, L. and D. Zheng, “An effective hybrid optimization strategy for job-shop scheduling problems,” Computers & Operations Research, Vol. 28, pp. 585-596, 2001.
【29】Wong, C., K. K. Steinhofel, and A. Albrecht, “Two Simulated Annealing-Based Heuristics for the job shop scheduling problem,” European Journal of Operational Research, Vol. 118, No. 3, pp524-548, 1999.
【30】Wang, L. and D. Zheng, “A Modified Genetic Algorithm for Job Shop Scheduling,” The International Journal of Advanced Manufacturing Technology, Vol. 20 No. 1, pp. 72-76, 2002.
【31】Yamada, T. and R. Nakano,“Genetic Algorithms for Job Shop Scheduling Problems,” Proceedings of Modern Heuristic for Decision Support, pp. 67-81, 1997.