LP-based online scheduling: From single to parallel machines (Q1013970)

This paper considers the problem of scheduling \(n\) jobs with given release dates on \(m\) identical parallel machines such that the sum of weighted completion times becomes minimal. Both the non-preemptive and the preemptive problems are considered in an online version. The paper uses linear programming techniques and generalizes the ideas given by \textit{M. X. Goemans} et al. [SIAM J. Discrete Math. 15, No. 2, 165--192 (2002; Zbl 1009.90096)] for the single machine problem to the parallel machine case. In particular, it improves the 3.28-competitive algorithm by \textit{N. Megow} and \textit{A. S. Schulz} [Oper. Res. Lett. 32, No. 5, 485--490 (2004; Zbl 1054.90037)] for the non-preemptive version and is 2.618-competitive. Moreover, it is shown that the algorithm can be improved further using randomization. More precisely, randomized algorithms with a competitive ratio strictly smaller than two are given for any number of machines, approaching to two as the number of machines grows. This improves former algorithms by \textit{A. S. Schulz} and \textit{M. Skutella} [SIAM J. Discrete Math. 15, No. 4, 450--469 (2002; Zbl 1055.90040)]. Finally, computational results are given for problems with up to 500 jobs and 25 machines.