ИСТИНА

We consider single machine scheduling problems. N jobs that must be processed on the machine are given. Machine is ready to star processing since time 0 and can handle only one job at a time. Preemptions are not allowed. Each job $j$ is characterized by processing time $p_j$, due date $d_j$, and release date $r_j$. Our goal is to construct a schedule of processing that minimizes total tardiness of the jobs. We propose a new approach to construct approximate solutions with guaranteed absolute error for the problem. The approach consists in finding an instance of the problem, closest to a given instance in certain metric and using its optimal schedule as an approximate solution for the given instance. The approach can be generalized to scheduling problems with other objective functions.