The pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine

The classical problem of scheduling theory that is NP-hard in the strong sense 1|r _j|L _max is considered. New properties of optimal schedules are found. A polynomially resolved case of the problem is selected, when the release times (r _j), the processing time (p _j), and due dates of completion of processing (d _j) of jobs satisfy the constraints d ₁ ≤ ... ≤ d _n and d ₁ ? r ₁ ? p ₁ ≥ ... ≥ d _n ? r _n ? p _n. An algorithm of run time O(n ³logn) finds Pareto-optimal sets of schedules according to the criteria L _max and C _max that contains no more than n variants.