Równoległe szacowanie wartości funkcji celu w elastycznym problemie gniazdowym
Files
Date
Presentation Date
Editor
Other contributors
Other title
Parallel estimation of the cost function for the flexible scheduling problem
Resource type
Version
Pagination/Pages:
Research Project
Description
Abstract
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ń.
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.