  We consider the scheduling of multiple tasks with pre-determined deadlines
under random processing cost. This problem is motivated by the potential of
large scale adoption of plug-in (hybrid) electric vehicles (PHEVs) in the near
future. The charging requests of PHEVs usually have deadline constraints, and
the electricity cost associated with PHEV charging is usually random due to the
uncertainty in both system load and renewable generation. We seek to properly
schedule the battery charging of multiple PHEVs so as to minimize the overall
cost, which is derived from the total charging cost and the penalty for not
completing charging before requested deadlines. Through a dynamic programming
formulation, we establish the Less Laxity and Longer remaining Processing time
(LLLP) principle that improves any charging policy on a sample-path basis, when
the non-completion penalty is a convex function of the additional time needed
to fulfill the uncompleted request. Specifically, the LLLP principle states
that priority should be given to vehicles that have less laxity and longer
remaining processing times. Numerical results demonstrate that heuristic
policies that violate the LLLP principle, for example, the earliest deadline
first (EDF) policy, can result in significant performance loss.
