以工件序二元基因染色體表達法求解具維修特性之DFJSP排程問題

Abstract

本論文欲求解的問題是具維修特性之DFJSP排程問題。具維修特性之DFJSP排程問題有四項子決策，分別為(1)工件指派，(2)作業指派，(3)作業排序，(4)維修決策。具維修特性之DFJSP排程問題的時間複雜度為NP-hard，故本論文以巨集式啟發式演算法中的蟻群最佳化演算法(ant colony optimization, ACO)與基因演算法(genetic algorithm, GA)的架構為基礎，搭配一個新染色體表達法(簡稱 Sjob-2t)，發展新演算法(簡稱 ACO_Sjob-2t 與 GA_ Sjob-2t) 進行求解。Sjob-2t染色體表達法是指解的表達方式，主要構想是一條染色體由長度為工件數量的二元基因排序組成，二元資訊包含工件編號以及工件內作業結束後機台需維修的次數。給定一條Sjob-2t染色體，本論文發展四種啟發式演算法(heuristic methods)，可藉此解碼Sjob-2t染色體得到具維修特性之DFJSP的四項子決策資訊。本論文的目標函數為全域最大完工時間(global makespan)，實驗數據顯示ACO_Sjob-2t與 GA_ Sjob-2t在多數例題中績效優於過去學者提出的演算法。

This thesis addresses the problem of scheduling distributed and flexible job shop subject to preventive maintenance (called the DFJSP/PM scheduling problem) which is composed of four decisions: (1) job to cell assignment (2) operation to machine assignment (3) operation sequencing (4) prevent maintenance decision. The DFJSP/PM scheduling problem is NP-hard. Based on a proposed solution representation (called Sjob-2t), we develop two meta-heuristic algorithms (an ant colony optimization algorithm and a genetic algorithm). Sjob-2t represents a solution (also called a chromosome) by a sequence of jobs, and four heuristics are developed to decode the chromosome in order to obtain the aforementioned four decisions of the DFJSP/PM scheduling problem. The scheduling objective is to minimize the global makespan. Experimental results show that proposed two algorithms both outperform the state-of-art study reported in literature.