基因-禁忌演算法搭配新染色體表達法求解彈性零工式排程問題

Abstract

本論文為探討彈性零工式排程問題(flexible job-shop scheduling problem, FJSP)，此問題包括兩項子決策，分別為(1)作業指派(operation-to-machine assignment)，(2)作業排序(Operation Sequencing for Each Machine)。FJSP複雜度為NP-hard，過去研究發展各種不同巨集啟發式演算法(Meta-heuristic Algorithms)來求解。本論文採用基因-禁忌演算法的架構搭配一個新染色體表達法(簡稱Sop)，發展出一演算法(稱為GA-Tabu_Sop)來求解FJSP問題，並以最大完工時間(Makespan)為目標函數。所謂染色體表達法是指解的表達法，Sop表達法表示作業排序；亦即一個染色體就是一個特定的作業排序(A Particular Sequence of Operations)。給定某一染色體(作業排序)，本研究發展數種啟發式演算法(Heuristic Methods)，可藉此導出此染色體相對應的作業指派子決策。

This research is concerned with the scheduling of a flexible job-shop problem (called FJSP), which involves two sub-decisions: (1) assignment of each operation to an appropriate machine, and (2) sequencing all operations assigned to each machine. Most prior studies proposed meta-heuristic algorithms for the FJSP problem. This research proposes a new solution representation (called Sop), which is intended to model a particular sequence for all operations. Given a particular Sop, by proposed heuristic rule, we can obtain its two corresponding sub-decisions; which in turn represents a particular scheduling solution. Based on the Sop representation, this research adopts the architecture of genetic algorithms and Tabu search, and develops a meta-heuristic algorithm (called GA-Tabu_ Sop). Experiment results indicate that GA-Tabu _ Sop performance decline slightly from prior meta-heuristic algorithms in FJSP.