標題: 以作業序二元基因染色體表達法求解具維修特性之DFJSP排程問題
Using OP-Based Chromosomes with 2-tuple Genes to Develop Meta-heuristic Algorithms for DFJSP Scheduling Subject to Maintenance
作者: 李依玲
Lee, I-Ling
巫木誠
Wu, Muh-Cherng
工業工程與管理系所
關鍵字: 分散且彈性零工式生產排程;蟻群最佳化演算法;基因演算法;解表達法;預防維修;Distributed and Flexible Job Shops Scheduling;Ant Colony Optimization;Genetic Algorithm;Solution Representation;Preventive Maintenance
公開日期: 2012
摘要: 本論文探討具維修特性之分散且彈性零工式排程問題(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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070053321
http://hdl.handle.net/11536/71575
Appears in Collections:Thesis