整合粒子群最佳化與蜂群演算法求解彈性零工式生產排程問題之研究

Integrating Particle Swarm Optimization and Honey-bee Mating Optimization for Flexible Job Shop Scheduling Problem

賴阮明(Juan-Ming Lai)

指導教授 ： 邱垂昱

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2009年)

摘要

大部份排程問題都是非常複雜的組合最佳化問題(combinatorial optimization problems)，並且難以去求解。零工式生產排程問題(Job-Shop Scheduling Problem, JSP)則是屬於此問題之一。在文獻中，越來越多的學者使用不同的啟發式演算法去求解組合最佳化方面的問題，常見的有模擬退火法(Simulated Annealing, SA)、遺傳演算法(Genetic Algorithm)、塔布搜尋法(Tabu Search Approach)、蟻群最佳化演算法(Ant Colony Optimization, ACO)及粒子群最佳化 (Particle Swarm Optimization, PSO)等等。
隨著科技的日新月異，傳統的零工式生產排程已經不足以應付少量多樣的生產型態。因而發展出彈性零工式生產排程問題(Flexible Job-Shop Scheduling Problem, FJSP)。FJSP是從典型JSP延伸出來的排程問題，因為FJSP不但要決定加工作業的加工途程，還要指派欲進行加工之機台，因此FJSP又比JSP更為複雜且難解。
蜂群演算法(Honey-Bee Mating Optimization, HBMO)是一種新的啟發式方法，它結合SA、GA、局部搜尋和一些自我更新的方法，且HBMO也陸續被證明是具有高求解效率與品質的演算法。本研究主要是提出一個整合PSO與HBMO的啟發式方法以改善求解FJSP的效能及效率。
本研究所提出的方法針對FJSP標竿資料庫進行多目標排程演算，經排程實驗結果顯示，本研究所提出的PSO+HBMO方法比Temporal decomposition、CGA、AL、AL+CGA、PSO+SA及Simulation model等方法更適合求解FJSP問題。

關鍵字

彈性零工式生產排程 ； 粒子群最佳化 ； 蜂群演算法 ； 多目標排程

並列摘要

Most scheduling problems are very complex combinatorial optimization problems and hard to solve. The job-shop scheduling problem (JSP) is one of the problems. In the literature, more and more researchers used different heuristic algorithms to solve combinatorial optimization problems. Common algorithms are simulated annealing, genetic algorithm, tabu search approach, ant colony optimization and particle swarm optimization and so on.
By more and more progress technology, the traditional job-shop scheduling is not enough to solve the diversity and a little amount production type. The problem is referred to as the flexible job-shop scheduling problem (FJSP). FJSP is an extension of the classical JSP which allows an operation to be processed by any machine out of a set of machines. It combines all of the complexities of JSP and more elaborate than JSP.
Honey-bee mating optimization is a burgeoning heuristic algorithm which included of SA, GA, local search, and some innovations for its self-adaptation. Several studies have been made on efficiency evaluation of HBMO, and HBMO has proven to have good performance and quality in solving NP-hard problems.
In this research, we proposed a heuristic algorithm which integrates PSO and HBMO for solving the multi-objective FJSP. Experiment results indicate this method is competitive and efficient.

並列關鍵字

Flexible job-shop scheduling problem ； Particle swarm optimization ； Honey-bee mating optimization ； Multi-objective scheduling

參考文獻

[47] Y. T. Kua, Applying HBMO and PSO in an Intelligent Market Segmentation System, Master, National Taipei University of Technology, Taipei, 2008.

[1] 邱怡瑛，質群演算法於多組解方程最佳化問題之研究，碩士論文，私立元智大學工業工程與管理研究所，中壢，2004。

[37] R. C. Eberhart and Y. Shi, “Tracking and optimizing dynamic systems with particle swarms,” Proceedings of the 2001 Congress on Evolutionary Computation, Seoul, Korea, 2001, pp.29-36.

[2] A. Baykasoglu, “Linguistic-based meta-heuristic optimization model for flexible job shop scheduling,” International Journal of Production Research, vol. 40, no.17, 2002, pp. 4523-4543.

[3] A. Allahverdi and F. S. Al-Anzi, “A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application,” Computers and Operations Research, vol. 33, no. 4, 2006, pp.1056-1080.