Paper Info
Title
Minimizing average flow time on related machines
Abstract
We give the first on-line poly-logarithmic competitve algorithm for minimizing average flow time with preemption on related machines, i.e., when machines can have different speeds. This also yields the first poly-logarithmic polynomial time approximation algorithm for this problem.More specifically, we give an O(log2 P • log S)-competitive algorithm, where P is the ratio of the biggest and the smallest processing time of a job, and S is the ratio of the highest and the smallest speed of a machine. Our algorithm also has the nice property that it is non-migratory. The scheduling algorithm is based on the concept of making jobs wait for a long enough time before scheduling them on slow machines.
Year
DOI
Venue
2006
10.1145/1132516.1132618
STOC
Keywords
Field
DocType
smallest speed,competitive algorithm,smallest processing time,average flow time,log2 p,scheduling algorithm,on-line poly-logarithmic competitve algorithm,long enough time,different speed,poly-logarithmic polynomial time approximation,related machine,approximation algorithms,scheduling,competitive ratio
Approximation algorithm,Mathematical optimization,Fair-share scheduling,Computer science,Scheduling (computing),Flow shop scheduling,Least slack time scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Competitive analysis
Conference
ISBN
Citations 
PageRank 
1-59593-134-1
9
0.80
References 
Authors
11
2
Name
Order
Citations
PageRank
Naveen Garg12181178.27
Amit Kumar224017.84