在現今的複雜環境之下，各產業界競爭激烈，市場需求在短時間內快速提升。若發展出良好的排程方法，可將資源善加規劃做為有效的利用，並節省許多人力、成本與其他資源的浪費。生產排程領域中，排程種類眾多，其中以零工式排程問題(Job shop problem,JSP)，是最著名的NP-hard最佳化問題。遺傳演算法是解決最佳化問題最常用的技巧，因此本研究以部分配對交配(Partial-mapped crossover, PMX)和反向突變(Reversion Mutation)機制之演化運算來了解此方法在JSP最佳排程的效果。 在實驗部分，依據傳統JSP的benchmark問題來測試。在參數部份，分別設定不同的交配率與突變率，進行模擬實驗。根據各參數在執行排程演算時，比較排程最佳完工時間(Makespan)降低之情形，歸納出有利於JSP排程的參數組合，以符合排程效益。 In today’s complicated environment, each industry field competition are violent and the market demand promotes quickly within a short time. If we develop a good scheduling method, we can program resources to economize the use of manpower, cost, and other resources. In the production scheduling domain, the scheduling categories are numerous, among them take job-shop scheduling problem (JSP) as the most well-known problem. Genetic algorithm is a common use technique to solve optimal problem. So, our research use partial-mapped crossover (PMX) and reversion mutation (RM) to resolve job-shop scheduling problem. In our experiment, we test it based on the tradition benchmark problem of JSP. In parameters, we set different mate and mutation probability to execute imitating the experiment. In accordance with each parameters execution of scheduling, we compare the reduce situation of the makespan. We induce many favorable parameters association of the JSP to accord scheduling benefit.
