File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Scheduling for weighted flow time and energy with rejection penalty

TitleScheduling for weighted flow time and energy with rejection penalty
Authors
KeywordsOnline scheduling
Weighted flow time
Rejection penalty
Speed scaling
Issue Date2011
PublisherLIPICS.
Citation
The 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Tu Dortmund, Germany, 10-12 March 2011. In Proceedings of the 28th STACS, 2011, v. 9, p. 392-403 How to Cite?
AbstractThis paper revisits the online problem of flow-time 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 max-min 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 above-mentioned 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]).
DescriptionSession 8A (E23) - Scheduling 1
Persistent Identifierhttp://hdl.handle.net/10722/139979
ISBN

 

DC FieldValueLanguage
dc.contributor.authorChan, SHen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorLee, LKen_US
dc.date.accessioned2011-09-23T06:04:20Z-
dc.date.available2011-09-23T06:04:20Z-
dc.date.issued2011en_US
dc.identifier.citationThe 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Tu Dortmund, Germany, 10-12 March 2011. In Proceedings of the 28th STACS, 2011, v. 9, p. 392-403en_US
dc.identifier.isbn978-3-939897-25-5en_US
dc.identifier.urihttp://hdl.handle.net/10722/139979-
dc.descriptionSession 8A (E23) - Scheduling 1-
dc.description.abstractThis paper revisits the online problem of flow-time 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 max-min 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 above-mentioned 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.languageengen_US
dc.publisherLIPICS.en_US
dc.relation.ispartofProceedings of the International Symposium on Theoretical Aspects of Computer Science, STACS 2011en_US
dc.subjectOnline scheduling-
dc.subjectWeighted flow time-
dc.subjectRejection penalty-
dc.subjectSpeed scaling-
dc.titleScheduling for weighted flow time and energy with rejection penaltyen_US
dc.typeConference_Paperen_US
dc.identifier.emailChan, SH: shchan@cs.hku.hken_US
dc.identifier.emailLam, TW: twlam@cs.hku.hk-
dc.identifier.emailLee, LK: lklee@mpi-inf.mpg.de-
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.4230/LIPIcs.STACS.2011.392-
dc.identifier.hkuros192197en_US
dc.identifier.volume9en_US
dc.identifier.spage392en_US
dc.identifier.epage403en_US
dc.description.otherThe 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Tu Dortmund, Germany, 10-12 March 2011. In Proceedings of the 28th STACS, 2011, v. 9, p. 392-403-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats