File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Online flow time scheduling in the presence of preemption overhead
Title | Online flow time scheduling in the presence of preemption overhead |
---|---|
Authors | |
Keywords | On-line algorithms On-line flow Online problems Pre-emptive scheduling Resource augmentation |
Issue Date | 2012 |
Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
Citation | 15th International Workshop on Approximation, Randomization (APPROX 2012) and 16th International Workshop on Combinatorial Optimization (RANDOM 2012), Cambridge, MA., 15-17 August 2012. In Lecture Notes in Computer Science, 2012, v. 7408, p. 85-97 How to Cite? |
Abstract | This paper revisits the online problem of preemptive scheduling to minimize the total flow time. Previous theoretical results often assume that preemption is free, which is not true for most systems. This paper investigates the complexity of the problem when a processor has to perform a certain amount of overhead (extra work) before it resumes the execution of a job preempted before. Such overhead causes delay to all unfinished jobs. In this paper we first consider single-processor scheduling. We show that no online algorithm can be competitive for total flow time in the presence of preemption overhead (note that the well-known online algorithm SRPT is 1-competitive when preemption overhead is zero). We then consider resource augmentation and show a simple algorithm that is (1 + ε)-speed (1 + 1/ε)-competitive for minimizing total flow time on a single processor. We also extend the result to the multiprocessor setting. © 2012 Springer-Verlag. |
Description | LNCS v. 7408 has title: Approximation, randomization, and combinatorial optimization : algorithms and techniques : 15th International Workshop, APPROX 2012 ... proceedings |
Persistent Identifier | http://hdl.handle.net/10722/164911 |
ISBN | |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HL | en_US |
dc.contributor.author | Lam, TW | en_US |
dc.contributor.author | Li, R | en_US |
dc.date.accessioned | 2012-09-20T08:12:21Z | - |
dc.date.available | 2012-09-20T08:12:21Z | - |
dc.date.issued | 2012 | en_US |
dc.identifier.citation | 15th International Workshop on Approximation, Randomization (APPROX 2012) and 16th International Workshop on Combinatorial Optimization (RANDOM 2012), Cambridge, MA., 15-17 August 2012. In Lecture Notes in Computer Science, 2012, v. 7408, p. 85-97 | en_US |
dc.identifier.isbn | 978-3-642-32511-3 | - |
dc.identifier.issn | 0302-9743 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/164911 | - |
dc.description | LNCS v. 7408 has title: Approximation, randomization, and combinatorial optimization : algorithms and techniques : 15th International Workshop, APPROX 2012 ... proceedings | - |
dc.description.abstract | This paper revisits the online problem of preemptive scheduling to minimize the total flow time. Previous theoretical results often assume that preemption is free, which is not true for most systems. This paper investigates the complexity of the problem when a processor has to perform a certain amount of overhead (extra work) before it resumes the execution of a job preempted before. Such overhead causes delay to all unfinished jobs. In this paper we first consider single-processor scheduling. We show that no online algorithm can be competitive for total flow time in the presence of preemption overhead (note that the well-known online algorithm SRPT is 1-competitive when preemption overhead is zero). We then consider resource augmentation and show a simple algorithm that is (1 + ε)-speed (1 + 1/ε)-competitive for minimizing total flow time on a single processor. We also extend the result to the multiprocessor setting. © 2012 Springer-Verlag. | - |
dc.language | eng | en_US |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_US |
dc.relation.ispartof | Lecture Notes in Computer Science | en_US |
dc.rights | The original publication is available at www.springerlink.com | en_US |
dc.subject | On-line algorithms | - |
dc.subject | On-line flow | - |
dc.subject | Online problems | - |
dc.subject | Pre-emptive scheduling | - |
dc.subject | Resource augmentation | - |
dc.title | Online flow time scheduling in the presence of preemption overhead | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=978-3-642-32511-3&volume=&spage=85&epage=97&date=2012&atitle=Online+Flow+Time+Scheduling+in+the+Presence+of+Preemption+Overhead | en_US |
dc.identifier.email | Chan, HL: hlchan@cs.hku.hk | en_US |
dc.identifier.email | Lam, TW: twlam@cs.hku.hk | en_US |
dc.identifier.email | Li, R: bli@cs.hku.hk | - |
dc.identifier.authority | Chan, HL=rp01310 | en_US |
dc.identifier.authority | Lam, TW=rp00135 | en_US |
dc.identifier.scopus | eid_2-s2.0-84865305975 | - |
dc.identifier.hkuros | 206268 | en_US |
dc.identifier.volume | 7408 | - |
dc.identifier.spage | 85 | en_US |
dc.identifier.epage | 97 | en_US |
dc.publisher.place | Germany | - |
dc.customcontrol.immutable | sml 130417 | - |
dc.identifier.issnl | 0302-9743 | - |