Non-preemptive speed scaling. Antoniadis, A. & Huang, C. *Journal of Scheduling*, 16(4):385--394, August, 2013. Paper doi abstract bibtex We consider the following offline variant of the speed scaling problem introduced by Yao et al. We are given a set of jobs and we have a variable-speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. In contrast to Yao et al., no preemption of jobs is allowed. Unlike the preemptive version that is known to be in P, the non-preemptive version of speed scaling is strongly NP-hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unrelated machine scheduling problem with LpL_p -norm objective.

@article{antoniadis_non-preemptive_2013,
title = {Non-preemptive speed scaling},
volume = {16},
issn = {1094-6136, 1099-1425},
url = {http://link.springer.com/article/10.1007/s10951-013-0312-6},
doi = {10.1007/s10951-013-0312-6},
abstract = {We consider the following offline variant of the speed scaling problem introduced by Yao et al. We are given a set of jobs and we have a variable-speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. In contrast to Yao et al., no preemption of jobs is allowed. Unlike the preemptive version that is known to be in P, the non-preemptive version of speed scaling is strongly NP-hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unrelated machine scheduling problem with LpL\_p -norm objective.},
language = {en},
number = {4},
urldate = {2014-09-30TZ},
journal = {Journal of Scheduling},
author = {Antoniadis, Antonios and Huang, Chien-Chung},
month = aug,
year = {2013},
keywords = {Artificial Intelligence (incl. Robotics), Calculus of Variations and Optimal Control; Optimization, Energy-efficient scheduling, Non-preemption, Operations Research/Decision Theory, Production/Logistics/Supply Chain, approximation algorithms, optimization},
pages = {385--394}
}

Downloads: 0

{"_id":"CA5G8n4YbevEfBrxh","bibbaseid":"antoniadis-huang-nonpreemptivespeedscaling-2013","downloads":0,"creationDate":"2016-12-19T20:50:58.271Z","title":"Non-preemptive speed scaling","author_short":["Antoniadis, A.","Huang, C."],"year":2013,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"Non-preemptive speed scaling","volume":"16","issn":"1094-6136, 1099-1425","url":"http://link.springer.com/article/10.1007/s10951-013-0312-6","doi":"10.1007/s10951-013-0312-6","abstract":"We consider the following offline variant of the speed scaling problem introduced by Yao et al. We are given a set of jobs and we have a variable-speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. In contrast to Yao et al., no preemption of jobs is allowed. Unlike the preemptive version that is known to be in P, the non-preemptive version of speed scaling is strongly NP-hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unrelated machine scheduling problem with LpL_p -norm objective.","language":"en","number":"4","urldate":"2014-09-30TZ","journal":"Journal of Scheduling","author":[{"propositions":[],"lastnames":["Antoniadis"],"firstnames":["Antonios"],"suffixes":[]},{"propositions":[],"lastnames":["Huang"],"firstnames":["Chien-Chung"],"suffixes":[]}],"month":"August","year":"2013","keywords":"Artificial Intelligence (incl. Robotics), Calculus of Variations and Optimal Control; Optimization, Energy-efficient scheduling, Non-preemption, Operations Research/Decision Theory, Production/Logistics/Supply Chain, approximation algorithms, optimization","pages":"385--394","bibtex":"@article{antoniadis_non-preemptive_2013,\n\ttitle = {Non-preemptive speed scaling},\n\tvolume = {16},\n\tissn = {1094-6136, 1099-1425},\n\turl = {http://link.springer.com/article/10.1007/s10951-013-0312-6},\n\tdoi = {10.1007/s10951-013-0312-6},\n\tabstract = {We consider the following offline variant of the speed scaling problem introduced by Yao et al. We are given a set of jobs and we have a variable-speed processor to process them. The higher the processor speed, the higher the energy consumption. Each job is associated with its own release time, deadline, and processing volume. The objective is to find a feasible schedule that minimizes the energy consumption. In contrast to Yao et al., no preemption of jobs is allowed. Unlike the preemptive version that is known to be in P, the non-preemptive version of speed scaling is strongly NP-hard. In this work, we present a constant factor approximation algorithm for it. The main technical idea is to transform the problem into the unrelated machine scheduling problem with LpL\\_p -norm objective.},\n\tlanguage = {en},\n\tnumber = {4},\n\turldate = {2014-09-30TZ},\n\tjournal = {Journal of Scheduling},\n\tauthor = {Antoniadis, Antonios and Huang, Chien-Chung},\n\tmonth = aug,\n\tyear = {2013},\n\tkeywords = {Artificial Intelligence (incl. Robotics), Calculus of Variations and Optimal Control; Optimization, Energy-efficient scheduling, Non-preemption, Operations Research/Decision Theory, Production/Logistics/Supply Chain, approximation algorithms, optimization},\n\tpages = {385--394}\n}\n\n","author_short":["Antoniadis, A.","Huang, C."],"key":"antoniadis_non-preemptive_2013","id":"antoniadis_non-preemptive_2013","bibbaseid":"antoniadis-huang-nonpreemptivespeedscaling-2013","role":"author","urls":{"Paper":"http://link.springer.com/article/10.1007/s10951-013-0312-6"},"keyword":["Artificial Intelligence (incl. Robotics)","Calculus of Variations and Optimal Control; Optimization","Energy-efficient scheduling","Non-preemption","Operations Research/Decision Theory","Production/Logistics/Supply Chain","approximation algorithms","optimization"],"downloads":0,"html":""},"search_terms":["non","preemptive","speed","scaling","antoniadis","huang"],"keywords":["artificial intelligence (incl. robotics)","calculus of variations and optimal control; optimization","energy-efficient scheduling","non-preemption","operations research/decision theory","production/logistics/supply chain","approximation algorithms","optimization"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}