以案例式推理為基礎的基因演算法解決生產排程問題

A Case-Based Genetic Algorithm For Scheduling Problems

何仁祥(Ren-Shiang Ho)

指導教授 ： 張百棧

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

摘要

近年來人工智慧的方法已經廣泛且有效被應用在生產排程的問題上，其中包含了模糊理論（Fuzzy theory）、遺傳演算法（Evolutionary Algorithms）、類神經網路（Neural Network）等，而這些以人工智慧為基礎的方法，最困難的工作便是要具備對於問題相當深入了解的專家知識，另外在面對較大或較複雜的排程問題時，也會使得系統難以執行。本研究結合案例式推理和基因演算法，提出以案例式推理為基礎的基因演算法，透過案例式推理的技術來找出與目前問題相似的案例，並將這些過去解決過的案例中所得到的資訊，應用到基因演算法上以解決目前的問題，最後再將目前的問題儲存起來變成案例以便未來使用。經實驗結果可發現，以案例式推理為基礎的基因演算法，不僅可以得到一組很好的起始母體，而且可以很快達到收斂的效果，最後也可得到很好的最終解。

關鍵字

動態排程 ； 案例式推理 ； 基因演算法

並列摘要

In this research, case-based reasoning and genetic algorithms are integrated into the case-based genetic algorithm in order to minimize the total weighted completion time for a single-machine scheduling problem with considering release times. This algorithm first retrieves the analogical cases from the case base then incorporates these analogies into the genetic algorithm to deal with the problem at hand. Finally, case-based genetic algorithm stores the solved problem in the case base for the future use. Extensive experimental results show that this approach outperforms the other three algorithms considered in the paper in both the computation time and the quality of solutions.

並列關鍵字

Dynamic Scheduling ； Case-Base Reasoning ； Genetic Algorithms

參考文獻

[3] Madureira, A., C. Ramos, and S.C. Silva, “A Genetic Approach for Dynamic Job-Shop Scheduling Problem,” 4th Metaheuristics International Conference, 2001.

[5] Suresh, C., R. Traub, R. Uzsoy, “An iterative heuristic for the single machine dynamic total completion time scheduling problem,” Computers and Operations Research, Vol.23, No.7, pp.641-651, 1996.

[6] Chandra, R., “On n/1/F Dynamic Deterministic System,” Naval Research Logistics Quarterly, Vol. 26, pp.537-544, 1979.

[7] Deogun, J. S., “On shcduling with Ready Time to Minimize Mean Flow Time,” The Computer Journal, Vol. 26, No 4, pp.320-328, 1983.

[8] Dessouky, M. I., and J. S. Deogun, “Sequencing jobs with unequal ready times to minimize mean flow times,” SIAM Journal Computing, Vol. 10, pp.192-202, 1981.