We propose a battery replacement strategy to increase the efficiency of chargers and save drivers' time at charging stations for plug-in hybrid electric vehicles (PHEVs). With the battery replacement strategy, we optimize the scheduling for the operations of chargers in a charging station. The scheduling objectives are to minimize the power consumption cost and to allow as many PHEVs to be served as possible. In addition, we quantitatively analyze the impact of imperfect data communication on the scheduling performance. Furthermore, we formulate and solve a multistage stochastic programming model to minimize the power supply cost for the benefit of the grid operator. Renewable source generation and utilization of energy storage devices are integrated into the supply optimization problem.