粒子群演算法於多目標排程問題之研究

A Study of Particle Swarm Optimization for Multi-objective Production Scheduling Problems

林信宏(Hsing-Hung Lin)

指導教授 ： 沙永傑 ； 洪瑞雲

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

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

摘要

以往學術上排程問題的研究主流是尋找單一目標的最佳解(如: 最小完工時間) ，然而，實務上生產製造系統的排程需求是達成多目標最佳化。由於運算時間與成本的考量，過去的許多研究已經發展出許多演算法則以搜尋最佳解或近似最佳解。
在本篇論文中，我們分別提出適合求解流程型排程問題(Flow Shop Scheduling Problem, FSSP)、零工型排程問題(Job Shop Scheduling Problem, JSSP)與開放型排程問題(Open Shop Scheduling Problem, OSSP)的粒子群最佳化演算法(Particle Swarm Optimization, PSO)。本研究所提出的演算法針對三種典型排程問題，以同時達到最小完工時間(Makespan)、總流程時間(Total flow time)與機器閒置時間(Machine idle time)作為目標。
粒子群演算法是一種群體搜尋最佳化演算法，於1995年被提出。原始的PSO是應用於求解連續最佳化問題。因為排程問題為一離散最佳化問題，我們必須修改粒子位置、粒子移動以及粒子速度的表達方式，讓PSO更適於求解排程問題。
對於FSSP與JSSP，本研究比較PSO與文獻中的基因演算法(Genetic Algorithm, GA)搜尋三大目標的結果，顯示本文提出的PSO優於基因演算法。本研究另行發展求解多目標OSSP的基因演算法並與PSO進行Benchmark問題的比較，計算結果顯示，修改後的PSO所搜尋到的解，在品質與效率上優於基因演算法。

關鍵字

粒子群最佳化 ； 流程型排程 ； 零工型排程 ； 開放型排程 ； 啟發式演算法

並列摘要

The academic approach of discovering the single optimal solution (ex. makespan) of scheduling for production system is the mainstream although the empirical requirement of production system is to achieve multi-objective optimization. Many algorithms have been developed to search for optimal or near-optimal solutions due to the computational cost of determining exact solutions.
This study provides a Particle Swarm Optimization (PSO) to elaborate multi-objective flow shop scheduling problem (FSSP), job shop scheduling problem (JSSP) and open shop scheduling problem (OSSP). The proposed evolutionary algorithm searches the optimal solution for objectives by considering the makespan, total flow time, and machine idle time simultaneously.
Particle Swarm Optimization (PSO) is a population-based optimization algorithm, which was developed in 1995. The original PSO is used to solve continuous optimization problems. Due to the discrete solution spaces of scheduling optimization problems, the authors modified the particle position representation, particle movement, and particle velocity in this study. The modified PSO could be applied for solving various benchmark problems; moreover, the results demonstrated that the modified PSO outperformed traditional evolutionary heuristics – Genetic Algorithm in searching quality and efficiency.

並列關鍵字

Particle swarm optimization ； Flow shop scheduling ； Job shop scheduling ； Open shop scheduling ； Heuristic

參考文獻

Bean, J. (1994). Genetic algorithms and random keys for sequencing and optimization. Operations Research Society of America (ORSA) Journal on Computing, 6, 154–160.

Bllzewicz J., Pesch E., Sterna M., Werner F. (2004). Open shop scheduling problems with late work criteria. Discrete Applied Mathematics, 134 (1-3), 1-24.

Blum C. (2005). Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers & Operations Research, 32, 1565–1591.

Campbell H.G., Dudek R.A. & Smith M.L. (1970). A heuristic algorithm for the n-job m,_machine sequencing problem. Management Science, 16, B630–B637.

Candido M. A. B., S. K. Khator & R.M. Barcia. (1998). A genetic algorithm based rocedre for more realistic job shop scheduling problems. International Journal of Production Research, 36(12), 3437-3457.