以不同染色體表達法用基因演算法求解DFJS排程問題

Abstract

本研究使用SOP染色體表達法(chromosome representations)搭配GA_OP演算法求解分散且彈性的零工式排程(distributed flexible job shop scheduling, DFJS)問題，並比較不同染色體表達法對解品質的影響。過去許多研究都使用基因演算法(genetic algorithm, GA)求解DFJS問題，而此問題已被證明是NP-hard問題。過去研究提出求解DFJS問題的改善方法，多半使用相似的GA演算法流程，但搭配不同的染色體表達法。依循這樣的思路發展，本研究提出一種新的SOP染色體表達法搭配GA_OP基因演算法來求解DFJS問題。實驗結果發現，GA_OP演算法的解品質比過去研究中演算法的績效好。由此結果，我們可以推論在求解高維空間搜尋問題時，建構適合的染色體表達法搭配基因演算法來解空間搜尋問題是很重要的。

This paper proposes SOP chromosome representation and develops GA_OP genetic algorithm to solve the DFJS problem. We attempt to compare the effect of using different chromosome representations while developing a genetic algorithm to solve a scheduling problem called DFJS (distributed flexible job shop scheduling) problem. The DFJS problem is strongly NP-hard; most recent prior studies develop various genetic algorithms (GAs) to solve the problems. These prior GAs are similar in the algorithmic flows, but are different in proposing different chromosome representations. Extending from this line, this research proposes a new chromosome representation (called SOP) and develops a genetic algorithm (called GA_OP) to solve the DFJS problem. Experiment results indicate that GA_OP outperforms all prior genetic algorithms. This research advocates the importance of developing appropriate chromosome representations while applying genetic algorithms (or other meta-heuristic algorithms) to solve a space search problem, in particular when the solution space is high-dimensional.