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.