96-07
A Near Optimal Solution to Problem $Pm/d_j = d/ \sum T_j$
by Kovalyov, M. Y.; Werner, F.
Preprint series: 96-07, Preprints
The paper is published: Journal of Heuristics, Vol. 8, No. 4, 2002, 415 - 428.
Abstract: The problem of scheduling n non-preemptive jobs having commondue date d on m; $m \ge 2$, parallel idenical machines to minimize totaltardiness is studied. Approximability issues are discussed and a familyof 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^*$ isthe optimal solution value and $T^A$ is the value of solution deliveredby $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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.