File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Non-clairvoyant weighted flow time scheduling with rejection penalty
  • Basic View
  • Metadata View
  • XML View
TitleNon-clairvoyant weighted flow time scheduling with rejection penalty
 
AuthorsChan, HL1
Chan, SH1
Lam, TW1
Lee, LK1
Zhu, J1
 
KeywordsCompetitive analysis
Nonclairvoyant scheduling
Online scheduling
Rejection penalty
Weighted flow time
 
Issue Date2012
 
PublisherAssociation for Computing Machinery.
 
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-254 [How to Cite?]
DOI: http://dx.doi.org/10.1145/2312005.2312050
 
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.
 
ISSN978-1-4503-1213-4
 
DOIhttp://dx.doi.org/10.1145/2312005.2312050
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChan, HL
 
dc.contributor.authorChan, SH
 
dc.contributor.authorLam, TW
 
dc.contributor.authorLee, LK
 
dc.contributor.authorZhu, J
 
dc.date.accessioned2012-09-20T08:12:21Z
 
dc.date.available2012-09-20T08:12:21Z
 
dc.date.issued2012
 
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.
 
dc.description.naturelink_to_OA_fulltext
 
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.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-254 [How to Cite?]
DOI: http://dx.doi.org/10.1145/2312005.2312050
 
dc.identifier.doihttp://dx.doi.org/10.1145/2312005.2312050
 
dc.identifier.epage254
 
dc.identifier.hkuros206264
 
dc.identifier.issn978-1-4503-1213-4
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-84864126527
 
dc.identifier.spage246
 
dc.identifier.urihttp://hdl.handle.net/10722/164910
 
dc.languageeng
 
dc.publisherAssociation for Computing Machinery.
 
dc.publisher.placeUnited States
 
dc.relation.ispartofAnnual ACM Symposium on Parallelism in Algorithms and Architectures
 
dc.relation.referencesReferences in Scopus
 
dc.rightsProceedinbgs of the 24th ACM Symposium on Parallelism in Algorithms and Architectures. Copyright © Association for Computing Machinery.
 
dc.subjectCompetitive analysis
 
dc.subjectNonclairvoyant scheduling
 
dc.subjectOnline scheduling
 
dc.subjectRejection penalty
 
dc.subjectWeighted flow time
 
dc.titleNon-clairvoyant weighted flow time scheduling with rejection penalty
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chan, HL</contributor.author>
<contributor.author>Chan, SH</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Lee, LK</contributor.author>
<contributor.author>Zhu, J</contributor.author>
<date.accessioned>2012-09-20T08:12:21Z</date.accessioned>
<date.available>2012-09-20T08:12:21Z</date.available>
<date.issued>2012</date.issued>
<identifier.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</identifier.citation>
<identifier.issn>978-1-4503-1213-4</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/164910</identifier.uri>
<description.abstract>This 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 + &#949;)-speed for any &#949; &gt; 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.</description.abstract>
<language>eng</language>
<publisher>Association for Computing Machinery.</publisher>
<relation.ispartof>Annual ACM Symposium on Parallelism in Algorithms and Architectures</relation.ispartof>
<rights>Proceedinbgs of the 24th ACM Symposium on Parallelism in Algorithms and Architectures. Copyright &#169; Association for Computing Machinery.</rights>
<subject>Competitive analysis</subject>
<subject>Nonclairvoyant scheduling</subject>
<subject>Online scheduling</subject>
<subject>Rejection penalty</subject>
<subject>Weighted flow time</subject>
<title>Non-clairvoyant weighted flow time scheduling with rejection penalty</title>
<type>Conference_Paper</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=978-1-4503-1213-4&amp;volume=&amp;spage=246&amp;epage=254&amp;date=2012&amp;atitle=Non-clairvoyant+weighted+flow+time+scheduling+with+rejection+penalty</identifier.openurl>
<description.nature>link_to_OA_fulltext</description.nature>
<identifier.doi>10.1145/2312005.2312050</identifier.doi>
<identifier.scopus>eid_2-s2.0-84864126527</identifier.scopus>
<identifier.hkuros>206264</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-84864126527&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.spage>246</identifier.spage>
<identifier.epage>254</identifier.epage>
<publisher.place>United States</publisher.place>
<description.other>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</description.other>
<bitstream.url>http://hub.hku.hk/bitstream/10722/164910/1/re01.htm</bitstream.url>
</item>
Author Affiliations
  1. The University of Hong Kong