臺灣博碩士論文加值系統

本論文欲求解的問題是具維修特性之DFJSP排程問題。具維修特性之DFJSP排程問題有四項子決策，分別為(1)工件指派，(2)作業指派，(3)作業排序，(4)維修決策。具維修特性之DFJSP排程問題的時間複雜度為NP-hard，故本論文以巨集式啟發式演算法中的蟻群最佳化演算法(ant colony optimization, ACO)與基因演算法(genetic algorithm, GA)的架構為基礎，搭配一個新染色體表達法(簡稱 Sjob-2t)，發展新演算法(簡稱 ACO_Sjob-2t 與 GA_ Sjob-2t) 進行求解。Sjob-2t染色體表達法是指解的表達方式，主要構想是一條染色體由長度為工件數量的二元基因排序組成，二元資訊包含工件編號以及工件內作業結束後機台需維修的次數。給定一條Sjob-2t染色體，本論文發展四種啟發式演算法(heuristic methods)，可藉此解碼Sjob-2t染色體得到具維修特性之DFJSP的四項子決策資訊。本論文的目標函數為全域最大完工時間(global makespan)，實驗數據顯示ACO_Sjob-2t與 GA_ Sjob-2t在多數例題中績效優於過去學者提出的演算法。

This thesis addresses the problem of scheduling distributed and flexible job shop subject to preventive maintenance (called the DFJSP/PM scheduling problem) which is composed of four decisions: (1) job to cell assignment (2) operation to machine assignment (3) operation sequencing (4) prevent maintenance decision. The DFJSP/PM scheduling problem is NP-hard. Based on a proposed solution representation (called Sjob-2t), we develop two meta-heuristic algorithms (an ant colony optimization algorithm and a genetic algorithm). Sjob-2t represents a solution (also called a chromosome) by a sequence of jobs, and four heuristics are developed to decode the chromosome in order to obtain the aforementioned four decisions of the DFJSP/PM scheduling problem. The scheduling objective is to minimize the global makespan. Experimental results show that proposed two algorithms both outperform the state-of-art study reported in literature.

中文摘要 ii
Abstract iii
誌謝 iv
目錄 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 研究背景 1
1.2 研究構想 3
1.3 研究方法 4
1.4 論文架構 5
第二章 文獻探討 6
2.1 排程環境 6
2.2 解的表達法 9
2.3 蟻群最佳化演算法 10
2.4 基因演算法 12
第三章 研究問題與新舊解表達法 15
3.1 研究問題 15
3.2 研究假設 19
3.3 新舊解表達法 20
3.3.1 舊解表達法(Sold) 20
3.3.2 新解表達法(Sjob-2t) 21
3.3 計算目標值 22
第四章 巨集啟發式演算法搭配Sjob-2t 23
4.1解碼Sjob-2t染色體表達法 23
4.1.1 Sjob-2t解碼流程 24
4.1.2工件指派法則(H1_Heuristic) 25
4.1.3作業排序法則(S1_Heuristic) 27
4.1.4作業指派法則(R1_Heuristic) 28
4.1.5維修決策法則(M1_Heuristic) 29
4.2巨集啟發式演算法架構 31
4.2.1 ACO_Sjob-2t演算法架構 31
4.2.2 GA_Sjob-2t演算法架構 32
4.3部分進化機制 33
4.4巨集啟發式演算法搭配Sjob-2t求解過程 36
4.4.1 ACO_Sjob-2t求解過程 36
4.4.2 GA_Sjob-2t求解過程 40
第五章 實驗情境與結果 45
5.1實驗情境 45
5.2蟻群最佳化演算法實驗結果 48
5.2.1 ACO_Sjob-2t (N = 5000) 48
5.2.2 ACO_Sjob-2t (B = 500) 50
5.3基因演算法實驗結果 52
5.3.1 GA_Sjob-2t (N = 5000) 52
5.3.2 GA_Sjob-2t (B = 500) 54
5.4與其他現行研究比較 56
第六章 結論與未來研究方向 59
6.1結論 59
6.1.1研究問題 59
6.1.2研究創意 59
6.2未來研究方向 60
參考文獻 61

