by Kovalyov, M. Y., Werner, F..

**Series:** 1996-07, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

The problem of scheduling n non-preemptive jobs having common

due date d on m; $m \ge 2$, parallel idenical machines to minimize total

tardiness is studied. Approximability issues are discussed and a family

of algorithms $A_{\epsilon}$ is presented such that

($T^A - T^*) / (T^* + d) \leq \epsilon$

holds for any problem instance and for any given

$\epsilon > 0$, where $T^*$ is

the optimal solution value and $T^A$ is the value of solution delivered

by $A_{\epsilon$. Each algorithm $A_{\epsilon}$ runs in

$O(n^3/\epsilon)$ time if $m = 2$ and in

$O(n^{2m}/\epsilon^{m-1}$ time if m is a constant with

$m \ge 3$.

**Keywords:**

- parallel machine scheduling, total tardiness, approximation algorithms

**This paper was published in:**

Journal of Heuristics, Vol. 8, No. 4, 2002, 415 - 428.