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

Abstract

本論文探討議題為具維修特性之分散且彈性零工式排程問題。此排程問題的複雜度為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.