Minimization of the maximal lateness for a single machine

Consideration was given to the classical NP‐hard problem 1|r j |L max of the scheduling theory. An algorithm to determine the optimal schedule of processing n jobs where the job parameters satisfy a system of linear constraints was presented. The polynomially solvable area of the problem 1|r j |L max was expanded. An algorithm was described to construct a Pareto‐optimal set of schedules by the criteria L max and C max for complexity of O(n ³logn) operations.