--- _id: '580' abstract: - lang: eng text: We present and study a new model for energy-aware and profit-oriented scheduling on a single processor.The processor features dynamic speed scaling as well as suspension to a sleep mode.Jobs arrive over time, are preemptable, and have different sizes, values, and deadlines.On the arrival of a new job, the scheduler may either accept or reject the job.Accepted jobs need a certain energy investment to be finished in time, while rejected jobs cause costs equal to their values.Here, power consumption at speed $s$ is given by $P(s)=s^{\alpha}+\beta$ and the energy investment is power integrated over time.Additionally, the scheduler may decide to suspend the processor to a sleep mode in which no energy is consumed, though awaking entails fixed transition costs $\gamma$.The objective is to minimize the total value of rejected jobs plus the total energy.Our model combines aspects from advanced energy conservation techniques (namely speed scaling and sleep states) and profit-oriented scheduling models.We show that \emph{rejection-oblivious} schedulers (whose rejection decisions are not based on former decisions) have – in contrast to the model without sleep states – an unbounded competitive ratio.It turns out that the jobs' value densities (the ratio between a job's value and its work) are crucial for the performance of such schedulers.We give an algorithm whose competitiveness nearly matches the lower bound w.r.t\text{.} the maximum value density.If the maximum value density is not too large, the competitiveness becomes $\alpha^{\alpha}+2e\alpha$.Also, we show that it suffices to restrict the value density of low-value jobs only.Using a technique from \cite{Chan:2010} we transfer our results to processors with a fixed maximum speed. author: - first_name: Andreas full_name: Cord-Landwehr, Andreas last_name: Cord-Landwehr - first_name: Peter full_name: Kling, Peter last_name: Kling - first_name: Fredrik full_name: Mallmann Trenn, Fredrik last_name: Mallmann Trenn citation: ama: 'Cord-Landwehr A, Kling P, Mallmann Trenn F. Slow Down & Sleep for Profit in Online Deadline Scheduling. In: Even G, Rawitz D, eds. Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg). LNCS. ; 2012:218-231. doi:10.1007/978-3-642-34862-4_17' apa: Cord-Landwehr, A., Kling, P., & Mallmann Trenn, F. (2012). Slow Down & Sleep for Profit in Online Deadline Scheduling. In G. Even & D. Rawitz (Eds.), Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg) (pp. 218–231). https://doi.org/10.1007/978-3-642-34862-4_17 bibtex: '@inproceedings{Cord-Landwehr_Kling_Mallmann Trenn_2012, series={LNCS}, title={Slow Down & Sleep for Profit in Online Deadline Scheduling}, DOI={10.1007/978-3-642-34862-4_17}, booktitle={Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)}, author={Cord-Landwehr, Andreas and Kling, Peter and Mallmann Trenn, Fredrik}, editor={Even, Guy and Rawitz, DrorEditors}, year={2012}, pages={218–231}, collection={LNCS} }' chicago: Cord-Landwehr, Andreas, Peter Kling, and Fredrik Mallmann Trenn. “Slow Down & Sleep for Profit in Online Deadline Scheduling.” In Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), edited by Guy Even and Dror Rawitz, 218–31. LNCS, 2012. https://doi.org/10.1007/978-3-642-34862-4_17. ieee: A. Cord-Landwehr, P. Kling, and F. Mallmann Trenn, “Slow Down & Sleep for Profit in Online Deadline Scheduling,” in Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), 2012, pp. 218–231. mla: Cord-Landwehr, Andreas, et al. “Slow Down & Sleep for Profit in Online Deadline Scheduling.” Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), edited by Guy Even and Dror Rawitz, 2012, pp. 218–31, doi:10.1007/978-3-642-34862-4_17. short: 'A. Cord-Landwehr, P. Kling, F. Mallmann Trenn, in: G. Even, D. Rawitz (Eds.), Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), 2012, pp. 218–231.' date_created: 2017-10-17T12:42:45Z date_updated: 2022-01-06T07:02:42Z ddc: - '040' department: - _id: '63' doi: 10.1007/978-3-642-34862-4_17 editor: - first_name: Guy full_name: Even, Guy last_name: Even - first_name: Dror full_name: Rawitz, Dror last_name: Rawitz file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-15T09:03:39Z date_updated: 2018-03-15T09:03:39Z file_id: '1265' file_name: 580-P._Kling__F._Mallmann-Trenn__A._Cord-Landwehr_-_Slow_Down___Sleep_for_Profit_in_Online_Deadline_Scheduling.pdf file_size: 325939 relation: main_file success: 1 file_date_updated: 2018-03-15T09:03:39Z has_accepted_license: '1' language: - iso: eng page: 218-231 project: - _id: '1' name: SFB 901 - _id: '14' name: SFB 901 - Subprojekt C2 - _id: '16' name: SFB 901 - Subproject C4 - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg) series_title: LNCS status: public title: Slow Down & Sleep for Profit in Online Deadline Scheduling type: conference user_id: '477' year: '2012' ...