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

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

林佳慧(Chia-Hui Lin)

指導教授 ： 巫木誠

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

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

摘要

本論文探討議題為分散且彈性零工式排程問題(Distributed Flexible Job-Shop Problem, DFJSP)。DFJSP排程問題包含三項子決策，分別為 (1) 工件指派：決定每個工件所要加工的製造單元(job-to-cell assignment)，(2) 作業指派：決定每個作業的加工機台(operation-to-machine assignment)，(3) 作業排序：決定每個加工工件的排序(operations sequencing)。DFJSP排程問題的複雜度已被證明為NP-hard，過去學者多專注於巨集啟發式演算法(meta-heuristic algorithms)的改良。本論文使用蟻群最佳化演算法(ant colony optimization, ACO)的架構搭配一新染色體表達法(簡稱 Sop)，發展出一新演算法(稱為 ACO_Sop)求解DFJSP問題。所謂染色體表達法指的是解的表達法，而Sop表達法的構想是將作業排序；亦即一個染色體就是一個特定的作業排序(a particular sequence of operations)。本論文發展數種啟發式演算法(heuristic methods)，藉此導出該染色體 (作業排序)相對應的三項DFJSP子決策。實驗結果顯示ACO_Sop比過去研究有更優良的表現。

關鍵字

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

並列摘要

This research is concerned with the scheduling of a distributed flexible job-shop problem (called DFJSP), which involves three sub-decisions: (1) assignment of each job to an appropriate manufacturing cell, (2) assignment of each operation to an appropriate machine, and (3) sequencing all operations assigned to each machine. Most prior studies proposed meta-heuristic algorithms for the DFJSP problem. This research proposes a new solution representation (called Sop), which is intended to model a particular sequence for all operations. Given a particular Sop, by some heuristic rules, we can obtain its three corresponding sub-decisions; which in turn represents a particular scheduling solution. Based on the Sop representation, this research adopts the architecture of ant colony optimization (ACO) algorithms, and develops a meta-heuristic algorithm (called ACO_ Sop). Experiment results indicate that ACO_ Sop out performs prior meta-heuristic algorithms.

並列關鍵字

Distributed Flexible Job Shop Scheduling ； Ant Colony Optimization ； Solution Representation ； Scheduling

參考文獻

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

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

Chan, F.T.S., Chung, S.H. and Chan, P.L.Y. (2006b). 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.

Carlier, J. and Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35, 164–176.

Garey, M.R., Johnson, D.S. and Sethi, R. (1976). The complexity of flow shop and job-shop scheduling. Mathematics of Operations Research, 1:2, 117-129.