以兩種染色體表達法求解具工件族特性之排程問題

A Comparison of Two Chromosome Representation Schemes Used in Solving a Family-Based Scheduling Problem

陳振富(Chen-Fu Chen)

指導教授 ： 巫木誠

國立交通大學/管理學院/工業工程與管理系所/博士(2012年)

https://doi.org/10.6842/NCTU.2012.00758

摘要

本篇論文探討在運用進化演算法(meta-heuristic algorithms)搭配新的解表達法(solution representation)時的影響性。本研究以一個流線型製造單元系統(PMFS; permutation manufacturing-cell flow shop scheduling problem)的排程問題為研究範疇來討論此影響性。上述排程問題，過去研究都使用同一解表達法（簡稱Sold），本研究提出一個新的解表達法(簡稱Snew)，戴邦豪(2010)、林耿漢(2011)與李奕勳(2011)分別應用Snew於基因演算法(genetic algorithm)、禁忌搜尋演算法(tabu search)與蟻群最佳化演算法(ant colony optimization)。本研究的第一個重點將探討為何Snew比採用Sold的解品質好之原因分析。透過數據的分析，可以獲得以下的結果。在禁忌搜尋演算法中Sold有較高的機率會陷入「迴圈」之中。在基因演算法與蟻群最佳化演算法中， Sold容易在解的特定決策參數上陷入「同質化」現象；而此現象導致其進化過程無法再搜尋到更好的解。本研究的第二個重點是討論同時改善進化演算法（混用基因演算法與禁忌搜尋演算法)與改善解表達法(採用Snew)對解品質的影響，實驗結果顯示兼採此兩種方法，解的品質的改善效果會比只採單一方法更好。本研究的主要貢獻是證實改善解表達法(solution representation) 對進化演算法的重要性，此概念可進一步延伸到進化演算法的相關應用。

關鍵字

進化演算法 ； 禁忌搜尋法 ； 基因演算法 ； 解表達法 ； 解表達法 ； 排程

並列摘要

This dissertation examines the effect of using new solution representation in the application of meta-heuristic algorithms. The effect is justified by solving a scheduling problem, called permutation manufacturing-cell flow shop scheduling problem (PMFS). Most prior studies on PMFS used a common solution representation (called Sold); we propose a new one (called Snew). Based on experiments (Tai 2010, Lin 2011, Li 2011), Snew appears to outperform Sold while the two representations are embedded in tabu search, genetic algorithm (GA), and ant colony optimization (ACO). This dissertation attempts to explain why Snew outperforms Sold in these three algorithms. Through empirical analyses, the following findings are obtained. In the tabu algorithms, Sold tends to have a higher probability of being trapped into a loop. In the GA and ACO algorithms, Sold tends to result in a homogeneous set of solutions for some critical scheduling decisions, and reduces the probability of getting better solutions. This dissertation also proposed a new algorithm GA_Tabu_Snew, which outperforms all prior algorithms in solving the PMFS problem.

並列關鍵字

Meta-heuristic algorithms ； Tabu search ； Genetic Algorithm ； Ant colony Optimization ； Solution Representation ； Scheduling

參考文獻

林耿漢，「以塔布搜尋法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，2011。

李奕勳，「以蟻群最佳化演算法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，2011。

Chan, F.T.S., Choy, K.L., Bibhushan, A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop. Expert Systems with Applications; 2011; 38: 8703-8715.

Chang, P.C., Chen, S.H., Fan, C.Y., Mani, V., Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems. Annals of Operations Research; 2008: 1-15.

Chen, C.F., Wu M.C., Li Y.H., Tai P.H., Chiou C.W., A comparison of two chromosome representation schemes used in solving a family-based scheduling problem. Robotics and Computer-Integrated Manufacturing; 2012: doi:10.1016/j.rcim.2012.04.009.