以三階基因演算法搭配作業序表達法求解彈性零工式排程問題

Abstract

本論文主要在探討彈性零工式排程問題(flexible job-shop scheduling problem, FJSP)，FJSP排程問題包括兩項子決策，分別為(1)作業的機台指派(operation-to-machine assignment)，(2)機台前的作業加工順序(operation sequencing for each machine)。FJSP問題的複雜度已被證明是NP-hard，過去研究發展各種不同巨集啟發式演算法(meta-heuristic algorithms)來求解。本論文採用基因演算法(genetic algorithm；GA)的架構搭配作業序表達法，為一個新的染色體表達法(簡稱Sop)，發展出一新演算法(稱為GA_Sop)來求解FJSP問題。所謂染色體表達法是指解的表達法，Sop表達法的構想是將作業排序；亦即一個染色體就是一個特定的作業排序(a particular sequence of operations)。在給定某一染色體(作業排序)的條件下，本研究發展數種啟發式演算法(heuristic methods)，可藉此導出此染色體相對應的作業指派子決策。本研究是以最大完工時間(makespan)為目標函數。

This research is concerned with the scheduling of a flexible job-shop problem (called FJSP), which involves two sub-decisions: (1) operation-to-machine assignment (2) operation sequencing for 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 some heuristic rules, 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 existing architecture of genetic algorithm (GA) and develops a meta-heuristic algorithm (called GA_ Sop) to solve the FJSP problem.