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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.