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

Using OP-Based Chromosomes with Maintenance Assignment Heuristics to Develop Meta-heuristic Algorithms for DFJSP Scheduling

郭俊儀(Chun-Yi Kuo)

指導教授 ： 巫木誠

國立交通大學/管理學院/工業工程與管理系所/碩士(2013年)

https://doi.org/10.6842/NCTU.2013.00231

摘要

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).

並列關鍵字

Distributed Flexible Job Shop Scheduling ； Preventive Maintenance ； Ant Colony Optimization ； Genetic Algorithm ； Solution Representation ； Scheduling

參考文獻

2. 何年尉，「以工件序二元基因染色體表達法求解具維修特性之DFJSP排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國102年。

3. 李依玲，「以作業序二元基因染色體表達法求解具維修特性之DFJSP排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國102年。

4. 李奕勳，「以蟻群最佳化演算法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，民國100年。

5. 林佳慧，「以蟻群最佳化演算法搭配作業序表達法求解分散且彈性零工式排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國101年。

7. 范詠婷，「以作業序一元基因染色體表達法求解具維修特性之DFJSP排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國102年。