Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorithm TSAB

Sortuj według:

Ogranicz wyniki do:

Pewne modyfikacje algorytmu TSAB dla problemu gniazdowego

Nowicki E.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

2001

T. 5, z. 1/2

439-447

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.