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

Abstract

本論文探討議題為分散且彈性零工式排程問題(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.