Równoległe szacowanie wartości funkcji celu w elastycznym problemie gniazdowym

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

Warianty tytułu

EN

Parallel estimation of the cost function for the flexible scheduling problem

• Języki publikacji: PL

Abstrakty

PL

W pracy jest rozpatrywany silnie NP-trudny hybrydowy problem szeregowania zadań z równoległymi maszynami, zwany w literaturze elastycznym problemem gniazdowym. Głównym celem pracy jest wskazanie metody przeglądania otoczeń, dla złożonych problemów optymalizacji dyskretnej, z wykorzystaniem środowiska obliczeń równoległych. Aby proces ten przyśpieszyć, zastosowano szacowanie wartości funkcji celu (zamiast liczenia wartości dokładnej). Pozwoliło to znacznie przyśpieszyć obliczenia przy niewielkim pogorszeniu się wartości wyznaczanych rozwiązań.

EN

The aim of this paper is to show how to determine the neigh-borhood of the complex diserete optimization problem and how to search it in the parallel environment, this being illustrated by an example of the hybrid scheduling, more precisely a flexible job shop problem. We present a parallel single-walk approach in this respect. A theoretical analysis based on PRAM model of parallel computing has been made. We propose a cost-optimal method of neighborhood generation parallelization.

Słowa kluczowe

PL

elastyczny problem gniazdowy; szeregowanie zadań; algorytm równoległy; GPU

EN

flexible job shop problem; scheduling; parallel algorithm; GPU

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2011
• Tom: T. 15, z. 2
• Strony: 91--99
• Opis fizyczny: Bibliogr. 7 poz., tab.

Twórcy

autor

Bożejko W.

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

autor

Uchroński M.

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

autor

Wodecki M.

• Uniwersytet Wrocławski, Instytut Informatyki

Bibliografia

• [1] Bożejko W., Uchroński M., Wodecki M., The new golf neighborhood for the flexible job shop problem. Proceedings of the ICCS 2010, Procedia Computer Science, 1, 2010, Elsevier, 289-296.
• [2] Bożejko W., A new class of parallel scheduling algorithms. Oficyna Wydawnicza Politechniki Wrocławskiej, seria: monografie, 2010.
• [3] Gao J., Sun L., Gen M., A hybrid genetic and variable neighborhood descent algorithm forflexible job shop scheduling problems. Computers & Operations Research, 35, 2008, 2892-2907.
• [4] Garey M.R., Johnson D.S., Sethi R., The complexity of the flowshop and jobshop scheduling. Math. Oper. Res., 1/2, 1974, 117-128.
• [5] Hurink E., Jurisch B., Thole M., Tabu search for the job shop scheduling problem with multi-purpose machinę. Operations Research Spektrum, 15, 1994, 205-215.
• [6] Mastrolilli M., Gambardella L.M., Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling, 3/1, 2000, 3-20.
• [7] Pinedo M., Scheduling: theory, algorithms and systems. Englewood Cliffs, NJ: Prentice-Hall, 2002.