以三階粒子群最佳化演算法搭配作業序表達法解彈性零工式排程問題

Abstract

本論文研究議題為彈性零工式排程問題(Flexible Job-shop Scheduling Problem, FJSP)。FJSP包含兩項子決策：(1)作業指派(operation-to-machine assignment)，(2)作業排序(operation sequencing for each machine)。過去研究已證明FJSP的複雜度為NP-hard，以往學者透過發展各種不同巨集啟發式演算法(meta-heuristic algorithms)來求解。本論文以粒子群最佳化演算法(Particle Swarm Optimization, PSO)的架構搭配一個新的染色體表達法(簡稱Sop)，發展出一新的三階演算法(稱為PSO_Sop)來求解FJSP。染色體表達法即是指解的表達法，Sop表達法的概念是排序所有作業，即一條染色體就是一組特定的作業排序(a particular sequence of operations)。本論文提出啟發式規則(heuristic rule)，藉此導出作業排序染色體其相對應的作業指派子決策。本論文求解目標為最小化最大完工時間(makespan)。

This research is concerned with the scheduling of a flexible job-shop problem (called FJSP), which involves two sub-decisions: (1) operation-to-machine assignment (2) operation sequencing for each machine. Most prior studies proposed meta-heuristic algorithms for the FJSP 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 a heuristic rule, we can obtain its two corresponding sub-decisions; which in turn represents a particular scheduling solution. Based on the Sop representation, this research adopts the existing architecture of particle swarm optimization (PSO) algorithm and develops a three phases meta-heuristic algorithm (called PSO_ Sop) to solve the FJSP problem.