• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Working paper

A general approximation approach for multi-machine scheduling problems with minimizing the maximum penalty

Lazarev A. A., Lemtuzhnikova D., Werner F.
We consider NP-hard multi{machine scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness. For such problems, we introduce a metric which delivers an upper bound on the absolute error of the objective function value. Taking the given in- stance of some problem and using the introduced metric, we determine the nearest instance for which a polynomial or pseudo-polynomial algorithm is known. For this determined instance, we construct a schedule which is then applied to the original instance. It is shown how this approach is applied to di_erent scheduling problems.