在現今的資訊時代環境，企業國際化使得產業界競爭更加激烈，市場需求快速提升。產業界的生產排程領域中，若能發展出良好的排程方法，將資源善加規劃做有效的利用，節省人力，滿足市場需求並降低成本，減少資源的浪費是很重要的關鍵因素。
　
　　目前排程種類方法眾多，其中零工式排程問題( Job shop problem，JSP )，是最著名的 NP-hard 最佳化問題。遺傳演算法是解決最佳化問題最常用的技巧。但是遺傳演算法最令人困擾的問題是收斂快時，解的品質穩定性不佳。而解的品質好穩定性佳時，可能陷入區域解，缺乏多樣性，且收斂速度慢。所以集中度及多樣性要取得平衡，是重要的問題。
　
　　本研究在解決零工式排程問題上， 以遺傳演算法為基礎，改良加入優生政策，調整演算過程期望在集中度及多樣性取得平衡。運用優生繁殖複製，以部分配對交配( Partial-mapped crossover , PMX )和反向突變( Reversion Mutation )機制及優生突變之演化運算。目的以優生繁殖複製提升解的品質穩定性及改善收斂速度，而以優生動態突變提升演算過程搜尋的多樣性。經由實驗結果分析優生基因演算法解JSP問題，確實改善傳統基因演算法，有較佳的解的品質及穩定性。

　　Under present information era and environment, the internationalization of enterprise makes industrial circles much more competitive and market demands enhanced rapidly. In the field of the productive schedule in the industrial circles, it is a very important key factor to reduce the waste of resources. Viewed so, this study intends to develop a better method for the productive schedule in order to draw up a better scheme for making good use of resources, saving manpower, meeting market demands and lowering costs.
　
　　Currently, among many kinds of the productive schedule, the job-shop scheduling problem (JSP) is the best well-known as the NP-hard optimal problem. And the genetic algorithm is a skill used most frequently to solve the NP-hard optimal problem. However, there are two annoying problems in the genetic algorithm. For one, when the speed of convergence becomes fast, the quality of the solution cannot have a good stability. For the other, when the quality of the solution has good stability, it may fall into the local solution and have lack of variety. Besides, the speed of convergence may become slower. Seen in this way, how to make concentration degree and variety balanced is an essential issue.
　
　　On this basis, this study aims to solve the job-shop scheduling problem (JSP) according to genetic algorithm, in addition to eugenic policy, to adjust the process of mathematical calculation to make the concentration degree and variety balanced. We intend to use the eugenic breeding and duplication by means of Partial-mapped Crossover (PMX), Reversion Mutation Mechanism and the evolutional operation of eugenic mutation to do mathematical calculations. Our goal is to promote the stability of the quality of solution and improve the speed of convergence through the eugenic breeding and duplication. Our purpose is to promote the variety of surfing in the process of mathematical calculation via the eugenic dynamic mutation. We expect to solve the job-shop scheduling problem (JSP) by analyzing the experimental results according to eugenic genetic algorithm so as to improve the traditional genetic algorithm and provide a better quality of solution with better stability.

書名頁....................................... ii
論文指導教授推薦函........................... iii
論文口試合格證明............................. iv
誌謝辭或序言................................. v
中文摘要..................................... vi
英文摘要..................................... vii
目錄......................................... viii
表目錄....................................... ix
圖目錄....................................... x
　
第一章 緒論.................................. 1
第一節 研究背景與動機........................ 1
第二節 研究目的.............................. 2
第三節 研究流程.............................. 3
第四節 研究問題與方法描述.................... 4
第五節 論文架構.............................. 7
　
第二章 文獻回顧與探討........................ 8
第一節 排程的定義與分類...................... 8
第二節 零工式排程............................ 12
第三節 遺傳演算法............................ 15
第四節 遺傳演算法在JSP之編碼型態............. 20
第五節 遺傳演算法在JSP之交配與突變方法....... 21
第六節 優生遺傳演算法........................ 25
　
第三章 建立系統架構.......................... 28
第一節 建立應用優生演算法於JSP問題之系統架構. 28
第二節 優生基因演算法在JSP問題上的應用....... 31
　
第四章 實驗結果與分析........................ 43
第一節 實驗測試環境.......................... 43
第二節 實驗設計.............................. 43
第三節 實驗測試、結果分析.................... 44
　
第五章 結論與未來展望........................ 50
第一節 結論.................................. 50
第二節 未來展望.............................. 51
　
參考文獻..................................... 52

