Minimization of the maximal lateness for a single machine

Consideration was given to the classical NP-hard problem $1|r_j|L_\mathrm{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_\mathrm{max}$ was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria $L_\mathrm{max}$ and $C_\mathrm{max}$ for complexity of $O(n^3 \log n)$ operations.

Presented by the member of Editorial Board: F. T. Aleskerov