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.

MSC:
90B35 Scheduling theory, See also {68M20}

 

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.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster