Complexity of a Problem of Energy Efficient Real-Time Task Scheduling on a Multicore Processor

摘要

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 P not equal NP, the EETSP problem is also proved to be inapproximable. (C) 2014 Wiley Periodicals, Inc.