應用優生基因演算法解JSP問題

NHUIR > College of Science and Technology > Department of Information Management > Disserations and Theses > Item 987654321/22501

Please use this identifier to cite or link to this item: http://nhuir.nhu.edu.tw/handle/987654321/22501

Title:	應用優生基因演算法解JSP問題
Other Titles:	An Eugenic Genetic Algorithm for the Job-shop scheduling problem
Authors:	黃富一 Huang, Fu-yi
Contributors:	資訊管理學研究所邱宏彬 Hong-bin Chiu
Keywords:	零工式排程;遺傳演算法;優生遺傳演算法 job-shop scheduling problem;genetic algorithm;eugenic genetic algorithm
Date:	2006
Issue Date:	2015-08-04 14:50:10 (UTC+8)
Abstract:	在現今的資訊時代環境，企業國際化使得產業界競爭更加激烈，市場需求快速提升。產業界的生產排程領域中，若能發展出良好的排程方法，將資源善加規劃做有效的利用，節省人力，滿足市場需求並降低成本，減少資源的浪費是很重要的關鍵因素。　　　目前排程種類方法眾多，其中零工式排程問題( 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.
Appears in Collections:	[Department of Information Management] Disserations and Theses

Files in This Item:

File	Description	Size	Format
094NHU05396013-001.pdf		667Kb	Adobe PDF	0	View/Open
index.html		0Kb	HTML	149	View/Open

Loading...