Complexity of a problem of energy efficient real‐time task scheduling on a multicore processor
Abhishek Mishra, Anil Kumar Tripathi · Complexity · 2014
The problem of scheduling independent tasks with a common deadline for a multicore processor is investigated. The speed of cores can be varied (from a finite set of core speeds) using software controlled Dynamic Voltage Scaling. The energy consumption is to be minimized. This problem was called the Energy Efficient Task Scheduling Problem (EETSP) in a previous work in which a Monte Carlo algorithm was proposed for solving it. This work investigates the complexity of the EETSP problem. The EETSP problem is proved to be NP‐Complete. Under the assumption of , the EETSP problem is also proved to be inapproximable. © 2014 Wiley Periodicals, Inc. Complexity 21: 259–267, 2015