File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Non-clairvoyant weighted flow time scheduling with rejection penalty

TitleNon-clairvoyant weighted flow time scheduling with rejection penalty
Authors
KeywordsCompetitive analysis
Nonclairvoyant scheduling
Online scheduling
Rejection penalty
Weighted flow time
Issue Date2012
PublisherAssociation for Computing Machinery.
Citation
The 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), Pittsburgh, PA., 25-27 June 2012. In Proceedinbgs of the 24th ACM SPAA, 2012, p. 246-254 How to Cite?
AbstractThis paper initiates the study of online scheduling with rejection penalty in the non-clairvoyant setting, i.e., the size (processing time) of a job is not assumed to be known at its release time. In the rejection penalty model, jobs can be rejected with a penalty, and the user cost of a job is defined as the weighted flow time of the job plus the penalty if it is rejected before completion. Previous work on minimizing the total user cost focused on the clairvoyant single-processor setting [2, 8] and has produced O(1)-competitive online algorithm for jobs with arbitrary weights and penalties. This paper gives the first non-clairvoyant algorithms that are O(1)-competitive for minimizing the total user cost on a single processor and multi-processors, when using slightly faster (i.e., (1 + ε)-speed for any ε > 0) processors. Note that if no extra speed is allowed, no on- line algorithm can be O(1)-competitive even for minimizing (unweighted) flow time alone. The new user cost results can also be regarded as a generalization of previous non-clairvoyant results on minimizing weighted flow time alone (WSETF [4] for a single pro- cessor; WLAPS [14] for multi-processors). The above results assume a processor running at a fixed speed. This paper shows more interesting results on extending the above study to the dynamic speed scaling model, where the processor can vary the speed dynamically and the rate of energy consumption is an arbitrary increasing function of speed. A scheduling algorithm has to decide job rejection and determine the order and speed of job execution. It is interesting to study the tradeoff between the above-mentioned user cost and energy. This paper gives two O(1)-competitive non-clairvoyant algorithms for minimizing the user cost plus energy on a single processor and multi-processors, respectively. Copyright 2012 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/164910
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorChan, SHen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorZhu, Jen_HK
dc.date.accessioned2012-09-20T08:12:21Z-
dc.date.available2012-09-20T08:12:21Z-
dc.date.issued2012en_HK
dc.identifier.citationThe 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), Pittsburgh, PA., 25-27 June 2012. In Proceedinbgs of the 24th ACM SPAA, 2012, p. 246-254en_US
dc.identifier.issn978-1-4503-1213-4en_US
dc.identifier.urihttp://hdl.handle.net/10722/164910-
dc.description.abstractThis paper initiates the study of online scheduling with rejection penalty in the non-clairvoyant setting, i.e., the size (processing time) of a job is not assumed to be known at its release time. In the rejection penalty model, jobs can be rejected with a penalty, and the user cost of a job is defined as the weighted flow time of the job plus the penalty if it is rejected before completion. Previous work on minimizing the total user cost focused on the clairvoyant single-processor setting [2, 8] and has produced O(1)-competitive online algorithm for jobs with arbitrary weights and penalties. This paper gives the first non-clairvoyant algorithms that are O(1)-competitive for minimizing the total user cost on a single processor and multi-processors, when using slightly faster (i.e., (1 + ε)-speed for any ε > 0) processors. Note that if no extra speed is allowed, no on- line algorithm can be O(1)-competitive even for minimizing (unweighted) flow time alone. The new user cost results can also be regarded as a generalization of previous non-clairvoyant results on minimizing weighted flow time alone (WSETF [4] for a single pro- cessor; WLAPS [14] for multi-processors). The above results assume a processor running at a fixed speed. This paper shows more interesting results on extending the above study to the dynamic speed scaling model, where the processor can vary the speed dynamically and the rate of energy consumption is an arbitrary increasing function of speed. A scheduling algorithm has to decide job rejection and determine the order and speed of job execution. It is interesting to study the tradeoff between the above-mentioned user cost and energy. This paper gives two O(1)-competitive non-clairvoyant algorithms for minimizing the user cost plus energy on a single processor and multi-processors, respectively. Copyright 2012 ACM.en_HK
dc.languageengen_US
dc.publisherAssociation for Computing Machinery.en_US
dc.relation.ispartofAnnual ACM Symposium on Parallelism in Algorithms and Architecturesen_HK
dc.rightsProceedinbgs of the 24th ACM Symposium on Parallelism in Algorithms and Architectures. Copyright © Association for Computing Machinery.-
dc.subjectCompetitive analysisen_HK
dc.subjectNonclairvoyant schedulingen_HK
dc.subjectOnline schedulingen_HK
dc.subjectRejection penaltyen_HK
dc.subjectWeighted flow timeen_HK
dc.titleNon-clairvoyant weighted flow time scheduling with rejection penaltyen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=978-1-4503-1213-4&volume=&spage=246&epage=254&date=2012&atitle=Non-clairvoyant+weighted+flow+time+scheduling+with+rejection+penaltyen_US
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.1145/2312005.2312050en_HK
dc.identifier.scopuseid_2-s2.0-84864126527en_HK
dc.identifier.hkuros206264en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84864126527&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage246en_HK
dc.identifier.epage254en_HK
dc.publisher.placeUnited States-
dc.description.otherThe 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), Pittsburgh, PA., 25-27 June 2012. In Proceedinbgs of the 24th ACM SPAA, 2012, p. 246-254-
dc.identifier.scopusauthoridChan, HL=55171146200en_HK
dc.identifier.scopusauthoridChan, SH=36652336600en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridZhu, J=55170440000en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats