[{"page":"128-137","citation":{"mla":"Brinkmann, Andre, et al. “Scheduling Shared Continuous Resources on Many-Cores.” <i>Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2014, pp. 128–37, doi:<a href=\"https://doi.org/10.1145/2612669.2612698\">10.1145/2612669.2612698</a>.","bibtex":"@inproceedings{Brinkmann_Kling_Meyer auf der Heide_Nagel_Riechers_Suess_2014, title={Scheduling Shared Continuous Resources on Many-Cores}, DOI={<a href=\"https://doi.org/10.1145/2612669.2612698\">10.1145/2612669.2612698</a>}, booktitle={Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, author={Brinkmann, Andre and Kling, Peter and Meyer auf der Heide, Friedhelm and Nagel, Lars and Riechers, Sören and Suess, Tim }, year={2014}, pages={128–137} }","short":"A. Brinkmann, P. Kling, F. Meyer auf der Heide, L. Nagel, S. Riechers, T. Suess, in: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2014, pp. 128–137.","apa":"Brinkmann, A., Kling, P., Meyer auf der Heide, F., Nagel, L., Riechers, S., &#38; Suess, T. (2014). Scheduling Shared Continuous Resources on Many-Cores. <i>Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 128–137. <a href=\"https://doi.org/10.1145/2612669.2612698\">https://doi.org/10.1145/2612669.2612698</a>","chicago":"Brinkmann, Andre, Peter Kling, Friedhelm Meyer auf der Heide, Lars Nagel, Sören Riechers, and Tim  Suess. “Scheduling Shared Continuous Resources on Many-Cores.” In <i>Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 128–37, 2014. <a href=\"https://doi.org/10.1145/2612669.2612698\">https://doi.org/10.1145/2612669.2612698</a>.","ieee":"A. Brinkmann, P. Kling, F. Meyer auf der Heide, L. Nagel, S. Riechers, and T. Suess, “Scheduling Shared Continuous Resources on Many-Cores,” in <i>Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2014, pp. 128–137, doi: <a href=\"https://doi.org/10.1145/2612669.2612698\">10.1145/2612669.2612698</a>.","ama":"Brinkmann A, Kling P, Meyer auf der Heide F, Nagel L, Riechers S, Suess T. Scheduling Shared Continuous Resources on Many-Cores. In: <i>Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. ; 2014:128-137. doi:<a href=\"https://doi.org/10.1145/2612669.2612698\">10.1145/2612669.2612698</a>"},"year":"2014","has_accepted_license":"1","doi":"10.1145/2612669.2612698","title":"Scheduling Shared Continuous Resources on Many-Cores","author":[{"first_name":"Andre","last_name":"Brinkmann","full_name":"Brinkmann, Andre"},{"last_name":"Kling","full_name":"Kling, Peter","first_name":"Peter"},{"first_name":"Friedhelm","full_name":"Meyer auf der Heide, Friedhelm","id":"15523","last_name":"Meyer auf der Heide"},{"last_name":"Nagel","full_name":"Nagel, Lars","first_name":"Lars"},{"last_name":"Riechers","full_name":"Riechers, Sören","first_name":"Sören"},{"first_name":"Tim ","last_name":"Suess","full_name":"Suess, Tim "}],"date_created":"2017-10-17T12:42:03Z","date_updated":"2022-01-06T06:59:30Z","status":"public","file":[{"date_updated":"2018-03-20T07:17:38Z","creator":"florida","date_created":"2018-03-20T07:17:38Z","file_size":485767,"file_id":"1403","access_level":"closed","file_name":"368-BKMNRS14.pdf","content_type":"application/pdf","success":1,"relation":"main_file"}],"abstract":[{"text":"We consider the problem of scheduling a number of jobs on $m$ identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement r_j \\in {0,1}. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their \\emph{processing speeds}, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.In this paper, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include an efficient optimal algorithm for 2 processors. Moreover, we prove that balanced schedules yield a 2-1/m-approximation for a fixed number of processors. Such schedules are computed by our GreedyBalance algorithm, for which the bound is tight.","lang":"eng"}],"publication":"Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","type":"conference","file_date_updated":"2018-03-20T07:17:38Z","language":[{"iso":"eng"}],"ddc":["040"],"department":[{"_id":"63"}],"user_id":"15415","_id":"368","project":[{"_id":"1","name":"SFB 901"},{"_id":"16","name":"SFB 901 - Subprojekt C4"},{"_id":"14","name":"SFB 901 - Subproject C2"},{"_id":"4","name":"SFB 901 - Project Area C"}]},{"publication":"Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)","type":"conference","abstract":[{"text":"We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analysed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.","lang":"eng"}],"editor":[{"first_name":"Ron","last_name":"Lavi","full_name":"Lavi, Ron"}],"status":"public","file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2018-03-16T11:25:10Z","date_created":"2018-03-16T11:25:10Z","creator":"florida","file_size":283266,"file_name":"451-DRS14.pdf","access_level":"closed","file_id":"1344"}],"_id":"451","project":[{"_id":"1","name":"SFB 901"},{"_id":"14","name":"SFB 901 - Subproject C2"},{"_id":"16","name":"SFB 901 - Subproject C4"},{"name":"SFB 901 - Subproject A3","_id":"7"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"4","name":"SFB 901 - Project Area C"}],"department":[{"_id":"63"},{"_id":"541"}],"series_title":"Lecture Notes in Computer Science","user_id":"477","ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-16T11:25:10Z","has_accepted_license":"1","year":"2014","page":"110-121","citation":{"bibtex":"@inproceedings{Drees_Riechers_Skopalik_2014, series={Lecture Notes in Computer Science}, title={Budget-restricted utility games with ordered strategic decisions}, DOI={<a href=\"https://doi.org/10.1007/978-3-662-44803-8_10\">10.1007/978-3-662-44803-8_10</a>}, booktitle={Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)}, author={Drees, Maximilian and Riechers, Sören and Skopalik, Alexander}, editor={Lavi, RonEditor}, year={2014}, pages={110–121}, collection={Lecture Notes in Computer Science} }","short":"M. Drees, S. Riechers, A. Skopalik, in: R. Lavi (Ed.), Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT), 2014, pp. 110–121.","mla":"Drees, Maximilian, et al. “Budget-Restricted Utility Games with Ordered Strategic Decisions.” <i>Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)</i>, edited by Ron Lavi, 2014, pp. 110–21, doi:<a href=\"https://doi.org/10.1007/978-3-662-44803-8_10\">10.1007/978-3-662-44803-8_10</a>.","apa":"Drees, M., Riechers, S., &#38; Skopalik, A. (2014). Budget-restricted utility games with ordered strategic decisions. In R. Lavi (Ed.), <i>Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)</i> (pp. 110–121). <a href=\"https://doi.org/10.1007/978-3-662-44803-8_10\">https://doi.org/10.1007/978-3-662-44803-8_10</a>","ama":"Drees M, Riechers S, Skopalik A. Budget-restricted utility games with ordered strategic decisions. In: Lavi R, ed. <i>Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)</i>. Lecture Notes in Computer Science. ; 2014:110-121. doi:<a href=\"https://doi.org/10.1007/978-3-662-44803-8_10\">10.1007/978-3-662-44803-8_10</a>","ieee":"M. Drees, S. Riechers, and A. Skopalik, “Budget-restricted utility games with ordered strategic decisions,” in <i>Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)</i>, 2014, pp. 110–121.","chicago":"Drees, Maximilian, Sören Riechers, and Alexander Skopalik. “Budget-Restricted Utility Games with Ordered Strategic Decisions.” In <i>Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)</i>, edited by Ron Lavi, 110–21. Lecture Notes in Computer Science, 2014. <a href=\"https://doi.org/10.1007/978-3-662-44803-8_10\">https://doi.org/10.1007/978-3-662-44803-8_10</a>."},"date_updated":"2022-01-06T07:01:07Z","author":[{"full_name":"Drees, Maximilian","last_name":"Drees","first_name":"Maximilian"},{"last_name":"Riechers","full_name":"Riechers, Sören","first_name":"Sören"},{"first_name":"Alexander","full_name":"Skopalik, Alexander","id":"40384","last_name":"Skopalik"}],"date_created":"2017-10-17T12:42:20Z","title":"Budget-restricted utility games with ordered strategic decisions","doi":"10.1007/978-3-662-44803-8_10"},{"publication":"Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)","type":"conference","abstract":[{"text":"We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds.Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem.","lang":"eng"}],"status":"public","file":[{"file_name":"435-Kling_C2_STACS2014.pdf","file_id":"1354","access_level":"closed","file_size":525851,"date_created":"2018-03-16T11:30:23Z","creator":"florida","date_updated":"2018-03-16T11:30:23Z","relation":"main_file","success":1,"content_type":"application/pdf"}],"_id":"435","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt C4","_id":"16"},{"name":"SFB 901 - Subproject C2","_id":"14"},{"name":"SFB 901 - Project Area C","_id":"4"}],"department":[{"_id":"63"}],"series_title":"LIPIcs","user_id":"477","ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-16T11:30:23Z","has_accepted_license":"1","year":"2014","page":"63--74","citation":{"mla":"Antoniadis, Antonios, et al. “Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules.” <i>Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)</i>, 2014, pp. 63--74, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2014.63\">10.4230/LIPIcs.STACS.2014.63</a>.","bibtex":"@inproceedings{Antoniadis_Barcelo_Consuegra_Kling_Nugent_Pruhs_Scquizzato_2014, series={LIPIcs}, title={Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2014.63\">10.4230/LIPIcs.STACS.2014.63</a>}, booktitle={Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)}, author={Antoniadis, Antonios and Barcelo, Neal and Consuegra, Mario and Kling, Peer and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele}, year={2014}, pages={63--74}, collection={LIPIcs} }","short":"A. Antoniadis, N. Barcelo, M. Consuegra, P. Kling, M. Nugent, K. Pruhs, M. Scquizzato, in: Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS), 2014, pp. 63--74.","apa":"Antoniadis, A., Barcelo, N., Consuegra, M., Kling, P., Nugent, M., Pruhs, K., &#38; Scquizzato, M. (2014). Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. In <i>Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)</i> (pp. 63--74). <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2014.63\">https://doi.org/10.4230/LIPIcs.STACS.2014.63</a>","ama":"Antoniadis A, Barcelo N, Consuegra M, et al. Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. In: <i>Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)</i>. LIPIcs. ; 2014:63--74. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2014.63\">10.4230/LIPIcs.STACS.2014.63</a>","chicago":"Antoniadis, Antonios, Neal Barcelo, Mario Consuegra, Peer Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. “Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules.” In <i>Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)</i>, 63--74. LIPIcs, 2014. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2014.63\">https://doi.org/10.4230/LIPIcs.STACS.2014.63</a>.","ieee":"A. Antoniadis <i>et al.</i>, “Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules,” in <i>Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)</i>, 2014, pp. 63--74."},"date_updated":"2022-01-06T07:00:58Z","date_created":"2017-10-17T12:42:16Z","author":[{"full_name":"Antoniadis, Antonios","last_name":"Antoniadis","first_name":"Antonios"},{"first_name":"Neal","last_name":"Barcelo","full_name":"Barcelo, Neal"},{"first_name":"Mario","last_name":"Consuegra","full_name":"Consuegra, Mario"},{"full_name":"Kling, Peer","last_name":"Kling","first_name":"Peer"},{"full_name":"Nugent, Michael","last_name":"Nugent","first_name":"Michael"},{"first_name":"Kirk","last_name":"Pruhs","full_name":"Pruhs, Kirk"},{"last_name":"Scquizzato","full_name":"Scquizzato, Michele","first_name":"Michele"}],"title":"Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules","doi":"10.4230/LIPIcs.STACS.2014.63"},{"ddc":["040"],"language":[{"iso":"eng"}],"file_date_updated":"2018-03-15T13:40:02Z","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subproject C4","_id":"16"},{"name":"SFB 901 - Subproject C2","_id":"14"},{"_id":"4","name":"SFB 901 - Project Area C"}],"_id":"499","user_id":"477","department":[{"_id":"63"}],"abstract":[{"lang":"eng","text":"We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors.Moreover, we provide a tight analysis of the algorithm's competitiveness.Our results generalize and improve upon work by \\citet{Chan:2010}, which considers a single speed-scalable processor.Using significantly different techniques, we can not only extend their model to multiprocessors but also prove an enhanced and tight competitive ratio for our algorithm.In our scheduling problem, jobs arrive over time and are preemptable.They have different workloads, values, and deadlines.The scheduler may decide not to finish a job but instead to suffer a loss equaling the job's value.However, to process a job's workload until its deadline the scheduler must invest a certain amount of energy.The cost of a schedule is the sum of lost values and invested energy.In order to finish a job the scheduler has to determine which processors to use and set their speeds accordingly.A processor's energy consumption is power $\\Power{s}$ integrated over time, where $\\Power{s}=s^{\\alpha}$ is the power consumption when running at speed $s$.Since we consider the online variant of the problem, the scheduler has no knowledge about future jobs.This problem was introduced by~\\citet{Chan:2010} for the case of a single processor.They presented an online algorithm which is $\\alpha^{\\alpha}+2e\\alpha$-competitive.We provide an online algorithm for the case of multiple processors with an improved competitive ratio of $\\alpha^{\\alpha}$."}],"file":[{"creator":"florida","date_created":"2018-03-15T13:40:02Z","date_updated":"2018-03-15T13:40:02Z","file_name":"499-P._Kling__P._Pietryzk_-_Profitable_Scheduling_on_Multiple_Speed-scalable_Processors__2013_.pdf","file_id":"1310","access_level":"closed","file_size":558661,"content_type":"application/pdf","relation":"main_file","success":1}],"status":"public","type":"conference","publication":"Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","title":"Profitable Scheduling on Multiple Speed-Scalable Processors","doi":"10.1145/2486159.2486183","date_updated":"2022-01-06T07:01:34Z","author":[{"last_name":"Kling","full_name":"Kling, Peter","first_name":"Peter"},{"first_name":"Peter","last_name":"Pietrzyk","full_name":"Pietrzyk, Peter"}],"date_created":"2017-10-17T12:42:29Z","year":"2013","citation":{"bibtex":"@inproceedings{Kling_Pietrzyk_2013, title={Profitable Scheduling on Multiple Speed-Scalable Processors}, DOI={<a href=\"https://doi.org/10.1145/2486159.2486183\">10.1145/2486159.2486183</a>}, booktitle={Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, author={Kling, Peter and Pietrzyk, Peter}, year={2013}, pages={251–260} }","short":"P. Kling, P. Pietrzyk, in: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013, pp. 251–260.","mla":"Kling, Peter, and Peter Pietrzyk. “Profitable Scheduling on Multiple Speed-Scalable Processors.” <i>Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2013, pp. 251–60, doi:<a href=\"https://doi.org/10.1145/2486159.2486183\">10.1145/2486159.2486183</a>.","apa":"Kling, P., &#38; Pietrzyk, P. (2013). Profitable Scheduling on Multiple Speed-Scalable Processors. In <i>Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i> (pp. 251–260). <a href=\"https://doi.org/10.1145/2486159.2486183\">https://doi.org/10.1145/2486159.2486183</a>","ama":"Kling P, Pietrzyk P. Profitable Scheduling on Multiple Speed-Scalable Processors. In: <i>Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. ; 2013:251-260. doi:<a href=\"https://doi.org/10.1145/2486159.2486183\">10.1145/2486159.2486183</a>","ieee":"P. Kling and P. Pietrzyk, “Profitable Scheduling on Multiple Speed-Scalable Processors,” in <i>Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2013, pp. 251–260.","chicago":"Kling, Peter, and Peter Pietrzyk. “Profitable Scheduling on Multiple Speed-Scalable Processors.” In <i>Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 251–60, 2013. <a href=\"https://doi.org/10.1145/2486159.2486183\">https://doi.org/10.1145/2486159.2486183</a>."},"page":"251-260 ","has_accepted_license":"1"},{"doi":"10.1007/978-3-642-34862-4_17","title":"Slow Down & Sleep for Profit in Online Deadline Scheduling","author":[{"last_name":"Cord-Landwehr","full_name":"Cord-Landwehr, Andreas","first_name":"Andreas"},{"full_name":"Kling, Peter","last_name":"Kling","first_name":"Peter"},{"full_name":"Mallmann Trenn, Fredrik","last_name":"Mallmann Trenn","first_name":"Fredrik"}],"date_created":"2017-10-17T12:42:45Z","date_updated":"2022-01-06T07:02:42Z","citation":{"apa":"Cord-Landwehr, A., Kling, P., &#38; Mallmann Trenn, F. (2012). Slow Down &#38; Sleep for Profit in Online Deadline Scheduling. In G. Even &#38; D. Rawitz (Eds.), <i>Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)</i> (pp. 218–231). <a href=\"https://doi.org/10.1007/978-3-642-34862-4_17\">https://doi.org/10.1007/978-3-642-34862-4_17</a>","bibtex":"@inproceedings{Cord-Landwehr_Kling_Mallmann Trenn_2012, series={LNCS}, title={Slow Down &#38; Sleep for Profit in Online Deadline Scheduling}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-34862-4_17\">10.1007/978-3-642-34862-4_17</a>}, 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} }","mla":"Cord-Landwehr, Andreas, et al. “Slow Down &#38; Sleep for Profit in Online Deadline Scheduling.” <i>Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)</i>, edited by Guy Even and Dror Rawitz, 2012, pp. 218–31, doi:<a href=\"https://doi.org/10.1007/978-3-642-34862-4_17\">10.1007/978-3-642-34862-4_17</a>.","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.","ama":"Cord-Landwehr A, Kling P, Mallmann Trenn F. Slow Down &#38; Sleep for Profit in Online Deadline Scheduling. In: Even G, Rawitz D, eds. <i>Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)</i>. LNCS. ; 2012:218-231. doi:<a href=\"https://doi.org/10.1007/978-3-642-34862-4_17\">10.1007/978-3-642-34862-4_17</a>","ieee":"A. Cord-Landwehr, P. Kling, and F. Mallmann Trenn, “Slow Down &#38; Sleep for Profit in Online Deadline Scheduling,” in <i>Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)</i>, 2012, pp. 218–231.","chicago":"Cord-Landwehr, Andreas, Peter Kling, and Fredrik Mallmann Trenn. “Slow Down &#38; Sleep for Profit in Online Deadline Scheduling.” In <i>Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)</i>, edited by Guy Even and Dror Rawitz, 218–31. LNCS, 2012. <a href=\"https://doi.org/10.1007/978-3-642-34862-4_17\">https://doi.org/10.1007/978-3-642-34862-4_17</a>."},"page":"218-231","year":"2012","has_accepted_license":"1","language":[{"iso":"eng"}],"file_date_updated":"2018-03-15T09:03:39Z","ddc":["040"],"series_title":"LNCS","user_id":"477","department":[{"_id":"63"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt C2","_id":"14"},{"_id":"16","name":"SFB 901 - Subproject C4"},{"_id":"4","name":"SFB 901 - Project Area C"}],"_id":"580","file":[{"file_size":325939,"access_level":"closed","file_id":"1265","file_name":"580-P._Kling__F._Mallmann-Trenn__A._Cord-Landwehr_-_Slow_Down___Sleep_for_Profit_in_Online_Deadline_Scheduling.pdf","date_updated":"2018-03-15T09:03:39Z","date_created":"2018-03-15T09:03:39Z","creator":"florida","success":1,"relation":"main_file","content_type":"application/pdf"}],"status":"public","editor":[{"last_name":"Even","full_name":"Even, Guy","first_name":"Guy"},{"first_name":"Dror","full_name":"Rawitz, Dror","last_name":"Rawitz"}],"abstract":[{"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.","lang":"eng"}],"type":"conference","publication":"Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)"},{"title":"An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment","doi":"10.1007/978-3-642-31500-8_4","date_updated":"2022-01-06T07:03:14Z","date_created":"2017-10-17T12:43:01Z","author":[{"first_name":"Joachim","last_name":"Gehweiler","full_name":"Gehweiler, Joachim"},{"first_name":"Peter","last_name":"Kling","full_name":"Kling, Peter"},{"last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm","first_name":"Friedhelm"}],"year":"2011","citation":{"bibtex":"@inproceedings{Gehweiler_Kling_Meyer auf der Heide_2011, series={LNCS}, title={An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment}, DOI={<a href=\"https://doi.org/10.1007/978-3-642-31500-8_4\">10.1007/978-3-642-31500-8_4</a>}, booktitle={Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)}, author={Gehweiler, Joachim and Kling, Peter and Meyer auf der Heide, Friedhelm}, year={2011}, pages={31--40}, collection={LNCS} }","short":"J. Gehweiler, P. Kling, F. Meyer auf der Heide, in: Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM), 2011, pp. 31--40.","mla":"Gehweiler, Joachim, et al. “An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment.” <i>Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)</i>, 2011, pp. 31--40, doi:<a href=\"https://doi.org/10.1007/978-3-642-31500-8_4\">10.1007/978-3-642-31500-8_4</a>.","apa":"Gehweiler, J., Kling, P., &#38; Meyer auf der Heide, F. (2011). An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment. In <i>Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)</i> (pp. 31--40). <a href=\"https://doi.org/10.1007/978-3-642-31500-8_4\">https://doi.org/10.1007/978-3-642-31500-8_4</a>","ama":"Gehweiler J, Kling P, Meyer auf der Heide F. An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment. In: <i>Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)</i>. LNCS. ; 2011:31--40. doi:<a href=\"https://doi.org/10.1007/978-3-642-31500-8_4\">10.1007/978-3-642-31500-8_4</a>","ieee":"J. Gehweiler, P. Kling, and F. Meyer auf der Heide, “An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment,” in <i>Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)</i>, 2011, pp. 31--40.","chicago":"Gehweiler, Joachim, Peter Kling, and Friedhelm Meyer auf der Heide. “An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment.” In <i>Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)</i>, 31--40. LNCS, 2011. <a href=\"https://doi.org/10.1007/978-3-642-31500-8_4\">https://doi.org/10.1007/978-3-642-31500-8_4</a>."},"page":"31--40","has_accepted_license":"1","ddc":["040"],"file_date_updated":"2018-03-14T13:45:57Z","project":[{"_id":"1","name":"SFB 901"},{"name":"SFB 901 - Subprojekt C4","_id":"16"},{"name":"SFB 901 - Subproject C2","_id":"14"},{"name":"SFB 901 - Project Area C","_id":"4"}],"_id":"664","series_title":"LNCS","user_id":"15504","department":[{"_id":"63"}],"abstract":[{"lang":"eng","text":"Web Computing is a variant of parallel computing where the idle times of PCs donated by worldwide distributed users are employed to execute parallel programs. The PUB-Web library developed by us supports this kind of usage of computing resources. A major problem for the efficient execution of such parallel programs is load balancing. In the Web Computing context, this problem becomes more difficult because of the dynamic behavior of the underlying \"parallel computer\": the set of available processors (donated PCs) as well as their availability (idle times) change over time in an unpredictable fashion.In this paper, we experimentally evaluate and compare load balancing algorithms in this scenario, namely a variant of the well-established Work Stealing algorithm and strategies based on a heterogeneous version of distributed hash-tables (DHHTs) introduced recently. In order to run a meaningful experimental evaluation, we employ, in addition to our Web Computing library PUB-Web, realistic data sets for the job input streams and for the dynamics of the availability of the resources.Our experimental evaluations suggest that Work Stealing is the better strategy if the number of processes ready to run matches the number of available processors. But a suitable variant of DHHTs outperforms Work Stealing if there are significantly more processes ready to run than available processors."}],"file":[{"access_level":"closed","file_id":"1216","file_name":"664-PPAM11GKM_01.pdf","file_size":333335,"date_created":"2018-03-14T13:45:57Z","creator":"florida","date_updated":"2018-03-14T13:45:57Z","relation":"main_file","success":1,"content_type":"application/pdf"}],"status":"public","type":"conference","publication":"Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics (PPAM)"}]