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

Abstract

本論文探討具維修特性之分散且彈性零工式排程問題(distributed and flexible job shops scheduling problem with maintenance)，在DFJSP問題下考慮機台維修(maintenance)的問題。此排程問題包含四項子決策，分別為(1)工件指派加工的製造單元(job-to-cell assignment)，(2)作業指派加工的機台(operation-to-machine assignment)，(3)決定每個作業的排序(operations sequencing)，(4)機台維修指派(PM decisions)。具維修特性之DFJSP為NP-hard問題，本論文發展出兩種新演算法(簡稱ACO_ Sop-1t 與GA_ Sop-1t)，搭配新染色體表達法(簡稱 Sop-1t)進行求解。本論文主要構想是將機台維修視為一個虛擬作業，因此Sop-1t為一般作業與虛擬維修作業所構成之特定的作業排序。本論文發展兩種啟發式準則(heuristic rules)，可藉此導出此染色體相對應的四項DFJSP子決策。數值實驗結果顯示Sop-1t之績效優於過去文獻所發展的演算法。

This research is concerned with distributed flexible job shop problem subject to maintenance (called the DFJSP/PM problem), which considers the effect of preventive maintenance (PM) in scheduling. The DFJSP/PM problem involves four sub-decisions: (1) job-to-cell assignment, (2) operation-to-machine assignment, (3) operations sequencing, and (4) PM decisions. The complexity of the scheduling problem is NP-hard. This research solves the problem by two meta-heuristic algorithms (called ACO_ Sop-1t and GA_ Sop-1t), based on a new solution representation (called Sop-1t). Sop-1t represents a solution by a sequence of generic operations, where an operation is either a normal operation or a virtual PM operation. Decoding Sop-1t by two heuristic rules, we can obtain the aforementioned four sub-decisions. Experiment results show that ACO_Sop-1t and GA_Sop-1t outperform prior meta-heuristic algorithms in literature.