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

Using job-based chromosomes with 1-tuple genes to develop meta-heuristic algorithms for DFJSP scheduling subject to maintenance

張慕萱(Mu-Hsuan Chang)

指導教授 ： 巫木誠

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

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

摘要

本論文探討議題為具維修特性之分散且彈性零工式排程問題。此排程問題的複雜度為NP-hard，包含四項子決策，分別為 (1) 工件指派，(2) 作業指派，(3)作業排序，(4) 維修決策。本論文發展兩個啟發式演算法搭配一新解表達(簡稱Sjob-1t)來求解此排程問題。Sjob-1t為工件及虛擬維修工件的排序，意即一個染色體就是一個特定的工件排序(a particular sequence of jobs)。並且發展四種啟發式演算法(heuristic methods)求解具維修特性之分散且彈性零工式排程問題的四項子決策。本研究是以全域最大完工時間(global makespan)為目標函數，實驗結果顯示本研究所提出的兩個演算法在多數例題中，績效優於文獻所發展的演算法。

關鍵字

分散且彈性零工式生產排程 ； 蟻群最佳化演算法 ； 基因演算法 ； 解表達法 ； 預先維修

並列摘要

This thesis aims at solve the problem of distributed flexible job-shop subject to preventive maintenance (i.e., the DFJSP/PM problem). This scheduling problem is NP-hard, which contains four sub-decisions: (1) job-to-cell assignment, (2) operation-to-machine, (3) operation sequencing, and (4) preventive maintenance assignment. To solve this scheduling problem, this thesis develops two meta-heuristic algorithms based on a new solution representation (called Sjob-1t). Sjob-1t represents a solution by a sequence of generic jobs, which is composed of normal jobs and virtual PM jobs. Four heuristic rules are developed to decode the sequence of generic jobs to obtain the aforementioned four sub-decisions. The scheduling objecive is global makespan. Experiment results show that the two proposed algorithms both outperform prior algorithms in solving the DFJSP/PM problem.

並列關鍵字

Distributed flexible job-shop ； Ant colony algorithm ； Genetic algorithm ； Solution representation ； Prevent maintenance

參考文獻

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

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

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

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

林耿漢，「以塔布搜尋法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，民國100年。