The strongly NP-hard scheduling problem of minimizing the maximum lateness on one
machine subject to job release dates is under study. We present a general scheme of approximation
solution of the problem which is based on searching for a given problem instance another instance,
closest to the original in some metric and belonging to a known polynomially solvable class of
instances. For a few concrete variants of the scheme (using different polynomially solvable classes
of instances) some analytic formulas are found that make it possible, given a problem instance, to
compute easily an upper bound on the absolute error of the solution obtained by a chosen scheme.