On speed scaling via integer programming

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 NPNP-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.