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 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 for a set of benchmarks.