A Tabu Search Approach to the Generalized Assignment Problem

以禁忌搜尋演算法求解一般化指派問題

吳泰熙(Tai-Hsi Wu) ； 葉進儀(Jinn-Yi Yeh) ； 蕭育如(Yu-Ru Syau)

《工業工程學刊》 21卷3期 (2004/05) Pp. 301-309

https://doi.org/10.29977/JCIIE.200405.0010

摘要

一般化指派問題尋求最大利潤或最小成本之工作指派計畫，其應用面非常廣泛，單元形成問題即是一例。本文提出一禁忌搜尋演算法TSDL來求解一般化指派問題，該演算法利用了動態禁忌名單及長期記憶體機制。爲驗證本演算法之效用及效率，我們採用了84題文獻範例，並與現存文獻標竿演算結果做一比較後，發現TSDL可以於極短之演算時間內求得品質甚佳之演算結果。

關鍵字

一般化指派問題 ； 禁忌搜尋演算法 ； 動態禁忌名單

並列摘要

The generalized assignment problem (GAP) determines the maximum profit or minimum cost assignment of n jobs to m agents, which is a problem embedded in the cell formation problem. In this paper, a tabu search heuristic, TSDL that consists of dynamic tabu tenure with long-term memory mechanism is presented to solve the GAPs. A standard set of 84 test problems adopted from the literature is used to evaluate the performance of the proposed algorithm and for comparison with other existing methods. The TSDL can very efficiently find solutions with good quality. The proposed algorithm should thus be useful to practitioners and researchers.

並列關鍵字

assignment ； generalized assignment problem ； tabu search ； cell formation problem

參考文獻

Amini, M. M.,M. Racer(1995).A hybrid heuristic for the generalized assignment problem.European Journal of Operational Research.87,343-348.

Baker, B. M.,J. Sheasby(1999).Accelerating the convergence of subgradient optimization.European Journal of Operational Research.117,136-144.

Baker, M.,J. Sheasby(1999).Extensions to the generalized assignment heuristic for vehicle routing.European Journal of Operational Research.119,147-157.

Battiti, R.,G. Tecchiolli(1994).The reactive tabu search.ORSA Journal on Computing.6,126-140.

Beasley, J. E.(1990).OR-Library: Distributing test problems by electronic mail.Journal of Operational Research Society.41,1069-1072.