File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling

TitleNew resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling
Authors
KeywordsCompetitive Analysis
Multiprocessor Scheduling
Online Algorithms
Resource Augmentation
Issue Date2006
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2006, v. 359 n. 1-3, p. 430-439 How to Cite?
AbstractThis paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms Shortest Remaining Processing Time First (SRPT) and Shortest Job First (SJF) for minimizing total stretch, where the stretch of a job is its flow time (response time) divided by its processing time. SRPT is perhaps the most well-studied algorithm for minimizing total flow time or stretch. This paper gives the first resource augmentation analysis of the total stretch of SRPT, showing that it is indeed O (1)-speed 1-competitive. This paper also gives a simple lower bound result showing that SRPT is not s-speed 1-competitive for any s < 1.5. This paper also makes contribution to the analysis of SJF. Extending the work of [L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, K. Pruhs, Online weighted flow time and deadline scheduling, in: RANDOM-APPROX, 2001, pp. 36-47], we are able to show that SJF is O (1)-speed 1-competitive for minimizing total stretch. More interestingly, we find that the competitiveness of SJF can be reduced arbitrarily by increasing the processor speed (precisely, SJF is O (s)-speed (1 / s)-competitive for any s ≥ 1). We conjecture that SRPT also admits a similar result. © 2006 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152343
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorLiu, KSen_US
dc.contributor.authorWong, PWHen_US
dc.date.accessioned2012-06-26T06:37:20Z-
dc.date.available2012-06-26T06:37:20Z-
dc.date.issued2006en_US
dc.identifier.citationTheoretical Computer Science, 2006, v. 359 n. 1-3, p. 430-439en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/152343-
dc.description.abstractThis paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms Shortest Remaining Processing Time First (SRPT) and Shortest Job First (SJF) for minimizing total stretch, where the stretch of a job is its flow time (response time) divided by its processing time. SRPT is perhaps the most well-studied algorithm for minimizing total flow time or stretch. This paper gives the first resource augmentation analysis of the total stretch of SRPT, showing that it is indeed O (1)-speed 1-competitive. This paper also gives a simple lower bound result showing that SRPT is not s-speed 1-competitive for any s < 1.5. This paper also makes contribution to the analysis of SJF. Extending the work of [L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, K. Pruhs, Online weighted flow time and deadline scheduling, in: RANDOM-APPROX, 2001, pp. 36-47], we are able to show that SJF is O (1)-speed 1-competitive for minimizing total stretch. More interestingly, we find that the competitiveness of SJF can be reduced arbitrarily by increasing the processor speed (precisely, SJF is O (s)-speed (1 / s)-competitive for any s ≥ 1). We conjecture that SRPT also admits a similar result. © 2006 Elsevier B.V. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.subjectCompetitive Analysisen_US
dc.subjectMultiprocessor Schedulingen_US
dc.subjectOnline Algorithmsen_US
dc.subjectResource Augmentationen_US
dc.titleNew resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor schedulingen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/j.tcs.2006.06.003en_US
dc.identifier.scopuseid_2-s2.0-33746372167en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33746372167&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume359en_US
dc.identifier.issue1-3en_US
dc.identifier.spage430en_US
dc.identifier.epage439en_US
dc.identifier.isiWOS:000239885600029-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChan, WT=7403918060en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridLiu, KS=8883021000en_US
dc.identifier.scopusauthoridWong, PWH=9734871500en_US
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats