• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

On speed scaling via integer programming

Operations Research Letters. 2015. Vol. 43. No. 5. P. 537-544.
Karademir S., Prokopyev O.

We consider a class of convex mixed-integer nonlinear programs motivated by speed scaling of heterogeneous parallel processors with sleep states and convex power consumption curves. We show that the problem is NP-hard and identify some polynomially solvable classes. Furthermore, a dynamic programming and a greedy approximation algorithms are proposed to obtain a fully polynomial-time approximation scheme for a special case. For the general case, we implement an outer approximation algorithm.