A method for finding an approximate solution for NP-hard scheduling problems is proposed. The
example of the classical NP-hard in the strong sense problem of minimizing the maximum lateness of job processing
with a single machine shows how a metric introduced on the instance space of the problem and polynomially
solvable areas can be used to find an approximate solution with a guaranteed absolute error. The
method is evaluated theoretically and experimentally and is compared with the ED-heuristic. Additionally,
for the problem under consideration, we propose a numerical characteristic of polynomial unsolvability,
namely, an upper bound for the guaranteed absolute error for each equivalence class of the instance space.