ИСТИНА

We consider the classical NP-hard scheduling problem in strong sense $1|r_j|L_{max}$. New properties of optimal schedules are found. Polynomially case is found when the release times $(r_j)$, the processing times $(p_j)$ and due dates $(d_j)$ of jobs satisfy the relationships: $d_j=\altha p_j+\beta r_j+C$, $p_j\leq 0$, $\alpha\in[0,1]$, $\beta \in [1,+\infty)$, $C$ -- constant. An algorithm finds Pareto-optimal sets of schedules for objective functions $L_{max}$ and $C_{max}$ that contains no more than $n$ schedules. The machine can process at most one job at any time, and preemptions of the processing of a job are forbidden.