以塔布搜尋法求解流線型製造單元排程

Abstract

巨集啟發式演算法-塔布搜尋法已經廣泛地應用於求解複雜的空間搜尋問題。過去的研究專注於如何應用或改善塔布搜尋法機制於不同的問題。相對於過去的研究，本研究則專注於新的研究方向-採取新的解表達方式是否可以改善塔布搜尋法的績效。本研究以固定序列流線型製造單元為排程背景，比較兩種不同的塔布搜尋演算法。值得注意的是，此兩種不同的塔布搜尋演算法在搜尋流程上是相同的，不同的地方在於使用了不同的解表達法，分別稱作舊表達法(Sold)和新表達法(Snew)。Sold為過去研究所使用的解表達法，Snew為Wu et al. (2011)使用的解表達法。使用Sold的演算法稱作Tabu-Sold，使用Snew的演算法則稱作Tabu-Snew。經過大量的數據實驗顯示，使用Snew的演算法Tabu-Snew 其實驗結果皆優於使用Sold的演算法Tabu-Sold。這個發現顯示一個重要的新研究方向，即利用巨集啟發式演算法於不同空間求解問題時，亦可利用新的解表達法來改善空間求解問題。

The tabu-search mechanism, 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 the tabu-search mechanism 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 the tabu-search mechanism? A scheduling problem called flowshop manufacturing cell with permutation is used as the problem context, and two tabu-search algorithms 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 Tabu-Sold and Tabu-Snew accordingly. Extensive numerical experiments reveal that Tabu-Snew comprehensively outperforms Tabu-Sold. This finding highlights an important new research track—exploring new solution representation schemes while applying meta-heuristic algorithms to various space-search problems.