Supplementary

Citations:
 Appears in Collections:
Conference Paper: Scheduling for weighted flow time and energy with rejection penalty
Title  Scheduling for weighted flow time and energy with rejection penalty 

Authors  
Keywords  Online scheduling Weighted flow time Rejection penalty Speed scaling 
Issue Date  2011 
Publisher  LIPICS. 
Citation  The 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Tu Dortmund, Germany, 1012 March 2011. In Proceedings of the 28th STACS, 2011, v. 9, p. 392403 How to Cite? 
Abstract  This paper revisits the online problem of flowtime scheduling on a single processor when jobs can be rejected at some penalty [4]. 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. For jobs with arbitrary weights and arbitrary penalties, Bansal et al. [4] gave an online algorithm that is O((logW + log C)2)competitive for minimizing the total user cost when using a slightly faster processor, where W and C are the maxmin ratios of job weights and job penalties, respectively. In this paper we improve this result with a new algorithm that can achieve a constant competitive ratio independent of W and C when using a slightly faster processor. Note that 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 a cubic or any increasing function of speed. A scheduling algorithm has to control job admission and determine the order and speed of job execution. This paper studies the tradeoff between the abovementioned user cost and energy, and it shows two O(1)competitive algorithms and a lower bound result on minimizing the user cost plus energy. These algorithms can also be regarded as a generalization of the recent work on minimizing flow time plus energy when all jobs must be completed (see the survey paper [1]). 
Description  Session 8A (E23)  Scheduling 1 
Persistent Identifier  http://hdl.handle.net/10722/139979 
ISBN 
DC Field  Value  Language 

dc.contributor.author  Chan, SH  en_US 
dc.contributor.author  Lam, TW  en_US 
dc.contributor.author  Lee, LK  en_US 
dc.date.accessioned  20110923T06:04:20Z   
dc.date.available  20110923T06:04:20Z   
dc.date.issued  2011  en_US 
dc.identifier.citation  The 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Tu Dortmund, Germany, 1012 March 2011. In Proceedings of the 28th STACS, 2011, v. 9, p. 392403  en_US 
dc.identifier.isbn  9783939897255  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/139979   
dc.description  Session 8A (E23)  Scheduling 1   
dc.description.abstract  This paper revisits the online problem of flowtime scheduling on a single processor when jobs can be rejected at some penalty [4]. 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. For jobs with arbitrary weights and arbitrary penalties, Bansal et al. [4] gave an online algorithm that is O((logW + log C)2)competitive for minimizing the total user cost when using a slightly faster processor, where W and C are the maxmin ratios of job weights and job penalties, respectively. In this paper we improve this result with a new algorithm that can achieve a constant competitive ratio independent of W and C when using a slightly faster processor. Note that 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 a cubic or any increasing function of speed. A scheduling algorithm has to control job admission and determine the order and speed of job execution. This paper studies the tradeoff between the abovementioned user cost and energy, and it shows two O(1)competitive algorithms and a lower bound result on minimizing the user cost plus energy. These algorithms can also be regarded as a generalization of the recent work on minimizing flow time plus energy when all jobs must be completed (see the survey paper [1]).   
dc.language  eng  en_US 
dc.publisher  LIPICS.  en_US 
dc.relation.ispartof  Proceedings of the International Symposium on Theoretical Aspects of Computer Science, STACS 2011  en_US 
dc.subject  Online scheduling   
dc.subject  Weighted flow time   
dc.subject  Rejection penalty   
dc.subject  Speed scaling   
dc.title  Scheduling for weighted flow time and energy with rejection penalty  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Chan, SH: shchan@cs.hku.hk  en_US 
dc.identifier.email  Lam, TW: twlam@cs.hku.hk   
dc.identifier.email  Lee, LK: lklee@mpiinf.mpg.de   
dc.identifier.authority  Lam, TW=rp00135  en_US 
dc.description.nature  link_to_OA_fulltext   
dc.identifier.doi  10.4230/LIPIcs.STACS.2011.392   
dc.identifier.hkuros  192197  en_US 
dc.identifier.volume  9  en_US 
dc.identifier.spage  392  en_US 
dc.identifier.epage  403  en_US 
dc.description.other  The 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Tu Dortmund, Germany, 1012 March 2011. In Proceedings of the 28th STACS, 2011, v. 9, p. 392403   