We construct a dynamic stochastic model to study the scheduling problem for battery charging of multiple (possibly a large number of) PHEVs. Our model incorporates the stochasticity in future PHEV arrival process and future renewable generation. The objective of scheduling is to maximize the overall social welfare, which is derived from total customer utility, the electricity cost associated with PHEV charging, and the non-completion penalty for not satisfying PHEVs' charging requests. Through a dynamic programming formulation, we show the Less Laxity and Longer remaining Processing time (LLLP) principle: priority should be given to vehicles that have less laxity and longer remaining processing times, if the non-completion penalty (as a function of the additional time needed to fulfill the unsatisfied charging request) is convex. We introduce various forms of improved polices generated from a given heuristic policy according to the LLLP principle, and show that these improved polices can only improve social welfare, compared to the original heuristic.