穩健多目標基因演算法應用於流程型工廠之排程研究

Robust Multi-Objective Genetic Algorithm for Flowshop Scheduling Problems

廖麗滿(Li-Man Liao) ； 黃敬仁(Ching-Jen Huang) ； 林志諭(Zhi-Yu Lin)

《技術學刊》 26卷1期 (2011/03) Pp. 65-71

https://doi.org/10.29507/JT.201103.0007

摘要

本研究以基因演算法爲基礎發展啟發式演算法，求解最大完工時間、總流程時間、總延遲時間爲目標之流程型工廠排程問題，分析交配機制、強化策略，以及分散策略於多目標基因演算法之效果。首先，運用OPX、2PX、SJOX三種交配機制，分別分析其演算品質。然後，求解時間與品質的權衡下，執行強化策略，其中強化策略包含選擇優良解進行局部搜尋、使用簡易啟發式演算法加入優良解，以及利用人造解演算機制加入優良解。並於解群體的分散度較低時，運用分散策略產生部份新解。爲得到搜尋策略與參數的最佳組合，應用變異數分析法，且以綜合相對誤差爲指標，獲得較佳之柏拉圖最佳解。實驗結果顯示，本演算法可求得更有效的柏拉圖最佳解。

關鍵字

基因演算法 ； 流程型工廠 ； 排程 ； 多目標 ； 柏拉圖最佳解

並列摘要

This paper proposes a GA-based algorithm for flowshop scheduling problems (FSP) with multiple objectives which are makespan, total tardiness and total flow time. The algorithm analyzes the effects of crossover, intensification and diversification strategies in multi-objective genetic algorithms (MOGA). Firstly, OPX, 2PX, and SJOX crossover mechanisms are applied and their performance analyzed. Then, considering the tradeoffs of run time and solution quality, the GA-based heuristic applies three intensification strategies to rapidly search for good solutions. The strategies include local search, simple heuristics, and an artificial solution production mechanism. Additionally, if the diversity value falls below a given threshold value, a diversification strategy is applied where part of the population is regenerated. In order to obtain a good search strategy and calibrate the parameters of GA-based algorithms, analysis of variances (ANOVA) is adopted. The optimal combination of GA parameters is found and the better Pareto optimal solution set is obtained. Computational results show that the heuristic can find more effective Pareto optimal solutions.

並列關鍵字

genetic algorithm ； flowshop ； scheduling ； multi-objective ； Pareto optimal solutions