The classical problem of scheduling theory that is NP-hard in the strong sense 1|rj |Lmax is considered. New properties of optimal schedules are found. A polynomially resolved case of the problem is selected, when the release times (rj), the processing time (pj), and due dates of completion of processing (dj) of jobs satisfy the constraints d1 ≤ … ≤ dn and d1 – r1 – p1 ≥ … ≥ dn – rn – pn. An algorithm of run time O(n3logn) finds Pareto-optimal sets of schedules according to the criteria Lmax and Cmax that contains no more than n variants.