以基因演算法搭配工件順序的表達法求解分散且彈性零工式排程問題

Abstract

本篇論文主要在探討分散且彈性的零工式排程問題(Distributed Flexible Job Shop Scheduling Problem，DFJSP)。DFJSP排程問題包括有三項子決策，分別為 (1) 工件指派：工件如何指派到各製造單元，(2) 作業指派：各作業如何指派到哪一個加工機台，(3)作業排序：各工件的作業如何排序。DFJSP問題的複雜度已被證明是NP-hard，過去研究通常發展巨集啟發式演算法(Meta-Heuristic Algorithms)來求解。本論文延用基因演算法(Genetic Algorithm，GA)的架構，但結合一個新的染色體表達法(簡稱Sjob)，發展出一新演算法(稱為GA_Sjob)來求解DFJSP問題。所謂染色體表達法是指解的表達法，Sjob表達法的構想是將工件排序；亦即一個染色體就是一個特定的工件排序(a Particular Sequence of Jobs)。給定某一染色體（工件排序)，本研究發展數種啟發式演算法(Heuristic Methods)，可藉此導出此染色體相對應的三項DFJSP子決策。本研究是以最小化最全域最大完工時間(global makespan)為目標函數，數值實驗結果顯示GA_Sjob的績效優於過去文獻所發展的演算法。

This thesis investigates a distributed and flexible job shops scheduling problem (DFJSP), which is NP-hard in complexity. The DFJSP problem involves three sub-decisions: (1) job-to-cell assignment, (2) operation-to-machine assignment, and (3) operation sequencing for each machine. Prior studies have developed several meta-heuristic algorithms to solve the DFJSP problem. This research proposes a new chromosome representation (called Sjob), which is designed to model a sequence of jobs. Given such a job sequence, heuristic rules are then used to determine the three scheduling sub-decisions. Sjob chromosome thus represents a DFJSP solution. Based on Sjob, this research adopts the existing architecture of genetic algorithms (GA) and developed an algorithm (called GA_Sjob) to solve the DFJSP problem. Experiment results indicate that GA_Sjob outperforms prior algorithms in literature.