整合粒子群最佳化與模擬退火法求解彈性零工式生產排程問題之研究

Integrating Particle Swarm Optimization and Simulated Annealing for Flexible Job Shop Scheduling Problems

鄭國村(Kuo-Tsun Cheng)

指導教授 ： 邱垂昱

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

摘要

啟發式方法近年常被用來求解組合最佳化問題中非多項式問題(None-Polynomial, NP)。零工式生產排程問題(Job-Shop Scheduling Problem, JSP)則是公認最複雜度且難以解決的NP-hard問題之一。過去傳統求解排程的方法是使用優先派工法則（Priority Dispatching Rule）來決定加工作業的優先順序。但是JSP卻不能單純的以傳統方法解決，因此許多學者開始使用模擬退火法(Simulated Annealing, SA)、遺傳演算法(Genetic Algorithm, GA)及蟻拓最佳化技術(Ant Colony Optimization, ACO)等啟發式方法來求解這類型的問題。
隨著全球產業競爭的加劇，生產型態變得更彈性也更複雜。彈性零工式生產排程(Flexible Job-Shop Scheduling Problem, FJSP)就是這種趨勢下常見的排程問題。FJSP是從典型JSP延伸出來的排程問題，因為FJSP不但要決定加工作業的加工途程，還要指派欲進行加工之機台，因此FJSP又比JSP更為複雜且難解。
粒子群最佳化(Particle Swarm Optimization, PSO)是一種新的啟發式方法，PSO也陸續被證明是具有高求解效率與品質的演算法。本研究主要提出新的PSO權重遞減策略－拋物線遞減權重PSO(PDW-PSO)，並進一步提出整合SA與PDW-PSO的啟發式方法(PDW-PSOSA)以改善求解FJSP的效能及效率。
本研究先分別以4個非線性函數求出PDW-PSO之最佳參數，接著以多個不同維度之非線性函數測試PDW-PSO與PDW-PSOSA之求解效率與品質，並與其他版本的PSO作一比較。經實驗結果顯示，本研究所提出的PDW-PSO與PDW-PSOSA比其他版本的PSO在求解多維度非線性函數問題上具有較高的搜尋成功率。接著，再以PDW-PSOSA針對FJSP標竿資料庫進行多目標排程演算，並分別從不同的排程目標探討其求解績效。經排程實驗結果顯示，本研究所提出的PDW-PSOSA比Temporal decomposition、CGA、AL、AL+CGA等方法更適合解決FJSP問題。

關鍵字

彈性零工式生產排程 ； 粒子群最佳化 ； 模擬退火法 ； 拋物線遞減

並列摘要

Scheduling problems is the most difficult and important problems in the production management. Most scheduling problems are complex combinatorial optimization problems and hard to solve. The job-shop scheduling problem (JSP) is a branch of production scheduling, which is among the hardest combinatorial optimization problems. It is well known that this problem is NP-hard. Therefore, some heuristic methods such as genetic algorithm (GA), simulated annealing (SA) and ant colony optimization (ACO), were created to solve this problems.
With more competitive environment, it is inevitable to improve flexibility of production. The flexible job-shop scheduling problem (FJSP) arose in this trend. FJSP is an extension of the classical JSP that allows an operation of jobs 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.
Particle swarm optimization (PSO) is a burgeoning heuristic inspired by observing the behavior of organisms in bird flock and fish school. Several studies have been made on efficiency evaluation of PSO, and PSO has proven to have good performance and quality in solving NP-hard problems.
In this study, we proposed a hybrid heuristic approach, which integrates improving PSO － Parabola Decreasing Weight PSO (PDW-PSO) and SA for solving several non-linear functions with different dimension and multi-objective FJSP. To evaluate the proposed heuristic approach, comparisons with other known methods such as original PSO with a variety of inertia weight decreasing strategies. Experiment results shows that the proposed approach is competitive and efficient.

並列關鍵字

flexible job-shop scheduling problem ； particle swarm optimization ； simulated annealing ； parabola decreasing

參考文獻

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

[23] 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. 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.

[3] 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.

[4] A. J. Weintraub, D. Cormier, T. J. Hodgson, R. E. King, J. Wilson and A. Zozom Jr., “Scheduling with alternatives: A link between process planning and scheduling,” IIE Transaction, vol. 31, no. 11, 1999, pp. 1093-1102.