以基因演算法搭配工件順序的表達法求解分散且彈性零工式排程問題

A Genetic Algorithm With Job-Sequence-Based Chromosome Representation for Scheduling Distributed Flexible Job Shops

彭勇漢(Yong-Han Peng)

指導教授 ： 巫木誠

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

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

摘要

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

關鍵字

分散且彈性零工式排程問題 ； 基因演算法 ； 啟發式演算法

並列摘要

This thesis investigates a distributed and flexible job shops scheduling problem (DFJSP), which is NP-hard in complexity. The DFJSP problem involves three sub-decisions: (1) job-to-cell assignment, (2) operation-to-machine assignment, and (3) operation sequencing for each machine. Prior studies have developed several meta-heuristic algorithms to solve the DFJSP problem. This research proposes a new chromosome representation (called Sjob), which is designed to model a sequence of jobs. Given such a job sequence, heuristic rules are then used to determine the three scheduling sub-decisions. Sjob chromosome thus represents a DFJSP solution. Based on Sjob, this research adopts the existing architecture of genetic algorithms (GA) and developed an algorithm (called GA_Sjob) to solve the DFJSP problem. Experiment results indicate that GA_Sjob outperforms prior algorithms in literature.

並列關鍵字

Distributed and Flexible Job Shops Scheduling ； Genetic Algorithm ； Meta-heuristic Algorithms

參考文獻

1)A. Baykasoglu, Linguistic-based meta-heuristic optimization model for flexible job shop scheduling, International Journal of Production Research 40 (17)(2002) 4523–4543.

2)F. Pezzella, G. Morganti, G. Ciaschetti, A genetic algorithm for the flexible job shop scheduling problem, Computers and Operations Research 35 (2008)3202–3212.

3)F.T.S. Chan, S.H. Chung, P.L.Y. Chan, An adaptive genetic algorithm with dominated genes for distributed scheduling problems, Expert Systems with Applications 29 (2005) 364–371.

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

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