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. © 2008 Society for Industrial and Applied Mathematics. ; published_or_final_version


    Access

    Download


    Export, share and cite



    Title :

    Extra unit-speed machines are almost as powerful as speedy machines for flow time scheduling


    Contributors:
    Chan, HL (author) / Lam, TW (author) / Liu, KS (author)

    Publication date :

    2007-01-01


    Remarks:

    37



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    629




    High Performance Drivetrains for Powerful Mobile Machines

    Schumacher, Andreas / Rahmfeld, Robert / Laffrenzen, Heiko | BASE | 2016

    Free access

    In fra-structure Suppart Hydraulics, Powerful Construction Machines

    Ichiryu, K. | British Library Online Contents | 1996


    Interchangeable-unit machines

    Armitage, J.B. | Engineering Index Backfile | 1930


    Time machines

    Online Contents | 2007