一、中文部份
　
[1] 林淳菁，「應用遺傳基因演算法求解不相關平行機台之排程問題」，朝陽科技大學工業工程與管理研究所碩士論文，民國90 年。
　
[2] 林亞泰，「以代理人為基礎之虛擬企業資訊系統整合方法之研究」，朝陽科技大學資訊管理研究所碩士論文，民國91 年。
　
[3] 林純行，「多階平行機器零工式多目標排程之模式化與系統之研究」， 東海大學工業工程研究所碩士論文，民國92 年。
　
[4] 陳宜欣，「遺傳演算法在Job Shop 排程問題上的研究」，中央大學資訊管理研究所碩士論文，民國86 年。
　
[5] 周鵬程，遺傳演算法原理與應用活用Matlab，台北：全華科技圖書，民國91 年。
　
[6] 湯璟聖，「動態彈性平行機群排程的探討」，中原大學工業工程研究所，民國92 年。
　
[7] 張百棧、謝日章、蕭陳鴻，「基因演算法於非等效平行機台排程之應用」，Journal of the Chinese Institute of Industrial Engineers,vol.19, No.2, pp79-95.
　
[8] 詹詠翔，「二機連續性零工工廠總時程最小化排程問題之研究」，朝陽科技大學工業工程與管理碩士論文，民國93 年。
　
[9] 廖經芳、林安祥，「開放工廠總加權延遲最小化排程問題之研究」，中國工業工程學刊，民國88 年。
　
[10]蕭義梅，「遺傳演算法應用在零工式工廠生產排程之應用」，元智大學工業工程研究所碩士論文，民國88 年。
　
[11]蘇恆磊，「遺傳演算法於零工式生產排程系統之應用」，國立海洋大學系統工程暨造船學系碩士論文，民國91 年。
　
[12]謝文天，「基於遺傳演算法之最佳化排程技術的研究」，南華大學資訊管理研究所碩士論文，民國94年。
　
[13]于正之，「優生遺傳演算法應用於解旅行推銷員問題」，國立中興大學應用數學研究所碩士論文，民國86年。
　
二、西文部份
　
[14]B.J.Park , H.R.Choi and H.S.Kim , "A hybrid genetic algorithm for the job shop scheduling problems",Computers & Industrial Engineering 45 , pp.597-613 , 2003.
　
[15]B.Sandikci , "Genetic Algorithms", In partial fulfillment of the requirements for the course IE572 Spring , 2000.
　
[16]D.A.Koonce and S.C.Tsai , "Using data mining to find patterns in genetic algorithms solutions to a job shop schedule", Computers & Industrial Engineering 38 , pp.361-374 , 2000.
　
[17] D.E.Goldberg , "Genetic algorithms: in search, Optimization and Machine Learning", Addision-Wesley Publishing Co , 1989.
　
[18] E.D.Taillard , "Parallel taboo search techniques for the job shop scheduling problem" , ORSA Journal on Computing 6 , pp.108-117, 1994.
　
[19]E.Nowicki and C.smntnicki , " A fast tabu search algorithm for the job shop problem" , Management Science42, pp.797-813, 1996.
　
[20] F.Pezzella and E.Merelli , "A tabu search method guided by shiffing bottleneck for the job shop scheduling problem" , European Journal of Operational Research 120 , pp.297-310 , 2000.
　
[21] G.Cavory , R.Dupas and G.Goncalves , "A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints", European Journal of Operation Research 161 , pp.73-85 , 2005.
　
[22]H.Zhou , Y.Feng and L.Han , "The hybrid heuristic genetic algorithm for job shop scheduling, Computers & Industrial Engineering 40 , pp.191-200 , 2001.
　
[23] I.Ono , M.Yammamura and S.Kobayashi , "A Genetic algorithm for Job-Shop Scheduling Problems Using Job-Based Order Crossover", proc. ofICEC’96 , pp.547-552 , 1996.
　
[24] J.F.Goncalves , J.J.M.Mends and M.G.C.Resende , 　"A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem", European Journal of Operational Research 167 , pp77-95 , 2005.
　
[25] J.F.Muth and G.L.Thompson , "Industrial scheduling" , Englewood Cliffs,NJ:Prentice Hall , 1963.
　
[26] J.Holland , "Adaptation in Natural and Artificial Systems" , University of Michigan Press , Ann Arbor,Michigan , 1975.
　
[27]J.H.Blackstone.Jr , D.T.Phillips , G.L.Hogg , "A state-of-the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research 20, pp.27-45 , 1982.
　
[28] K.Steinhofel , A.Albrecht and C.K.Wong , "Two simulated annealing-based heuristics for the job shop scheduling problem" , European Journal of Operational Research 118 , pp.524-548 , 1999.
　
[29]L.Wang and D.Z.Zheng , "An effective hybrid optimization strategy for job-shop scheduling problems", Computers & Operations Research 28 , pp.585-596 , 2001.
　
[30]M.E.Aydin and T.C.Fogarty , "Simulated annealing with evolutionary processes in job shop scheduling" , In Evolutionary Methods for Design , Optimisation and Control , 2002.
　
[31] M.Koksalan and A.B.Keha , "Using genetic algorithms for single machine bicritria scheduling problems " , European Journal of Operational Research 145 , pp.543-556 , 2003.
　
[32] M.Perregaard and J.Clausen , "Parallel branch-and-bound methods for the job-shop scheduling problem" , Annals of Operations Research , Vol.83 , no.1 , pp.137-160 , 1998.
　
[33] M.Singer and P.Michael , "A computation study of branch and bound techniques for minimizing the total weighted tardiness in job shop" ,IEE Transactions 30 , pp109-118 , 1998.
　
[34] P.Brucker , B.Jurisch and B.Sievers , "A branch and bound algorithm for the job-shop scheduling problem" , Discrete Applied Mathematics Volume 49 , Issue1-3 , 1994.
　
[35] R.Cheng , M.Gen and Y.Tsujimura , "A Tutorial Survey Of Job Shop Scheduling Problem Using Genetic algorithms-I Representation" , Computers ind. Engng vol.30 , No.4 , pp.983-997 , 1996 .
　
[36] R.Cheng , M.Gen and Y.Tsujimura , "A tutorial survey of job-shop scheduling problem using genetic algorithms, Part II: hybrid genetic search strategies", Computers & Industrial Engineering 36 , pp.343-364 , 1999.
　
[37] R. T. Moghaddem and M. D.Mehr , "A Computer simulation model for job shop scheduling problems minimizing makespan" Computers & Industrial Engineering 48 , pp.811-823 , 2005.
　
[38] S.Lawrence," Resource constrained project scheduling : An experimental investigation of heuristic scheduling techniques", Graduate school of Industrial administration , Carnegie Mellon University : Pittsburgh , 1984.
　
[39] S.Y.W.Wong , "Hybrid simulated annealing /genetic algorithm approach to short term hydro-thermal scheduling with multiple thermal plants" , Electrical Power & Energy Systems 23 , pp.565-575 , 2001.
　
[40] T.Satake , K.Morikawa , K.Takahashi and N.Nakamura , "Simulated annealing approach for minimizing the makespan of the general job-shop" International Journal of Production Economics, pp.515-522 , 1999.
　
[41] V.Armentano and C.R.Scrich , "Tabu search for minimizing total tardiness in a job shop", International Journal of Production Economics ,63(2) , pp.131-140 , 2000.
　
[42] W.T.Chan and H.Hu , "An application of genetic algorithms to precast production scheduling",Computers and Structures 79 , pp.1605-1616 , 2001.
　
[43] Y.Tsujimura , Y.Mafune and M.Gen , "Effects of Symbiotic Evolution in Genetic Algorithms for job-shop scheduling", Proceddings of the 34TH Hawaii International Conference on System Sciences , 2001.
　
[44] A.S. Jain, S. Meeran | European Journal of Operational Research 113(1999).