Approximability of average completion time scheduling on unrelated machines (Q507314): Difference between revisions
From MaRDI portal
Revision as of 08:52, 13 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximability of average completion time scheduling on unrelated machines |
scientific article |
Statements
Approximability of average completion time scheduling on unrelated machines (English)
0 references
3 February 2017
0 references
This paper deals with the unweighted and weighted versions of the problem to minimize total completion time on unrelated parallel machines if preemption of operations is allowed. In Section 2, the author proves that already the unweighted version of this problem is \(\mathcal{APX}\)-hard. The second contribution of this paper are two approximation algorithms for the weighted version of this problem in Section 3. The first approximation algorithm is based on the 2-approximation algorithm given by \textit{M. Skutella} [J. ACM 48, No. 2, 206--242 (2001; Zbl 1323.90024)] and has an approximation ratio less than 1.81. The second algorithm is obtained by applying the first algorithm and another algorithm given by \textit{M. Queyranne} and \textit{M. Sviridenko} [J. Sched. 5, No. 4, 287--305 (2002; Zbl 1009.90046)] and taking then the better of the two solutions determined. This latter algorithm has an approximation ratio less than 1.698. The results of this paper fill a gap in the complexity classification results for this objective function, and it also improves the previously best known approximation ratio for this problem.
0 references
scheduling
0 references
total completion time
0 references
preemption
0 references
unrelated machines
0 references
\(\mathcal{APX}\)-hardness
0 references
approximation algorithm
0 references
0 references
0 references