Nowy algorytm lokalnej optymalizacji dla zagadnienia kolejnościowego przepływowego

• Autorzy: Bożejko W. , Grabowski J. , Pempera J.

Warianty tytułu

EN

New local search algorithm for the permutation flow-shop problem

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono klasyczne przepływowe zagadnienie szeregowania z kryterium minimalizacji terminu zakończenia wykonywania wszystkich zadań. Przedstawiono nowe własności zagadnienia oraz nowy rodzaj ruchu, którego wykonanie przesuwa jednocześnie co najmniej jedno zadanie w danej permutacji. Ruchy tego rodzaju mogą być stosowane w dowolnych algorytmach lokalnej optymalizacji szeregowania zadań. W niniejszej pracy zastosowano je do algorytmu opartego na technice tabu search. Przeprowadzono eksperymenty obliczeniowe a uzyskane rezultaty porównano z wynikami aktualnie najlepszych na świecie algorytmów opracowanych przez Nowickiego i Smutnickiego oraz Grabowskiego i Pemperę.

EN

The paper deals with the classic flow-shop scheduling problem with the makespan criterion. There are presented and discussed some new properties associated with the blocks and new definition of the move, by using of which at least one job is moved in a given permutation. This move can be applied in any local search algorithms. The algorithm based on tabu search approach is presented. Computational experiments are provided and compared with the results given by the best algorithms proposed by Nowicki & Smutnicki and Grabowski & Pempera.

Słowa kluczowe

PL

algorytm tabu search; algorytm TSAB; algorytm TSN

EN

tabu search algorithm; TSN algorithm

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

Twórcy

autor

Bożejko W.

autor

Grabowski J.

autor

Pempera J.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska