於流程式生產排程以基因演算法將總完工時間最小化之研究

A Study of Genetic Algorithms for Flowshop Scheduling to Minimize Makespan

李正羿(Cheng-Yi Li)

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2007年)

摘要

排程(Scheduling)被廣泛地應用在各個領域，如製造、生產管理、資訊工程等等。一個好的排程可以節省時間、降低成本且滿足顧客的要求，而流程式生產排程(Flow-Shop Scheduling)問題則是排程中常見於現實生活環境的一種排程問題。對於流程式生產而言，當我們對所有的工作進行排序時，會有n!個可行解。這樣的問題為一非多項式時間可解問題(NP-complete)，當工作數目和機器數目增大時，求解的複雜度變的相當高，因此要在有限時間內找到一個最佳解幾乎是不可能的，故有許多學者以啟發式演算法來求得近似解。近年來，啟發式演算法已經成為求解最佳化問題中之非多項式時間可解問題的主流。

在本研究中，我們應用基因演算法（Genetic Algorithms, GA）來求解最佳化之流程式生產排程的問題，並且以類似粒子群最佳化演算法(Similar Particle Swarm Optimization Algorithms, SPSOA)與互熵法(Cross Entropy Method, CE)所求得之總完工時間(Makespan)做比較。

研究結果發現，本研究所提出之演算法，在求解流程式生產排程問題時，相較於其他啟發式演算法，能夠尋找到較好的最佳近似解，因此可以證明基因演算法具有不錯之求解效能。

並列摘要

Scheduling is widely used in many fields, like information engineering, manufacture, production management and so on. A good scheduling can save time and reduce cost without decreasing the satisfaction of customers. The “flow-shop scheduling” is the most common problem in the daily life. For this specific problem, there will be n! feasible solutions when we sequence all of the jobs by flow-shop scheduling problems, and this will become a NP-complete problems in mathematics. In other words, the complexity of finding the solutions will be increased with the number of the elements, and it will almost be impossible to find the optimal solution in a short time. Recently, the heuristics algorithms have become the most popular ones to find the optimal solutions of the NP-complete problems, and many literatures in the area had been published.
In this paper we application the genetic algorithms (GA) to find the optimal solutions of the flow-shop scheduling problems and shows the comparisons of the results of makespan which derived from the GA method and similar particle swarm optimization algorithms (SPSOA) and cross-entropy method (CE).
It has been found that the proposed algorithm, genetic algorithms, is better than other heuristics ones when finding the optimal approximate solutions of the flow-shop scheduling problems.

參考文獻

[7]黃格威，2006，混合式進化演算法於無線基地台配置決策之應用，國立虎尾科技大學，碩士論文。

[11]Alon G., Kroese D. P., Raviv T., and Rubinstein R. Y., 2004,“Application of the Cross-Entropy Method to the Buffer Allocation Problem in a Simulation- Based Environment”, Annals of Operation Resear.

[12]Asmussen S., Kroese D. P., and R. Y. Rubinstein, 2004,“Heavy tails, importance sampling and cross-entropy”, Stochastic Models.

[13]Chepuri K. and Homem-de-Mello T., 2004,“Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method”, Annals of Operations Research.

[14]Cohen I., Golany B., and Shtub A., 2004,“Managing stochastic finite capacity multi-project systems through the cross-entropy method”, Annals of Operations Research.