Algorithms for Special Single Machine Total Tardiness Problems

2008. No. 12.

Лазарев А. А., Вернер Ф.

The scheduling problem of minimizing total tardiness on a single machine is knownto be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times $p_j$ and the due dates $d_j$ of the jobs $j, \, j \in N = \{ 1, 2, \ldots, n \}$, are oppositely ordered: $p_1\ge p_2\ge\dots\ge p_n$ and $d_1\le d_2\le\dots\le d_n$. It is shown that already this special case is $NP$-hard in the ordinary sense, too. The set of jobs $N$ is partitioned into $\Bbbk, 1 \le \Bbbk \le n$, subsets$\mathcal{M}_1,\mathcal{M}_2,\dots,\mathcal{M}_\Bbbk$,$\mathcal{M}_\nu \bigcap \mathcal{M}_\mu=\emptyset$ for $\nu\ne \mu,$$N=\mathcal{M}_1\bigcup\mathcal{M}_2\bigcup\dots\bigcup\mathcal{M}_\Bbbk$,such that$\max_{i,j\in\mathcal{M}_\nu}|d_i-d_j|\le\min_{j\in\mathcal{M}_\nu}p_j$for each $\nu=1,2,\dots,\Bbbk$. We propose algorithms which solve the problem: in $O(\Bbbk n\sum p_j)$ time if $1\le \Bbbk< n$ in $O(n^2)$ time if $\Bbbk= n$ and in $O(n^2)$ time if $\max_{i,j\in N}|d_i-d_j|\le 1$. The polynomial algorithms do neitherrequire the conditions $p_1\ge p_2\ge\dots\ge p_n$ mentioned above nor integer processing times to construct an optimal schedule. Finally, we apply the idea of the presented algorithm for the case $\Bbbk = 1$ to the even-odd partition problem

Ключевые слова: оптимизация, optimization, модели, models, scheduling theory, теория расписаний, приближенные алгоритмы, approximation algorithms