Circuit performance has been the key design constraint for over a decade. Variable-latency design (VLD) paradigm was proposed for optimizing the overall performance in terms of throughput. In addition, process variations and aging effects manifest themselves as gate delay shifts, and in turn cause variability of circuit timing (timing variability). Besides, Power consumption is another important design consideration. To deal with the impact of timing variability and power issue better, in this paper, we present a VDD assignment framework based on genetic algorithm (GA) to minimize the power consumption of VLD. Our objective is making constructed VLD circuits more power-efficient under given tolerance to timing variability. Experimental results show that on average our methodology can achieve 24% dynamic power reduction, while preserving at least 8% timing margin, with only 5% overhead in circuit area and leakage power.