Rights Creative Commons: Attribution 3.0 Hong Kong License Extra Unit-Speed Machines are Almost as Powerful as Speedy Machines for Competitive Flow Time Scheduling

Abstract. We study online scheduling of jobs to mini-mize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate the lack of future information. Recent re-sults show that a modest increase in machine speed can provide very competitive performance; in particular, us-ing O(1) times faster machines, the algorithm SRPT (shortest remaining processing time) is 1-competitive for both flow time [23] and stretch [12], and HDF (high-est density first) is O(1)-competitive for weighted flow time [6]. Using extra unit-speed machines instead of faster machines is more challenging. This paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. It shows that competitive re-sults via faster machines can be transformed to similar results via extra machines, and 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, respectively.