Title

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

Translated Titles

Robust Multi-Objective Genetic Algorithm for Flowshop Scheduling Problems

DOI

10.29507/JT.201103.0007

Authors

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

Key Words

基因演算法 ; 流程型工廠 ; 排程 ; 多目標 ; 柏拉圖最佳解 ; genetic algorithm ; flowshop ; scheduling ; multi-objective ; Pareto optimal solutions

PublicationName

技術學刊

Volume or Term/Year and Month of Publication

26卷1期(2011 / 03 / 01)

Page #

65 - 71

Content Language

繁體中文

Chinese Abstract

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

English Abstract

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.

Topic Category 工程學 > 工程學綜合
Times Cited
  1. 陳建隆(2008)。基因演算法於多目標TFT-LCD模組廠排程問題之研究。元智大學工業工程與管理學系學位論文。2008。1-94。 
  2. 黃鈺馨(2013)。混合整數規劃轉換成非線性規劃方法研究。屏東科技大學工業管理系所學位論文。2013。1-39。 
  3. 林振豪(2017)。膽結石病患伴隨腎結石之評估研究。虎尾科技大學工業管理系工業工程與管理碩士班學位論文。2017。1-75。