以進化搜尋演算法求解流線群組排程問題

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.