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

Abstract

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.

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.