Belaid, R., T’kindt, V., &; Esswein, C. (2012). Scheduling batches in flowshop with limited buffers in the shampoo industry. European Journal of Operational Research, 223, 560-572.
Chan, F. T. S., Chung, S. H., &; Chan, P. L. Y. (2006a). Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems. International Journal of Production Research, 44(3), 523-543.
Chung, S. H., Chan, F. T., &; Chan, H. K. (2009). A modified genetic algorithm approach for scheduling of perfect maintenance in distributed production scheduling. Engineering Applications of Artificial Intelligence, 22(7), 1005-1014.
Chan, F. T., Chung, S. H., Chan, L. Y., Finke, G., &; Tiwari, M. K. (2006b). Solving distributed FMS scheduling problems subject to maintenance: genetic algorithms approach. Robotics and Computer-Integrated Manufacturing, 22(5), 493-504.
Chen, C. F., Wu, M. C., Li, Y. H., Tai, P. H., &; Chiou, C. W. (2013). A comparison of two chromosome representation schemes used in solving a family-based scheduling problem. Robotics and Computer-Integrated Manufacturing, 29(3), 21-30.
Dorigo, M., Maniezzo, V., &; Colorni, A. (1991). The ant system: An autocatalytic optimizing process. TR91-016, Politecnico di Milano.
Dorigo, M., Maniezzo, V., &; Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 26(1), 29-41.
De Giovanni, L., &; Pezzella, F. (2010). An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. European journal of operational research, 200(2), 395-408.
Girish, B. S., &; Jawahar, N. (2009). Scheduling job shop associated with multiple routings with genetic and ant colony heuristics. International journal of production research, 47(14), 3891-3917.
Garey, M. R., Johnson, D. S., &; Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117-129.
Gonçalves, J. F., de Magalhães Mendes, J. J., &; Resende, M. G. (2005). A hybrid genetic algorithm for the job shop scheduling problem. European journal of operational research, 167(1), 77-95.
Gao, J., Sun, L., &; Gen, M. (2008). A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers &; Operations Research, 35(9), 2892-2907.
Huang, K. L., &; Liao, C. J. (2008). Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers &; Operations Research, 35(4), 1030-1046.
Huang, R. H., Yang, C. L., &; Cheng, W. C. (2013). Flexible job shop scheduling with due window─ A two-pheromone ant colony approach.International Journal of Production Economics, 141, 685-697.
Liaw, C. F. (2000). A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research, 124(1), 28-42
Lee, C. Y., Piramuthu, S., &; Tsai, Y. K. (1997). Job shop scheduling with a genetic algorithm and machine learning. International Journal of Production Research, 35(4), 1171-1191.

Mattfeld, D. C., &; Bierwirth, C. (2004). An efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research, 155(3), 616-630.
Pezzella, F., &; Merelli, E. (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120(2), 297-310.
Pezzella, F., Morganti, G., &; Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers &; Operations Research,35(10), 3202-3212.
Ruiz, R., &; Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 169(3), 781-800.
Sha, D. Y., &; Hsu, C. Y. (2006). A hybrid particle swarm optimization for job shop scheduling problem. Computers &; Industrial Engineering, 51(4), 791-808.
Zhang, G., Shao, X., Li, P., &; Gao, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem.Computers &; Industrial Engineering, 56(4), 1309-1318.
李依玲，「以作業序二元基因染色體表達法求解具維修特性之DFJSP排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國102年。
李奕勳，「以蟻群最佳化演算法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，民國100年。
林佳慧，「以蟻群最佳化演算法搭配作業序表達法求解分散且彈性零工式排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國101年。
林耿漢，「以塔布搜尋法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，民國100年。
范詠婷，「以作業序一元基因染色體表達法求解具維修特性之DFJSP排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國102年。
徐千雯，「基因-禁忌演算法搭配新染色體表達法求解彈性零工式排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國101年。
陳威宇，「以粒子群演算法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，民國100年。
郭俊儀，「以作業序染色體表達法結合維修指派法則求解DFJSP排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國102年。
張慕萱，「以工件序一元基因染色體表達法求解具維修特性之DFJSP排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國102年。
彭勇漢，「以基因演算法搭配工件順序的表達法求解分散且彈性零工式排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國101年。
黃建翰，「以三階基因演算法搭配作業序表達法求解彈性零工式排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國101年。
曾偉杰，「以模擬退火法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，民國100年。
潘冠銘，「以瀰集演算法求解流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，民國100年。
賴佳卉，「以三階粒子群最佳化演算法搭配作業序表達法求解彈性零工式排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國101年。
戴邦豪，「應用混合式染色體表達法於具順序相依家族整備時間之流線型製造單元排程」，國立交通大學工業工程與管理學系，碩士論文，民國99年。
譚浩，「以蟻群最佳化演算法搭配工件序表達法求解分散且彈性零工式排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國101年。