Approximation algorithm for the energy-aware profit maximizing problem in heterogeneous computing systems

摘要

Trade-offs between energy and performance are important for energy-aware scheduling. Recently, a novel model, called energy-aware profit maximizing scheduling problem (EAPM), which combines energy and makespan into the objective of maximizing the profit per unit of time has been proposed. The user pay a given price to have a bag-of-tasks processed and the objective is to maximize the profit per unit time. In this study, we design a polynomial-time algorithm for the EAPM problem. The execution time of our algorithm is polynomial in the number of task types which is an improvement over the previous algorithm, whose execution time is polynomial in the number of tasks. Moreover, we demonstrate that the approximation ratio of our algorithm is close to 2 for a special case, which may be the best result we can obtain. Experimental results show that our algorithm can produce a feasible solution with better objective value than the previous algorithm. (C) 2018 Published by Elsevier Inc.