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.
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ć.