Shioura, Akiyoshi, Shakhlevich, Natalia V. and Strusevich, Vitaly A. (2017) Machine speed scaling by adapting methods for convex optimization with submodular constraints. INFORMS Journal on Computing, 29 (4). pp. 724-736. ISSN 1091-9856 (Print), 1526-5528 (Online) (doi:https://doi.org/10.1287/ijoc.2017.0758)

Preview

PDF (Publisher's PDF - Open Access) 17696_STRUSEVICH_Machine_Speed_Scaling_2017.pdf - Published Version Available under License Creative Commons Attribution. Download (336kB) | Preview

Abstract

In this paper, we propose a new methodology for the speed-scaling problem based on its link to scheduling with controllable processing times and submodular optimization. It results in faster algorithms for traditional speed-scaling models, characterized by a common speed/energy function. Additionally, it efficiently handles the most general models with job-dependent speed/energy functions with single and multiple machines. To the best of our knowledge, this has not been addressed prior to this study. In particular, the general version of the single-machine case is solvable by the new technique in O(n2) time.

Item Type:	Article
Additional Information:	Open Access Statement: This work is licensed under a Creative Commons Attribution 4.0 International License. You are free to copy, distribute, transmit and adapt this work, but you must attribute this work as “INFORMS Journal on Computing. Copyright © 2017 The Author(s). https://doi.org/10.1287/ijoc.2017.0758, used under a Creative Commons Attribution License: https://creativecommons.org/licenses/by/4.0/.”
Uncontrolled Keywords:	Management Science and Operations Research, Software, Information Systems, Computer Science Applications
Subjects:	Q Science > QA Mathematics
Faculty / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
SWORD Depositor:	Publications Router
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/17696

Actions (login required)

View Item

Downloads