Paper Info
Title
Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling
Abstract
We study online scheduling of jobs to minimize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate for the lack of future information. Recent results show that a modest increase in machine speed can provide very competitive performance; in particular, using $O(1)$ times faster machines, the algorithm SRPT (shortest remaining processing time) is 1-competitive for both flow time [C. A. Phillips et al., in Proceedings of STOC, ACM, New York, 1997, pp. 140-149] and stretch [W. T. Chan et al., in Proceedings of MFCS, Springer-Verlag, Berlin, 2005, pp. 236-247] and HDF (highest density first) is $O(1)$-competitive for weighted flow time [L. Becchetti et al., in Proceedings of RANDOM-APPROX, Springer-Verlag, Berlin, 2001, pp. 36-47]. Using extra unit-speed machines instead of faster machines to achieve competitive performance is more challenging, as a faster machine can speed up a job but extra unit-speed machines cannot. This paper gives a nontrivial relationship between the extra-speed and extra-machine analyses. It shows that competitive results via faster machines can be transformed to similar results via extra machines, hence giving the first algorithms that, using $O(1)$ times unit-speed machines, are 1-competitive for flow time and stretch and $O(1)$-competitive for weighted flow time.
Year
DOI
Venue
2008
10.1137/060653445
SIAM J. Comput.
Keywords
Field
DocType
times faster machine,speedy machines,competitive result,faster machine,shortest remaining processing time,extra unit-speed machine,competitive performance,flow time scheduling,flow time,extra machine,extra resource,extra unit-speed machines,weighted flow time,competitive analysis
Discrete mathematics,Scheduling (computing),Computer science,Parallel computing,Algorithm,Flow time,Competitive analysis,Speedup
Journal
Volume
Issue
ISSN
37
5
0097-5397
Citations 
PageRank 
References 
0
0.34
9
Authors
3
Name
Order
Citations
PageRank
Ho-Leung Chan147125.23
Tak-Wah Lam21860164.96
Kin-Shing Liu320.71