ИСТИНА

In the paper, we study NP-hard in the ordinary sense scheduling problem of minimizing total tardiness on a single machine 1| |∑ Tj. We introduce four algorithms both polynomial and pseudo-polynomial for finding an optimal schedule for all sub-cases of the case when p1≥ p2≥…≥ pn and d1≤ d2≤ …≤ dn. The processing time pj and due date dj are given for all jobs from N. The machine processes only one job at a time without preemptions.