以蟻群最佳化演算法求解流線型製造單元排程

Abstract

蟻群最佳化演算法是一種巨集啟發式演算法，被廣範應用於求解複雜的空間搜尋問題。過去的研究，大部份注重於如何應用或加強演算法的搜尋機制，因此，在本研究中提出了新的研究方向：採用新的解表達法，是否能增進蟻群最佳化演算法的表現？ 研究中以固定序列式製造單元的排程為應用問題，比較兩種不同演算法的求解績效。兩種表達法的演算流程相同，但採用的解表達法不同。一種表達法是過去研究常用到的解表達法–舊解表達法，一種是Wu et al. (2011)用到的解表達法–新解表達法。實驗結果顯示，新解表達法在大部份的實驗情境下贏過過去常用的舊表達法，這樣的發現指出針對解表達法的創新及改良，是應用巨集啟發式演算法的研究新方向。

Ant Colony Optimization (ACO), 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 ACO 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 ACO? A Flowshop Manufacturing Cell Scheduling Problem with permutation is used as the problem context, and two ACOs 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 ACO-Sold and ACO-Snew accordingly. Extensive numerical experiments reveal that the two algorithms performs equally well in small setup time (LSU) scenarios. Yet, ACO-Snew outperforms ACO-Sold at small and medium setup time (SSU/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.