Approximability of average completion time scheduling on unrelated machines (Q507314)

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.