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

Robust Multi-Objective Genetic Algorithm for Flowshop Scheduling Problems

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

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