File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Online flow time scheduling in the presence of preemption overhead

TitleOnline flow time scheduling in the presence of preemption overhead
Authors
KeywordsOn-line algorithms
On-line flow
Online problems
Pre-emptive scheduling
Resource augmentation
Issue Date2012
PublisherSpringer 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?
AbstractThis 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.
DescriptionLNCS v. 7408 has title: Approximation, randomization, and combinatorial optimization : algorithms and techniques : 15th International Workshop, APPROX 2012 ... proceedings
Persistent Identifierhttp://hdl.handle.net/10722/164911
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorLi, Ren_US
dc.date.accessioned2012-09-20T08:12:21Z-
dc.date.available2012-09-20T08:12:21Z-
dc.date.issued2012en_US
dc.identifier.citation15th 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-97en_US
dc.identifier.isbn978-3-642-32511-3-
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/164911-
dc.descriptionLNCS v. 7408 has title: Approximation, randomization, and combinatorial optimization : algorithms and techniques : 15th International Workshop, APPROX 2012 ... proceedings-
dc.description.abstractThis 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.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.comen_US
dc.subjectOn-line algorithms-
dc.subjectOn-line flow-
dc.subjectOnline problems-
dc.subjectPre-emptive scheduling-
dc.subjectResource augmentation-
dc.titleOnline flow time scheduling in the presence of preemption overheaden_US
dc.typeConference_Paperen_US
dc.identifier.openurlhttp://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+Overheaden_US
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_US
dc.identifier.emailLam, TW: twlam@cs.hku.hken_US
dc.identifier.emailLi, R: bli@cs.hku.hk-
dc.identifier.authorityChan, HL=rp01310en_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.identifier.scopuseid_2-s2.0-84865305975-
dc.identifier.hkuros206268en_US
dc.identifier.volume7408-
dc.identifier.spage85en_US
dc.identifier.epage97en_US
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 130417-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats