File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling
Title | New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling |
---|---|
Authors | |
Issue Date | 2005 |
Publisher | Springer 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? |
Abstract | This 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. |
Description | LNCS v. 3618 entitled: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August29-September 2. 2005, Proceedings |
Persistent Identifier | http://hdl.handle.net/10722/89024 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, WT | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Liu, KS | en_HK |
dc.contributor.author | Wong, PWH | en_HK |
dc.date.accessioned | 2010-09-06T09:51:26Z | - |
dc.date.available | 2010-09-06T09:51:26Z | - |
dc.date.issued | 2005 | en_HK |
dc.identifier.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 | en_HK |
dc.identifier.issn | 0302-9743 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89024 | - |
dc.description | LNCS v. 3618 entitled: Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August29-September 2. 2005, Proceedings | - |
dc.description.abstract | This 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.language | eng | en_HK |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_HK |
dc.relation.ispartof | Lecture Notes in Computer Science | en_HK |
dc.rights | Theoretical Computer Science. Copyright © Elsevier BV. | en_HK |
dc.title | New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.openurl | http://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+scheduling | en_HK |
dc.identifier.email | Chan, WT: wtchan@cs.hku.hk | en_HK |
dc.identifier.email | Lam, TW: twlam@cs.hku.hk | - |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-26844549193 | en_HK |
dc.identifier.hkuros | 107758 | en_HK |
dc.identifier.hkuros | 130761 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-26844549193&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 3618 | en_HK |
dc.identifier.spage | 236 | en_HK |
dc.identifier.epage | 247 | en_HK |
dc.publisher.place | Germany | en_HK |
dc.identifier.scopusauthorid | Chan, WT=7403918060 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Liu, KS=8883021000 | en_HK |
dc.identifier.scopusauthorid | Wong, PWH=9734871500 | en_HK |
dc.customcontrol.immutable | sml 160105 - merged | - |
dc.identifier.issnl | 0302-9743 | - |