PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 3

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  algorytm TSAB
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Nowa metoda dywersyfikacji w algorytmach tabu dla problemu przepływowego
Nowicki E.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
193-198
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.
2
Content available remote 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
PL
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.
EN
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.
3
Content available remote Nowy algorytm lokalnej optymalizacji dla zagadnienia kolejnościowego przepływowego
Bożejko W., Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2001
|
T. 5, z. 1/2
77-85
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.
first rewind previous Strona / 1 next fast forward last
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ć.