Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Some modifications of algorithm TSAB for the job shop problem
Języki publikacji
Abstrakty
W pracy rozważa się problem minimalizacji terminu zakończenia wykonywania wszystkich zadań w gniazdowym problemie szeregowania. Przedstawiono szybki i łatwo implementowalny algorytm przybliżony do rozwiązania postawionego problemu. Algorytm ten stanowi modyfikację algorytmu TSAB, otrzymaną przez wykorzystanie oryginalnego przyspieszacza przeglądania sąsiedztwa oraz nowej techniki skoku powrotnego na trajektorii poszukiwań. Algorytm jest oparty na technice tabu z wykorzystaniem sąsiedztwa bazującego na blokach operacji ze ścieżki krytycznej. Przeprowadzone eksperymenty obliczeniowe (do 600 operacji) pokazują, że proponowany algorytm znajduje lepsze rozwiązania niż najlepsze znane do tej pory algorytmy w krótszym czasie, na komputerach o porównywalnej mocy obliczeniowej.
The paper deals with the problem of finding a minimum makespan in a job shop. A fast and easily implemented approximation algorithm for this problem is presented. The proposed algorithm is a modification of algorithm TSAB, obtained by using original search accelerator and new technique of back jumps on the search trajectory. The algorithm is based on a tabu search technique with a specific neighborhood definition. A neighborhood is defined using blocks of operations on a critical path. Computational experiments (up to 600 operations) show that the algorithm not only finds shorter makespan than the best known up to now algorithms but also runs in shorter time.
Wydawca
Rocznik
Tom
Strony
439--447
Opis fizyczny
Bibliogr. 14 poz., tab.
Twórcy
autor
- Instytut Cybernetyki Technicznej, Politechnika Wrocławska
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH1-0023-0150
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ć.