We address the problem of energy-optimal voltage scheduling for fixed-priority hard real-time systems. First, we prove that the problem is NP-hard. Then, we present a fully polynomial time approximation scheme (FPTAS) for the problem. for any $varepsilon$>0, the proposed approximation scheme computes a voltage schedule whose energy consumption is at most (1+$varepsilon$) times that of the optimal voltage schedule. Furthermore, the running time of the proposed approximation scheme is bounded by a polynomial function of the number of input jobs and 1/$varepsilon$. Experimental results show that the approximation scheme finds more efficient voltage schedules faster than the best existing heuristic.