Zurück zu den Preprints des Jahres 1996


1996-07

A Near Optimal Solution to Problem $Pm/d_j = d/ \sum T_j$

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.