TY - GEN
T1 - Scheduling-LPs bear probabilities randomized approximations for min-sum criteria
AU - Schulz, Andreas S.
AU - Skutella, Martin
N1 - Publisher Copyright:
© 1997, Springer Verlag, All Rights Reserved.
PY - 1997
Y1 - 1997
N2 - In this paper, we provide a new class of randomized approximation algorithms for scheduling problems by directly interpreting solutions to so-called time-indexed LPs as probabilities. The most general model we consider is scheduling unrelated parallel machines with release dates (or even network scheduling) so as to minimize the average weighted completion time. The crucial idea for these multiple machine problems is not to use standard list scheduling but rather to assign jobs randomly to machines (with probabilities taken from an optimal LP solution) and to perform list scheduling on each of them. For the general model, we give a (2+ ɛ)-approximation algorithm. The best previously known approximation algorithm has a performance guarantee of 16/3 [HSW96]. Moreover, our algorithm also improves upon the best previously known approximation algorithms for the special case of identical parallel machine scheduling (performance guarantee (2.89 + ɛ) in general [CPS+96] and 2.85 for the average completion time [CMNS97], respectively). A perhaps surprising implication for identical parallel machines is that jobs are randomly assigned to machines, in which each machine is equally likely. In addition, in this case the algorithm has running time O(nlogn) and performance guarantee 2. The same algorithm also is a 2-approximation for the corresponding preemptive scheduling problem on identical parallel machines. Finally, the results for identical parallel machine scheduling apply to both the off-line and the on-line settings with no difference in performance guarantees. In the on-line setting, we are scheduling jobs that continually arrive to be processed and, for each time t, we must construct the schedule until time t without any knowledge of the jobs that will arrive afterwards.
AB - In this paper, we provide a new class of randomized approximation algorithms for scheduling problems by directly interpreting solutions to so-called time-indexed LPs as probabilities. The most general model we consider is scheduling unrelated parallel machines with release dates (or even network scheduling) so as to minimize the average weighted completion time. The crucial idea for these multiple machine problems is not to use standard list scheduling but rather to assign jobs randomly to machines (with probabilities taken from an optimal LP solution) and to perform list scheduling on each of them. For the general model, we give a (2+ ɛ)-approximation algorithm. The best previously known approximation algorithm has a performance guarantee of 16/3 [HSW96]. Moreover, our algorithm also improves upon the best previously known approximation algorithms for the special case of identical parallel machine scheduling (performance guarantee (2.89 + ɛ) in general [CPS+96] and 2.85 for the average completion time [CMNS97], respectively). A perhaps surprising implication for identical parallel machines is that jobs are randomly assigned to machines, in which each machine is equally likely. In addition, in this case the algorithm has running time O(nlogn) and performance guarantee 2. The same algorithm also is a 2-approximation for the corresponding preemptive scheduling problem on identical parallel machines. Finally, the results for identical parallel machine scheduling apply to both the off-line and the on-line settings with no difference in performance guarantees. In the on-line setting, we are scheduling jobs that continually arrive to be processed and, for each time t, we must construct the schedule until time t without any knowledge of the jobs that will arrive afterwards.
UR - http://www.scopus.com/inward/record.url?scp=84949204738&partnerID=8YFLogxK
U2 - 10.1007/3-540-63397-9_32
DO - 10.1007/3-540-63397-9_32
M3 - Conference contribution
AN - SCOPUS:84949204738
SN - 3540633979
SN - 9783540633976
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 416
EP - 429
BT - Algorithms - ESA 1997 - 5th Annual European Symposium, Proceedings
A2 - Burkard, Rainer
A2 - Woeginger, Gerhard
PB - Springer Verlag
T2 - 5th Annual European Symposium on Algorithms, ESA 1997
Y2 - 15 September 1997 through 17 September 1997
ER -