Algorytm tabu w optymalizacji uogólnionego problemu przydziału

• Autorzy: Wala K.

Warianty tytułu

EN

Tabu algorithm for optimization of the generalized assignment problem

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono model dyskretny uogólnionego problemu przydziału. Model ten reprezentuje określone problemy przydziału zadań do środków. Dla badanego NP-trudnego problemu optymalizacji dyskretnej zaproponowano sześć algorytmów konstrukcyjnych szeregowania listowego oraz, jako algorytm popraw, algorytm tabu z pamięcią krótko- i długo terminową. Załączono wyniki badań numerycznych procesu poprawy rozwiązań dla instancji z biblioteki OR-library.

EN

In the paper the discrete model of generalized assignment problem is presented. For investigated NP-hard discrete optimization problem we give detailed description of six constructive algorithms and as improving algorithm the tabu one with short and long term memory. Numerical results of improving processes for instances from the OR_library are included.

Słowa kluczowe

PL

uogólniony problem przydziału; algorytm tabu; sąsiedztwo

EN

generalized assignment problem; tabu algorithm; neighbourhood

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2007
• Tom: T. 11, z. 1-2
• Strony: 309--316
• Opis fizyczny: Bibliogr. 5 poz., tab.

Twórcy

autor

Wala K.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Glover R, Taillard E., de Werra D.: A users guide to Tabu Search. Annals of Operations Research, 41:3-28, 1993
• [2] Martello S., Toth R: An algorithm for the generalized assignment problem, in: J. P. Brans, ed., Operational Research'81, North-Holland, Amsterdam, 1981
• [3] Martello S., Toth R: Linear assignment problems. Annals of Discrete Mathematics, 259-282, 1987
• [4] Osman I. H.: Heuristic for the generalized assignment problem: simulated annealing and tabu search approaches. OR Spektrum, Vol. 17, 211-225, 1995
• [5] OR-library, http://mscmga.ms.ic.ac.uk/