Metody dywersyfikacji procesu przeszukiwań algorytmów popraw dla problemu przepływowego z kryterium sumacyjnym

• Autorzy: Grabowski J. , Pempera J.

Warianty tytułu

EN

The methods of diversification of local search in flow shop problem with sum of completion times criteria

• Języki publikacji: PL

Abstrakty

PL

W pracy rozważany jest permutacyjny problem przepływowy z kryterium minimalizacji sumy czasów zakończenia wykonywania zadań. Przedstawiamy kilka sposobów dywersyfikacji procesu przeszukiwań, które zostały wykorzystane do konstrukcji algorytmu opartego na technice tabu search. Eksperymenty komputerowe przeprowadzone na literaturowych przykładach testujących pokazują wysoką efektywność proponowanych metod.

EN

In this paper we consider the flow shop problem with sum of completion times criteria. We present several methods of diversification of local search, which are applied to the construction of the tabu search algorithm. Computation experiments using benchmark problems demonstrate the high effectiveness of proposed methods.

Słowa kluczowe

PL

tabu search; dywersyfikacja; problem przepływowy; kryterium sumacyjne

EN

tabu search; diversification; flow shop; sum of completion times criteria

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2007
• Tom: T. 11, z. 1-2
• Strony: 117--127
• Opis fizyczny: Bibliogr. 10 poz., rys., tab.

Twórcy

autor

Grabowski J.

• Instytut Automatyki, Informatyki i Robotyki, Politechnika Wrocławska

autor

Pempera J.

• Instytut Automatyki, Informatyki i Robotyki, Politechnika Wrocławska

Bibliografia

• [1] Kohler W.H., Steiglitz K.: Exact, approximate and guaranteed accuracy algorithms for the flowshop problem n\2\F\F. Journal of the ACM 1975, 22, 106-104
• [2] Yamada T., Reeves C.R.: Sohing the Csum Permutation Flowshop scheduling problem by Genetic Local Search. IEEE International Conference on Evolutionary Computation 1998, 230-234
• [3] Wang C, Chu C, Proth ].: Heuristic approaches for n/m/F/SCi scheduling problems. European Journal of Operational Research 1997, 636-644
• [4] Nowicki E., Smutnicki C: A fast tabu search algorithm for the permutation flowshop problem. European Journal of Operational Research 1996, 91, 160-175
• [5] Grabowski J., Pempera I.: Some local search algorithms for no-wait flow-shop problem with makespan criterion. Computers & Operations Research 2005, 32, 2197-2212
• [6] Grabowski J., Wodecki M.: A very fast tabu search algorithm for the flow shop problem with makespan criterion. Computers and Operations Research 2004, 11, 1891-1909
• [7] Grabowski J., Wodecki M.: A very fast tabu search algorithm for job shop problem. Metaheuristic optimization via memory and evolution. Tabu search and scatter search. Ed. by Cesar Rego and Bahram Alidaee. Boston, Kluwer Academic Publ. 2005, 117-144
• [8] Schuster C.J., Framinan J.M.: Approximative procedures for no-wait job shop scheduling. Operations Research Letters 2003, 31, 308-318
• [9] Nawaz M., Enscore E., Ham I.: A Heuristic algorithm for the m-machine, n-job flowshop sequencing problem. OMEGA The International Journal of Management Science 1983, 11, 91-95
• [1O] Taillard E.: Benchmarks for basic scheduling problems. European Journal of Operational Research 1993, 64, 278-285