Tabu search based multiple voltage scheduling under both timing and resource constraints

In this work, we address the multiple voltage scheduling problem to minimize power consumption under both timing and resource constraints. We develop a tabu search-based algorithm with a general vector representation of solution and an effective performance estimation. Moreover, our approach tends to solve a series of scheduling problems with respect to multiple voltage designs. Specifically, our method represents each solution by a vector of operation types and solves the scheduling subproblem corresponding to a certain solution vector. To get feasible solutions of the subproblem, a two-stage method is presented by first adopting the PLNSM algorithm [3] to generate delay assignment satisfying the timing constraint and then performing delay adjustment iteratively until the resource constraints are met. A heuristic estimation is introduced to predict the total power and resource usage of the neighborhood. Our proposed method achieves near-optimal solutions with only an average power increase of 0.84% compared with ILP for small-size designs, and a 24.1% reduction over a previous tabu search-based algorithm [7] for a set of benchmarks.