Metoda analizy minimów lokalnych w rozwiązywaniu pewnych problemów optymalizacji dyskretnej

• Autorzy: Bożejko W. , Wodecki M.

Warianty tytułu

EN

Local minima analyzing method for some discrete optimization problems solving

• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrujemy dwumaszynowy problem przepływowy z minimalizacją sumy kar za nieterminowe wykonanie zadań. Przedstawiamy algorytm przybliżony, którego głównym elementem jest analiza minimów lokalnych wyznaczanych przez szybki algorytm typu popraw. Otrzymane wyniki obliczeniowe porównujemy między innymi z wartościami optymalnymi.

EN

In this paper we consider two machine flow shop problem with penalties sum minimization criterion where penalties are established for jobs tardiness. We propose an approximate algorithm which the main element is a module of local minima analyzing determining by a fast local search algorithm. We compare the obtained results with the optimal solutions.

Słowa kluczowe

PL

szeregowanie zadań; problem przepływowy; minima lokalne

EN

scheduling; flow shop problem; two machine; local minima; approximate algorithm

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 215--222
• Opis fizyczny: Bibliogr. 6 poz., tab.

Twórcy

autor

Bożejko W.

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

autor

Wodecki M.

• Instytut Informatyki, Uniwersytet Wrocławski

Bibliografia

• [1] Bożejko W., Wodecki M., A hybrid evolutionary algorithm for the permutation optimization problem. ISDA 05, IEEE Computer Society, 2005, 326-331.
• [2] Grabowski J., Wodecki M., A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers & Operations Research, 31, 2004, 1891-1909.
• [3] Nowicki E., Smutnicki C, A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 91, 1996, 160-175.
• [4] Navaz M., Encore E., Ham I., A heuristic algorithm for the m-machine n-job flow-shop sequencing problem. Omega, 11, 1983, 91-95.
• [5] Potts C.N., Van Wassenhove L.N., A Branch and Bound Algorithm for the Total Weighted Tardiness Problem. Operations Research, 33, 1985, 177-181.
• [6] Wodecki M., A branch-and-bound parallel algorithm for single-machine total weighted tardiness problem. Int. J. Adv. Manuf. Technol., 37, 2008, 996-1004.