Skip navigation

Machine speed scaling by adapting methods for convex optimization with submodular constraints

Machine speed scaling by adapting methods for convex optimization with submodular constraints

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)

[img]
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 / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Mathematical Sciences
SWORD Depositor: Publications Router
Last Modified: 10 Jun 2019 14:34
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: GREAT 2
URI: http://gala.gre.ac.uk/id/eprint/17696

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics