Równoległy algorytm hybrydowy dla problemu przepływowego z kryterium Csum

• Autorzy: Bożejko W. , Czapiński M. , Wodecki M.

Warianty tytułu

EN

Parallel hybrid algorithm for flow shop problem with Csum criterion

• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrujemy problem przepływowy z kryterium minimalizacji sumy czasów zakończenia zadań (F\\Csum). Przedstawiamy hybrydowy algorytm równoległy oparty na metodzie symulowanego wyżarzania z elementami algorytmu genetycznego. Otrzymane wyniki porównujemy z najlepszymi znanymi w literaturze.

EN

In the paper we consider flow shop problem with the criterion of minimalization of the sum of job's finishing times (F\\Csum). We present the parallel algorithm based on the simulated annealing method. Obtained results are compared to the best known from the literature.

Słowa kluczowe

PL

szeregowanie zadań; problem przepływowy; wyżarzanie symulowane; algorytm równoległy

EN

scheduling; flow shop problem; simulated annealing; parallel algorithm

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

Twórcy

autor

Bożejko W.

• Instytut Informatyki, Automatyki i Robotyki Politechniki Wrocławskiej

autor

Czapiński M.

• Instytut Informatyki, Uniwersytet Wrocławski

autor

Wodecki M.

• Instytut Informatyki, Uniwersytet Wrocławski

Bibliografia

• [1] Bożejko W., Pempera J., Parallel Tabu Search Algorithm for the Permutation Flow Shop Problem with Criterion of Minimizing Sum of Job Completion Times. 2008, Conference on Human System Interaction HSF08, IEEE Computer Sciety, 283-332.
• [2] Bożejko W., Wodecki M., Parallel path-relinking method for the flow shop scheduling problem. 2008, International Conference on Computational Science (ICCS 08) LNCS 5101, 264-273.
• [3] Ćerny V., Thermodynamical approach to travelling salesman problem: An efficient simulation algorithm. J. Optim. Theory Appl, 45, 1985, 41-51.
• [4] Czapiński M., Parallel simulated annealing with geneticenhancement for flowshop problem with Csum. 2009 (w redakcji).
• [5] 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.
• [6] Kirkpatrick S., Gellat CD., Vecchi M.P., Optimization by simulated annealing. Science, 220, 1983, 671-680.
• [7] Liu J., A new heuristic algorithm for csum flowshop scheduling problems. Personal Communication, 1997.
• [8] Nowicki E., Smutnicki C, A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 91, 1996, 160-175.
• [9] OR-Library: http://people.brunel.ac.uk/~mastjjb/jeb/info.html.
• [10] Reeves C.R., Yamada Т., Solving the Csum Permutation Flowshop Scheduling Problem by Genetic Local Search. IEEE International Conference on Evolutionary Computation, 1998, 230-234.
• [11] Taillard E., Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 1993, 278-285.
• [12] Wang C, Chu C, Proth J., Heuristic approaches for n/m/F/SCj scheduling problems. European Journal of Operational Research, 1997, 636-644.