Energy and time constrained task scheduling on multiprocessor computers with discrete speed levels

Energy and time constrained task scheduling on multiprocessor computers with discrete clock frequency and supply voltage and execution speed and power levels is addressed as combinatorial optimization problems. It is proved that the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint are NP-hard even on a uniprocessor computer with only two speed levels. A class of algorithms is developed to solve the above two problems. These algorithms include two components, namely, a list scheduling algorithm for task scheduling and a list placement algorithm for speed determination. A worst-case asymptotic performance bound and an average-case asymptotic performance bound are derived for our algorithms on uniprocessor computers, and a worst-case asymptotic performance bound is derived for our algorithms on multiprocessor computers. Extensive simulations are performed to verify our analytical results. It is found that our algorithms produce solutions very close to optimal and are practically very useful.