以蟻群最佳化演算法搭配工件序表達法求解分散且彈性零工式排程問題

An ACO Algorithm with a Job-Sequence-Based Chromosome Representation for Scheduling Distributed Flexible Job Shops

譚浩(Tan, Hao)

指導教授 ： 巫木誠

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

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

摘要

本篇論文主要在探討分散且彈性的零工式排程問題 (Distributed Flexible Job Shop Scheduling Problem, DFJSP) 。DFJSP包括有三項子決策，分別為 (1) 工件指派：工件該如何指派至各製造單元， (2) 作業排序：各工件的作業該如何排序， (3) 作業指派：各作業該指派到哪一個加工機台。DFJSP問題的複雜度已被證明是NP-hard，過去研究通常發展巨集啟發式演算法 (meta-heuristic algorithms) 來求解。本論文延用蟻群最佳化演算法 (ant colony optimization, ACO) 的架構，但結合一個新的染色體表達法 (簡稱 Sjob)，發展出一新演算法 (稱為 ACO_Sjob) 來求解DFJSP問題。所謂染色體表達法是指解的表達法，Sjob表達法的構想是將工件排序；亦即一個染色體就是一個特定的工件排序 (a particular sequence of jobs) 。給定某一染色體 (工件排序) ，本研究發展數種啟發式演算法 (heuristic methods) ，可藉此導出此染色體相對應的三項DFJSP子決策。本研究是以全域最大完工時間 (global makespan) 為目標函數，數值實驗結果顯示ACO_Sjob的績效優於過去文獻所發展的演算法

關鍵字

分散且彈性零工式排程問題、蟻群最佳化演算法、巨集啟發式演算法

並列摘要

This research examines a distributed and flexible job shops scheduling problem (DFJSP). With NP-hard in complexity, the DFJSP problem involves three sub-decisions: (1) job-to-cell assignment, (2) operation sequencing, and (3) operation-to-machine assignment. Several meta-heuristic algorithms have been proposed to solve the DFJSP problem. This research develops a new solution representation (called Sjob), which is for modeling a particular sequence of jobs. Given such a job sequence, heuristic rules are used to derive the three scheduling sub-decisions. Based on Snew, this research adopts the existing algorithmic architecture of ant colony optimization (ACO) and developed an algorithm (called ACO_Sjob) to solve the DFJSP problem. Experiment results indicate that ACO_Sjob outperforms prior meta-heuristic algorithms in literature.

並列關鍵字

Distributed and Flexible Job Shops Scheduling, Ant Colony Optimization, Meta-heuristic Algorithms.

參考文獻

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

Chan, F.T.S., Chung, S.H., and Chan,P.L.Y., 2006b, Application of genetic algorithm with dominated genes in a distributed scheduling problem in flexible manufacturing. International Journal of Production Research, 44(3), 523-543.

Chan, F.T.S., Chung, S.H., Chan, L.Y., Finke, G., and Tiwari , M.K., 2006a, Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach. Robotics and Computer-Integrated Manufacturing, 22, 493-504.

Chen, H., Ihlow, J., and Lehmann, C., 2004, A genetic algorithm for flexible job-shop scheduling, IEEE,1120-1125.

Choi, I.C., and Choi, D.S., 2002. A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups. Computers & Industrial Engineering, 42, 791-808.