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

A Tabu Search Approach to Scheduling Flowshop Manufacturing Cell

林耿漢

指導教授 ： 巫木誠

國立交通大學/管理學院/工業工程與管理系所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.00203

摘要

巨集啟發式演算法-塔布搜尋法已經廣泛地應用於求解複雜的空間搜尋問題。過去的研究專注於如何應用或改善塔布搜尋法機制於不同的問題。相對於過去的研究，本研究則專注於新的研究方向-採取新的解表達方式是否可以改善塔布搜尋法的績效。本研究以固定序列流線型製造單元為排程背景，比較兩種不同的塔布搜尋演算法。值得注意的是，此兩種不同的塔布搜尋演算法在搜尋流程上是相同的，不同的地方在於使用了不同的解表達法，分別稱作舊表達法(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.

並列關鍵字

Tabu search ； solution representation ； scheduling

參考文獻

呂佳玟，「應用基因演算法與家族式派工於傳輸整合步進機在小批量情境下之排程問題」，國立交通大學工業工程與管理學系，碩士論文，民國98年。

Cheng, T.C.E., Gupta, N.D.J., and Wang, G., 2000. A view of flowshop scheduling research with setup times. Production and Operations Management, 9, 262-282.

Das, S.R., and Canel, C., 2005. An algorithm for scheduling batches of parts in a multi-cell flexible manufacturing system. International Journal of Production Economics, 97, 247-262.

Franca, P.M., Gupta, J.N.D., and Mendes, A.S., 2005. Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups. Computer & Industrial Engineering, 48, 491-506.

Glover, F., 1989. Tabu search Part I. ORSA Journal of Computing, 1, 190-206.