Pseudopolynomial Approximation Algorithm for Solving the $NP$-Complete Problem of Minimizing Maximum Lateness

The article states and proves pseudopolynomial complexity approximation algorithm for solving the scheduling theory known as $NP$-complete problem, namely minimizing maximum lateness on a single machine, interruption in job processing being banned. The bound value absolute error of criterion function for schedule constructed by algorithm is received.