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

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

Amalia Utamima ； 歐陽超(Chao Ou-Yang)

《技術學刊》 27卷4期 (2012/12) Pp. 189-194

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

摘要

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

關鍵字

單列機台佈置問題 ； 基因演算法 ； 分佈估計演算法

並列摘要

The layout positioning problem of facilities on a straight line is known as Single Row Facility Layout Problem (SRFLP). The objective of SRFLP, categorized as NP-Complete problem, is to arrange the layout such that the sum of distances between all facilities' pairs can be minimized. Extended Artificial Chromosome Genetic Algorithm (eACGA) is a promising algorithm that has been proposed recently. eACGA extends the probabilistic model in Estimation of Distribution Algorithms (EDAs) and then hybridize it with Genetic Algorithms (GAs). eACGA is proven to produce an excellent solution for scheduling problem. In this paper, we modify the eACGA to solve SRFLP. Computational results on benchmark problems show the effectiveness of eACGA for solving SRFLP.

並列關鍵字

single row facility layout ； estimation distribution algorithm ； genetic algorithm