以粒子群演算法求解流線型製造單元排程

Abstract

粒子群演算法已被廣泛用於解決複雜的空間搜索問題。以前的研究大多專注於改進粒子群演算法的搜尋機制。本研究不同於傳統的研究方向，探討新的研究議題「採用新的解表達法是否可以提升粒子群演算法的績效」。 本研究以流程式製造單元排程問題為背景，討論兩種粒子群演算法的績效差異。這兩種演算本質上是相同的演算流程，但卻是搭配截然不同的表達法(分別稱作Sold 和 Snew)。其中，Sold是以前研究所用的表達法，而Snew是採用Wu et al., (2011)所提倡的新表達法。這兩種演算法分別稱作PSO-Sold 和 PSO-Snew。本研究採用大量的實驗數據證明， 發現在小整備時間 (SSU)下兩種演算表現都不錯。但是，在中和大的整備時間 (MSU/ LSU)情境下，PSO-Snew 顯著優於 PSO-Sold。本研究實驗結果凸顯了新的研究方向--「針對不同的空間搜尋問題，可以探索新的表達法搭配啟發式演算法的績效」。

Particle swarm optimization (PSO), a type of meta-heuristic algorithms, has been widely used in solving complex space-search problems. Most prior research focused on how to apply or enhance PSO to various problems. Aside from the traditional track, this research examines a new research issue—Can the adoption of a new solution representation scheme improve the performance of PSO? A scheduling problem called Flowshop Manufacturing Cell is used as the problem context, and two PSOs are compared. The two algorithms, essentially the same in algorithmic flow, are distinct in using two different solution representation schemes (respectively called Sold and Snew). Noticeably, Sold was developed by prior studies and Snew is by Wu et al., (2011); the two algorithms are named PSO-Sold and PSO-Snew accordingly. Extensive numerical experiments reveal that the two algorithms performs equally well in small setup time (SSU) scenarios. Yet, PSO-Snew outperforms PSO-Sold at large and medium setup time (LSU/MSU) scenarios. This finding highlights an important new research track—exploring new solution representation schemes while applying meta-heuristic algorithms to various space-search problems.