Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1145/2312005.2312050
 Scopus: eid_2s2.084864126527
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Nonclairvoyant weighted flow time scheduling with rejection penalty
Title  Nonclairvoyant weighted flow time scheduling with rejection penalty 

Authors  
Keywords  Competitive analysis Nonclairvoyant scheduling Online scheduling Rejection penalty Weighted flow time 
Issue Date  2012 
Publisher  Association for Computing Machinery. 
Citation  The 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), Pittsburgh, PA., 2527 June 2012. In Proceedinbgs of the 24th ACM SPAA, 2012, p. 246254 How to Cite? 
Abstract  This paper initiates the study of online scheduling with rejection penalty in the nonclairvoyant 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 singleprocessor setting [2, 8] and has produced O(1)competitive online algorithm for jobs with arbitrary weights and penalties. This paper gives the first nonclairvoyant algorithms that are O(1)competitive for minimizing the total user cost on a single processor and multiprocessors, 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 nonclairvoyant results on minimizing weighted flow time alone (WSETF [4] for a single pro cessor; WLAPS [14] for multiprocessors). 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 abovementioned user cost and energy. This paper gives two O(1)competitive nonclairvoyant algorithms for minimizing the user cost plus energy on a single processor and multiprocessors, respectively. Copyright 2012 ACM. 
Persistent Identifier  http://hdl.handle.net/10722/164910 
ISSN  
References 
DC Field  Value  Language 

dc.contributor.author  Chan, HL  en_HK 
dc.contributor.author  Chan, SH  en_HK 
dc.contributor.author  Lam, TW  en_HK 
dc.contributor.author  Lee, LK  en_HK 
dc.contributor.author  Zhu, J  en_HK 
dc.date.accessioned  20120920T08:12:21Z   
dc.date.available  20120920T08:12:21Z   
dc.date.issued  2012  en_HK 
dc.identifier.citation  The 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), Pittsburgh, PA., 2527 June 2012. In Proceedinbgs of the 24th ACM SPAA, 2012, p. 246254  en_US 
dc.identifier.issn  9781450312134  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/164910   
dc.description.abstract  This paper initiates the study of online scheduling with rejection penalty in the nonclairvoyant 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 singleprocessor setting [2, 8] and has produced O(1)competitive online algorithm for jobs with arbitrary weights and penalties. This paper gives the first nonclairvoyant algorithms that are O(1)competitive for minimizing the total user cost on a single processor and multiprocessors, 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 nonclairvoyant results on minimizing weighted flow time alone (WSETF [4] for a single pro cessor; WLAPS [14] for multiprocessors). 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 abovementioned user cost and energy. This paper gives two O(1)competitive nonclairvoyant algorithms for minimizing the user cost plus energy on a single processor and multiprocessors, respectively. Copyright 2012 ACM.  en_HK 
dc.language  eng  en_US 
dc.publisher  Association for Computing Machinery.  en_US 
dc.relation.ispartof  Annual ACM Symposium on Parallelism in Algorithms and Architectures  en_HK 
dc.rights  Proceedinbgs of the 24th ACM Symposium on Parallelism in Algorithms and Architectures. Copyright © Association for Computing Machinery.   
dc.subject  Competitive analysis  en_HK 
dc.subject  Nonclairvoyant scheduling  en_HK 
dc.subject  Online scheduling  en_HK 
dc.subject  Rejection penalty  en_HK 
dc.subject  Weighted flow time  en_HK 
dc.title  Nonclairvoyant weighted flow time scheduling with rejection penalty  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=9781450312134&volume=&spage=246&epage=254&date=2012&atitle=Nonclairvoyant+weighted+flow+time+scheduling+with+rejection+penalty  en_US 
dc.identifier.email  Lam, TW: hresltk@hkucc.hku.hk  en_HK 
dc.identifier.email  Lee, LK: lklee@cs.hku.hk  en_HK 
dc.identifier.authority  Lam, TW=rp00135  en_HK 
dc.identifier.authority  Lee, LK=rp00140  en_HK 
dc.description.nature  link_to_OA_fulltext   
dc.identifier.doi  10.1145/2312005.2312050  en_HK 
dc.identifier.scopus  eid_2s2.084864126527  en_HK 
dc.identifier.hkuros  206264  en_US 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.084864126527&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.spage  246  en_HK 
dc.identifier.epage  254  en_HK 
dc.publisher.place  United States   
dc.description.other  The 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), Pittsburgh, PA., 2527 June 2012. In Proceedinbgs of the 24th ACM SPAA, 2012, p. 246254   
dc.identifier.scopusauthorid  Chan, HL=55171146200  en_HK 
dc.identifier.scopusauthorid  Chan, SH=36652336600  en_HK 
dc.identifier.scopusauthorid  Lam, TW=7202523165  en_HK 
dc.identifier.scopusauthorid  Lee, LK=12646190100  en_HK 
dc.identifier.scopusauthorid  Zhu, J=55170440000  en_HK 