Estimation of the Absolute Error and Polynomial Solvability for a Classical NP-Hard Scheduling Problem

Abstract

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.