Title: 以進化搜尋演算法求解流線群組排程問題
Using Meta-Heuristics Algorithms for Solving Flow-Shop Family-Based Scheduling Problems
Authors: 巫木誠
Keywords: 染色體表達法;基因演算法;蟻群演算法;Chromosome Representation;Genetic algorithm;Ant Colony Optimization;Scheduling
Issue Date: 2012
Abstract: 本研究探討工序固定之製造單元排程問題(permutation manufacturing-cell flow shop,PMFS) 。過去文獻多數是用進化演算法(meta-heuristic algorithms)求解此問題,所採用之解表達法稱為Sold。本研究提出一新的解表達法(簡稱Snew),然後依照此表達法發展進化式演算法。本研究據此比較四種演算法:GA_Snew, GA_Sold, ACO_Snew, ACO_Sold。實驗結果顯示,GA_Snew較GA_Sold為佳,ACO_Snew較ACO_Sold為佳。本研究也以實驗方式解釋,造成此績效差異之原因。
Meta-heuristic algorithms have been widely used in solving scheduling problems; many prior studies focused on how to enhance existing algorithmic mechanisms. Aside from this traditional track, this research attempts to advocate a new perspective—developing new chromosome (solution) representation schemes might be able to improve the performance of existing meta-heuristic algorithms. Such a research claim is based on experiment findings obtained from solving a scheduling problem, called permutation manufacturing-cell flow shop (PMFS). We compare the effectiveness of two chromosome representation schemes (Sold and Snew) while they are embedded in a particular meta-heuristic algorithm to solve the scheduling problem. Two existing meta-heuristic algorithms, genetic algorithm (GA) and ant colony optimization (ACO), are tested. We herein denote a tested meta-heuristic algorithm by X_Y, where X represents an algorithmic mechanism and Y represents a chromosome representation. Experiment results indicate that the GA_ Snew outperforms GA_Sold, and ACO_Snew also outperforms ACO_Sold. These findings shed a light on the track of developing new chromosome representations in the research of meta-heuristic algorithms.
Gov't Doc #: NSC100-2221-E009-059-MY3
URI: http://hdl.handle.net/11536/98358
Appears in Collections:Research Plans