應用混合式基因演算法求解流程型工廠之多目標排程問題

An Application of Hybrid Genetic Algorithm for Scheduling in Flowshop with Multiple Objectives

林水耕(Shui-Geng Lin)

指導教授 ： 張百棧

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

摘要

在多目標問題當中，由於各個目標之間往往是相互衝突的，若只是一昧求其中單一目標的最佳排程，經常會造成其他目標的損失。因此如何在多個具有衝突的目標之間，找到一個平衡點，來達到整體的最佳目標，使整體的目標能夠符合決策者的要求，確實是一個相當困難的問題。在本研究的基因演算法和混合式基因演算法中，為了要達到搜尋所有可能的柏柆圖最佳解，本研究提出一個以演化世代數作為權重指定的基礎，可以根據決策者所訂定的目標優先順序以漸進式的權重指定方式，來搜尋在此優先順序下的柏拉圖最佳解(Pareto Optimal Solutions)。而此方法有別於一般在同一世代內隨機指定染色體變動權重的方式。經實驗證明，本研究所提出之漸進式優先順序法在求解時間與求解品質上均具有不錯的效果。

關鍵字

基因演算法 ； 流程型工廠 ； 多目標排程問題 ； 柏拉圖最佳解 ； 變動權重

並列摘要

The objectives are competitive in solving the multi-objective scheduling problem. Supposing that we just concentrate on searching the optimal schedule with respect to one of the objectives, it leads to the loss of the other objectives. And the optimal schedule of the specified objective is always a local optimum to the multi-objective scheduling problem. As for how to achieve the global optimization is a really hard problem. Conventionally, for lowering the complexity, multi-objective problems are transformed into single objective problem through linear combination. Supposing that the searching direction is fixed and many other superior solutions cannot be visited. In this research, to recover the key drawback of the conventional approach, we propose the gradual-priority weight assignment (GPWA) approach to search the Pareto optimal solutions. GPWA searches feasible region from the first objective in the beginning and toward the other objectives gradually. For verifying the effectiveness and efficiency, GPWA compares with the variable weights approach proposed by Murata et al. As the results of comparisons, GPWA performs quite effectively and efficiently.

並列關鍵字

Genetic Algorithm ； Flowshop ； Multi-objective scheduling ； Pareto Optimal Solutions ； Variable Weights Approach

參考文獻

[31] Tamaki, H., H. Kita, and S. Kobayashi, “Multi-Objective Optimization by Genetic Algorithms: A Review,” Proceedings of IEEE International Conference on Evolutionary Computation,” pp.517-522, 1996.

[2] Chen, C. L., V. S. Vempati and N. Aljaber, “An Application of Genetic Algorithms for Flow Shop Problems,” European Journal of Operational Research, 80, pp.389-396.1995.

[3] Davis, L., Handbook of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1987.

[4] French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop, John Wiley, New York, 1982.

[5] Gangadharan, R. and C. Rajendran, “A Simulated Annealing Heuristic for Scheduling in a Flowshop with Bicriteria,” Computers & Industrial Engineering, 27, pp.473-476, 1994.