Estimation of the absolute error and polynomial solvability for a classical $NP$-hard scheduling problem

AbstractA 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.