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

Abstract

本論文探討具維修特性之分散且彈性零工式排程問題(distributed flexible job shop scheduling problem, DFJSP)。具維修特性之DFJSP排程問題包含四項決策，分別為(1)工件指派彈性製造單元(job-to-cell assignment)。(2)作業指派機台(operation-to-machine assignment)。(3)作業加工順序(operations sequencing)。(4)機台維修指派(PM decision for each machine)。具維修特性之DFJSP的複雜度為NP-hard，於NP-hard的研究文獻中，過去學者多專注於巨集啟發式演算法(meta-heuristic algorithms)的改善。因此，本論文使用兩種巨集啟發式演算法搭配一新解表達法(簡稱Sop-2t)，Sop-2t是由一序列的作業所排列而成，且維修決策資訊以屬性的方式包含於每個作業中，意思是說，當此作業加工完成後，維修屬性會決定機台當下是否要進行維修。本論文使用蟻群最佳化演算法(ACO)以及基因演算法(GA)發展出兩種新的演算法(分別稱為ACO_Sop-2t、GA_Sop-2t)求解DFJSP。實驗結果顯示ACO_Sop-2t 以及GA_Sop-2t比過去文獻的演算法有更優良的表現。

This research examines a distributed flexible job shops scheduling problem subject to preventive maintenance (called the DFJSP/PM problem), which involves four decisions: (1) job-to-cell assignment, (2) operation-to-machine assignment, (3) operation sequencing, (4) prevent maintenance decision. Prior studies have shown that complexity of the problem is NP-hard. Most prior studies have proposed meta-heuristic algorithms to solve the DFJSP problem. This research proposes two meta-heuristic algorithms bases on a new solution representation (called Sop-2t). Sop-2t represents a solution by a sequence of operations, and PM (preventive maintenance) decision is attribute of an operation. That is, after completing an operation, the PM attribute of the operation is used to determine whether a PM shall be carried out immediately. This research adopts the algorithmic architecture of ant colony optimization (ACO) and genetic algorithms (GA), and develops two meta-heuristic algorithms (called ACO_Sop-2t and GA_Sop-2t) to solve the DFJSP problem. Experiment results show that ACO_Sop-2t and GA_Sop-2t outperform prior meta-heuristic algorithms in literature.