遺傳演算法應用在零工式工廠生產排程之應用

Application of Genetic Algorithm in Job-Shop Scheduling

蕭義梅(Yi-Mei Hsiao)

指導教授 ： 張百棧博士

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

摘要

快速的排程是工廠急欲解決的問題，遺傳演算法是目前常用解決NP-hard 排程問題的方法。在傳統上，使用遺傳演算法是需要長時間的演進，而時間正是排程問題的最大敵人。
本研究的目的在於如何利用遺傳演算法的良好特性：跳脫區域最佳解，並排除需要長時間演進的問題，使得可在短時間內獲得好的答案。
研究的結果中發現，在特定的交配法及突變率下，確實可讓問題快速的收斂，且也達到不錯的答案。

關鍵字

零工式工廠生產排程 ； 遺傳演算法 ； 生產排程

並列摘要

In factory, it is an important problem for scheduling rapidly, and genetic algorithm is a popular method to solve the NP-hard scheduling problem. In tradition, using genetic algorithm to solve the problem needs a long time, but ''time'' is the most important problem in scheduling.
This research intends to how to use the character of genetic algorithm to escape the trap in local solution, and exclude the long time of evolution from the genetic algorithm, then get the better solution in short time.
In this research, we develop a combination of using crossover, and mutation rate, to derive the solution fast and better.

並列關鍵字

Job-Shop Scheduling ； Genetic Algorithm ； Scheduling

參考文獻

【1】 Autin, S. "An introduction to genetic algorithms," AI Expert , pp.49-53.1990.

【2】 Ballakur, A., and H. J.Steudel, "Integration of Job Shop Control System : a State-of-the-Art Review," Journal of Manufacturing Systems, Vol. 3,No.1,pp.71-79. 1984.

【4】 Croce, F.D., Tadei, R. and Volta, G. "A genetic algorithm for the job shop problem," Computer Operation Research 22(1),pp.15-24.1995

【6】 Dorndorf, U. and Pesch, E., "Evolution based learning in a job shop scheduling enviroment," Computer Operation Research 22(1), pp.25-40.1995.

【8】 Gen, Mitsuo, Yasuhiro Tsujimura and Erika Kubota, "Solving Job Shop Scheduling Problem Using Genetic Algorithm ,"Proc. of 16th Int. Con. on Computers&Ind. Eng., Mar.7-9,pp.576-579.1994.