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

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • 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 Field
Value
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
Author Affiliations
  1. The University of Hong Kong