Metody dywersyfikacji procesu przeszukiwań w algorytmach popraw dla przepływowego problemu kolejnościowego

• Autorzy: Grabowski J. , Pempera J.

Warianty tytułu

EN

Some methods of diversification in local search algorithms for the flow-shop problem

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono klasyczne przepływowe zagadnienie szeregowania z kryterium minimalizacji terminu zakończenia wykonywania wszystkich zadań. Przedstawiono nowe metody dywersyfikacji (tzw. perturbacje) polegające na jednoczesnym przesunięciu kilku zadań w danej permutacji. Zaprezentowano także tablicę tabu o zmiennej długości. W niniejszej pracy elementy te zastosowano do algorytmu bazującego na technice tabu search. Przeprowadzono eksperymenty obliczeniowe, a uzyskane rezultaty porównano z wynikami aktualnie najlepszych na świecie algorytmów prezentowanych w literaturze.

EN

The paper deals with the classic flow-shop scheduling problem with the makespan criterion. There are presented and discussed some original methods of diversification (so-called perturbations) associated with the blocks by using of which a few jobs are moved simultaneously in a given permutation, and a tabu list with dynamic length. The algorithm based on tabu search approach is presented. Computational experiments are provided and compared with the results given by the best algorithms proposed in the literature.

Słowa kluczowe

PL

szeregowanie zadań; problem przepływowy; algorytm popraw

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 185--194
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Grabowski J.

• Politechnika Wrocławska, Wrocław

autor

Pempera J.

• Politechnika Wrocławska, Wrocław

Bibliografia

• 1. Amin S.: Zusing Adaptive Temperature Control for Solving Optimisation Problems, Baltzer Journals, 1996.
• 2. Aarts Lenstra J.K.: Local search in Combinatorial Optimization. John Wiley and Sons Ltd, Chichester 1997, England.
• 3. Bożejko W., Grabowski J., Pempera J.: Nowy algorytm lokalnej optymalizacji dla zagadnienia kolejnościowego przepływowego. Automatyka 2001, 77-86.
• 4. Dorigo M., Maniezzo V., Colomi A.: Ant System: Optimization by a Colony of Cooperating Agents. lee Transactions on Systems, Man, and Cybernetics, 1996,26 29-41.
• 5. Grabowski J., Pempera J.: New block properties for the permutation flow-shop problem with application in TS, Journal of Operational Research Society 52,2001,210-220.
• 6. Nowicki E., Smutnicki C.: A fast tabu search algorithm for the permutation flow-shop problem, European Journal of Operational Research 91 (1996), 160-175.
• 7. Nowicki E., Smutnicki C.: A fast tabu search algorithm for the job-shop problem. Management Science 42 (1996), 797-813.
• 8. Reeves C. R., Yamada T.: Genetic Algorithms, Path Relinking and the Fowshop Sequencing Problem, Evolutionary Computation Journal (MIT press)
• 9. Taillard E.: Some efficient heuristic methods for flow-shop sequencing, European Journal of Operational Research 47 (1990) 65-74.