運用延伸人工染色體基因演算法求解單列機台佈置問題

Solving Single Row Facility Layout Problem Using Extended Artificial Chromosome Genetic Algorithm

單列機台佈置問題 （single row facility layout problem, SRFLP） 是一個NP-Complete 的問題，該問題之目標值是希望將兩兩機台間距離之和最小化。延伸人工染色體基因演算法 （extended artificial chromosome genetic algorithm,eACGA） 是結合基因演算法 （genetic algorithm, GA） 及分佈估計演算法 （estimationof distribution algorithm, EDA）。該方法在解決生產排程問題上獲得了不錯的成果。本研究修改eACGA之方法並用來解10個SRFLP標竿問題，計算結果顯示eACGA較GA或EDA 更可獲得較好之目標值及較低誤差值。

The layout positioning problem of facilities on a straight line is knownas Single Row Facility Layout Problem (SRFLP). The objective ofSRFLP, categorized as NP-Complete problem, is to arrange the layout suchthat the sum of distances between all facilities’ pairs can be minimized.Extended Artificial Chromosome Genetic Algorithm (eACGA) is a promisingalgorithm that has been proposed recently. eACGA extends theprobabilistic model in Estimation of Distribution Algorithms (EDAs) andthen hybridize it with Genetic Algorithms (GAs). eACGA is proven toproduce an excellent solution for scheduling problem. In this paper, we modify the eACGA to solve SRFLP. Computational results on benchmarkproblems show the effectiveness of eACGA for solving SRFLP.