File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: 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
Issue Date2005
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 30th International Symposium on Mathematical Foundations of Computer Science 2005 (MFCS 2005), Gdansk, Poland, 29 August-2 September 2005. In Lecture Notes In Computer Science, 2005, v. 3618, p. 236-247 How to Cite?
AbstractThis paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms SRPT and 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 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 [4], 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. © Springer-Verlag Berlin Heidelberg 2005.
DescriptionLNCS v. 3618 entitled: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August29-September 2. 2005, Proceedings
Persistent Identifierhttp://hdl.handle.net/10722/89024
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLiu, KSen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-09-06T09:51:26Z-
dc.date.available2010-09-06T09:51:26Z-
dc.date.issued2005en_HK
dc.identifier.citationThe 30th International Symposium on Mathematical Foundations of Computer Science 2005 (MFCS 2005), Gdansk, Poland, 29 August-2 September 2005. In Lecture Notes In Computer Science, 2005, v. 3618, p. 236-247en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89024-
dc.descriptionLNCS v. 3618 entitled: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August29-September 2. 2005, Proceedings-
dc.description.abstractThis paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms SRPT and 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 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 [4], 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. © Springer-Verlag Berlin Heidelberg 2005.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.titleNew resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor schedulingen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=359:1-3&spage=430&epage=439&date=2006&atitle=New+resource+augmentation+analysis+of+the+total+stretch+of+SRPT+and+SJF+in+multiprocessor+schedulingen_HK
dc.identifier.emailChan, WT: wtchan@cs.hku.hken_HK
dc.identifier.emailLam, TW: twlam@cs.hku.hk-
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-26844549193en_HK
dc.identifier.hkuros107758en_HK
dc.identifier.hkuros130761-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-26844549193&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3618en_HK
dc.identifier.spage236en_HK
dc.identifier.epage247en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLiu, KS=8883021000en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.customcontrol.immutablesml 160105 - merged-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats