Nowa metoda dywersyfikacji w algorytmach tabu dla problemu przepływowego

• Autorzy: Nowicki E.

Warianty tytułu

EN

New method of diversification in tabu search algorithms for the flow-shop problem

• Języki publikacji: PL

Abstrakty

PL

W pracy rozważa się klasyczny problem minimalizacji terminu zakończenia wykonywania wszystkich zadań w przepływowym problemie szeregowania. Pewne własności szybkiego algorytmu TSAB Nowickiego i Smutnickiego zostały przedyskutowane. Następnie, wykorzystując nową metodę dywersyfikacji, algorytm TSAB został osadzony w bardziej zaawansowanym algorytmicznym schemacie, zwanym i-TSAB. Proponowana metoda dywersyfikacji ma pewne cechy wspólne z techniką path relinking. Algorytm i-TSAB jest szybki i dostarcza rozwiązań o lepszej jakości niż TSAB. Przykładowo, już w początkowych testach, w czasie kilku minut na komputerze klasy PC dostarczył 7 nowych górnych ograniczeń wśród 33 nie rozwiązanych do tej pory instancji Taillarda.

EN

The paper deals with the classic problem of finding a minimum makespan in a flow-shop. Some properties of the fast algorithm TSAB of Nowicki and Smutnicki have been discussed. Next, by introducing the original method of diversification, TSAB has been embedded in more advanced algorithmic framework i-TSAB, which has far analogy to path relinking technique. Newly proposed algorithm is faster and has better accuracy than TSAB, runs within time of minutes on a PC and already in preliminary tests provides 7 new upper bounds among 33 unsolved yet common Taillard's benchmarks.

Słowa kluczowe

PL

algorytm TSAB; problem przepływowy; metoda dywersyfikacji

EN

tabu search algorithm; flow-shop problem; method of diversification

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2003
• Tom: T. 7, z. 1-2
• Strony: 193--198
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Nowicki E.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

Bibliografia

• [1] Aarts E.H.I., Lenstra J.K.: Local search in combinatorial optimization. Chichester, England, John Wiley and Sons LtD 1997
• [2] Glover F., Laguna M.: Tabu search. Massachusetts USA, Kluwer Academic Publishers 1997
• [3] Grabowski J., Pempera J.: New block properties for the permutation flow shop problem with application in tabu search. Journal of the Operational Research Society, 52, 2001, 210-220
• [4] Grabowski J., Nowicki E., Smutnicki C.: Metoda blokowa w zagadnieniach szeregowania zadań. Warszawa, Akademicka Oficyna Wydawnicza EXIT 2003
• [5] Nowicki E.: Metoda tabu w problemach szeregowania zadań produkcyjnych. Monografia 27, Oficyna Wydawnicza Politechniki Wrocławskiej 1999
• [6] Nowicki E.: Analiza algorytmu tabu dla problemu przepływowego. Zbiór referatów III Konferencja Komputerowo Zintegrowane Zarządzanie, Warszawa, WNT 2000
• [7] Nowicki E., Smutnicki C.: A fast tabu search algorithm for the flow shop problem. European Journal of Operational Research, 91, 1996, 160-175
• [8] Nowicki E., Smutnicki C.: Some new ideas in TS for job-shop scheduling. Technical Report 50/2001, Institute of Engineering Cybernetics, Wroclaw University of Technology, [in:] Rego C., Alidaee B. (Eds), Adaptive Memory and Evolution: Tabu Search and Scatter Search, Kluwer Academic Publishers 2003 (In print)
• [9] Nowicki E., Smutnicki C.: Some new tools to solve the job shop problem. Technical Report 60/2002, Wroclaw, Poland, Institute of Engineering Cybernetics, Wroclaw University of Technology 2002
• [10] Reeves C.R., Yamada T: Genetic Algorithms, Path Relinking and the Flowshop Sequencing Problem. Evolutionary Computation Journal, 6, 1998, 45-60
• [11] Taillard E.: Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 1993, 278-285
• [12] Taillard E.: Internet, http://www.eivd.ch/ina/collaborateurs/etd/default.htm