File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/1109557.1109595
- Scopus: eid_2-s2.0-33244454964
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling
Title | Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling |
---|---|
Authors | |
Issue Date | 2006 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, FL, 22-24 January 2006. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, p. 334-343 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 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 [23] and stretch [12], and HDF (high-est density first) is O(1)-competitive for weighted flow time [6]. Using extra unit-speed machines instead of faster machines is more challenging. This paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. It shows that competitive results via faster machines can be transformed to similar results via extra machines, and 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, respectively. |
Persistent Identifier | http://hdl.handle.net/10722/53611 |
ISSN | |
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 | 2009-04-03T07:24:37Z | - |
dc.date.available | 2009-04-03T07:24:37Z | - |
dc.date.issued | 2006 | en_HK |
dc.identifier.citation | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), Miami, FL, 22-24 January 2006. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, p. 334-343 | en_HK |
dc.identifier.issn | 1071-9040 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/53611 | - |
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 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 [23] and stretch [12], and HDF (high-est density first) is O(1)-competitive for weighted flow time [6]. Using extra unit-speed machines instead of faster machines is more challenging. This paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. It shows that competitive results via faster machines can be transformed to similar results via extra machines, and 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, respectively. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. | en_HK |
dc.relation.ispartof | Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms | en_HK |
dc.rights | © 2006 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms in 2006, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.title | Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling | en_HK |
dc.type | Conference_Paper | 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 | en_HK |
dc.identifier.doi | 10.1145/1109557.1109595 | en_HK |
dc.identifier.scopus | eid_2-s2.0-33244454964 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33244454964&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 334 | en_HK |
dc.identifier.epage | 343 | 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 | 1071-9040 | - |