以作業序染色體表達法結合維修指派法則求解DFJSP排程問題

Abstract

DFJSP/PM(distributed flexible job shop problem with preventive maintenance) 為近年來被提出的分散且彈性零工式排程問題。該問題的求解包含四項子決策，依序為 (1) 工件指派：將每個工件指派給執行加工的製造單元(job-to-cell assignment)；(2) 作業指派：對完成工件指派後的工件之所屬作業，決定其加工的機臺(operation-to-machine assignment)；(3) 作業程序指派：決定所有作業的加工先後順序(operations sequencing)；(4)決定各作業完成後，其加工機臺是否進行維修。本論文將維修指派部分模組化，藉由”不回饋、變更原工件、作業指派演算法”之設計，使研究成果能適用於所有DFJSP演算法上，達到高可攜性、可移植性，低開發成本，為本研究之特點。本論文分別採用林佳慧與林季煖(2012)提出之蟻群演算法、基因演算法搭配作業序染色體表達法的求解DFJSP問題。經國外文獻提供之範例進行模擬比較，數據顯示本論文提出的方法在求解後，其最短全域加工時間顯著低於目前表現最佳之已發表文獻(S.H. Chung, 2009)，其勝出比例可達到40%。此外，本論文也同時與其他同步發展的四個優於S.H. Chung (2009)之演算法分別進行比較，並於多項實驗情境中勝出。

This thesis addresses a DFJSP/PM (a distributed flexible job shop with preventive maintenance) scheduling problem. That is, the scheduling context involves numerous FMUs (flexible manufacturing units), where each FMU is a flexible job shop problem (FJSP) and the timing decisions for carrying out preventive maintenance on each machine have to be considered. Having been proved as NP-hard, the scheduling problem involves four sub-decisions: (1) assigning each job to an FMU, (2) assigning each operation to a machine, (3) sequencing the operations assigned to each machine, and (4) determining when to carry out preventive maintenance (PM) on each machine. The objective is to minimize the global makespan, the time horizon required to finish all the jobs to be scheduled. Adopting the solution representation scheme developed C.H. Lin and C.S. Lin (2012), this thesis develops two meta-heuristic algorithms (called ACO_Snew and GA_Snew) to solves the DFJSP/PM scheduling problem. Experiment results reveal that ACO_Snew and GA_Snew significantly outperform the state-of-art algorithm (S.H. Chung 2009) in solving the DFJSP/PM problem; about 40% better off in solution quality. Noticeably, ACO_Snew and GA_Snew also outperform four other currently undergoing studies, which empirically appear to be superior to the state-of-art algorithm (S.H. Chung 2009).