File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleExtra unit-speed machines are almost as powerful as speedy machines for flow time scheduling
Authors
KeywordsCompetitive analysis
Extra-resource augmentation
Flow time
Online scheduling
Stretch
Issue Date2007
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP
Citation
SIAM Journal On Computing, 2007, v. 37 n. 5, p. 1595-1612 How to Cite?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/88925
ISSN
2015 Impact Factor: 0.841
2015 SCImago Journal Rankings: 1.808
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLiu, KSen_HK
dc.date.accessioned2010-09-06T09:50:12Z-
dc.date.available2010-09-06T09:50:12Z-
dc.date.issued2007en_HK
dc.identifier.citationSIAM Journal On Computing, 2007, v. 37 n. 5, p. 1595-1612en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88925-
dc.description.abstractWe 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.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMPen_HK
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectCompetitive analysisen_HK
dc.subjectExtra-resource augmentationen_HK
dc.subjectFlow timeen_HK
dc.subjectOnline schedulingen_HK
dc.subjectStretchen_HK
dc.titleExtra unit-speed machines are almost as powerful as speedy machines for flow time schedulingen_HK
dc.typeArticleen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/060653445en_HK
dc.identifier.scopuseid_2-s2.0-55249103152en_HK
dc.identifier.hkuros146732en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-55249103152&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume37en_HK
dc.identifier.issue5en_HK
dc.identifier.spage1595en_HK
dc.identifier.epage1612en_HK
dc.identifier.eissn1095-7111-
dc.identifier.isiWOS:000254459500014-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLiu, KS=8883021000en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats