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

A Three-Phase PSO Algorithm with an Operation-Sequence-Based Chromosome Representation for Scheduling Flexible Job Shops

賴佳卉(Chia-Hui Lai)

指導教授 ： 巫木誠

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

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

摘要

本論文研究議題為彈性零工式排程問題(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.

並列關鍵字

flexible job-shop scheduling problem ； particle swarm optimization algorithm ； meta-heuristic algorithms ； solution representation

參考文獻

林耿漢，「以塔布搜尋法求解流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2011。

陳威宇，「以粒子群演算法求解流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2011。

戴邦豪，「應用混合式染色體表達法於具順序相依家族整備時間之流線型製造單元排程」，國立交通大學工業工程與管理學系碩士論文，2010。

Brucker, P., and Schlie, R., 1990. Job-shop scheduling with multi-purpose machines. Computing, 45, 369-375.

Brandimarte, P., 1993. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41, 157-183.