File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/060653445
- Scopus: eid_2-s2.0-55249103152
- WOS: WOS:000254459500014
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Extra unit-speed machines are almost as powerful as speedy machines for flow time scheduling
Title | Extra unit-speed machines are almost as powerful as speedy machines for flow time scheduling |
---|---|
Authors | |
Keywords | Competitive analysis Extra-resource augmentation Flow time Online scheduling Stretch |
Issue Date | 2008 |
Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php |
Citation | SIAM Journal on Computing, 2008, v. 37 n. 5, p. 1595-1612 How to Cite? |
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. © 2008 Society for Industrial and Applied Mathematics. |
Persistent Identifier | http://hdl.handle.net/10722/88925 |
ISSN | 2023 Impact Factor: 1.2 2023 SCImago Journal Rankings: 2.143 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HL | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Liu, KS | en_HK |
dc.date.accessioned | 2010-09-06T09:50:12Z | - |
dc.date.available | 2010-09-06T09:50:12Z | - |
dc.date.issued | 2008 | en_HK |
dc.identifier.citation | SIAM Journal on Computing, 2008, v. 37 n. 5, p. 1595-1612 | en_HK |
dc.identifier.issn | 0097-5397 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/88925 | - |
dc.description.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. © 2008 Society for Industrial and Applied Mathematics. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php | - |
dc.relation.ispartof | SIAM Journal on Computing | en_HK |
dc.rights | © 2008 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 37, issue 5, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Competitive analysis | en_HK |
dc.subject | Extra-resource augmentation | en_HK |
dc.subject | Flow time | en_HK |
dc.subject | Online scheduling | en_HK |
dc.subject | Stretch | en_HK |
dc.title | Extra unit-speed machines are almost as powerful as speedy machines for flow time scheduling | en_HK |
dc.type | Article | en_HK |
dc.identifier.email | Chan, HL:hlchan@cs.hku.hk | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, HL=rp01310 | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1137/060653445 | en_HK |
dc.identifier.scopus | eid_2-s2.0-55249103152 | en_HK |
dc.identifier.hkuros | 146732 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-55249103152&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 37 | en_HK |
dc.identifier.issue | 5 | en_HK |
dc.identifier.spage | 1595 | en_HK |
dc.identifier.epage | 1612 | en_HK |
dc.identifier.eissn | 1095-7111 | - |
dc.identifier.isi | WOS:000254459500014 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Liu, KS=8883021000 | en_HK |
dc.identifier.issnl | 0097-5397 | - |