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

Abstract

本篇論文主要在探討分散且彈性的零工式排程問題 (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.