  In vehicular cloud computing (VCC) systems, the computational resources of
moving vehicles are exploited and managed by infrastructures, e.g., roadside
units, to provide computational services. The offloading of computational tasks
and collection of results rely on successful transmissions between vehicles and
infrastructures during encounters. In this paper, we investigate how to provide
timely computational services in VCC systems. In particular, we seek to
minimize the deadline violation probability given a set of tasks to be executed
in vehicular clouds. Due to the uncertainty of vehicle movements, the task
replication methodology is leveraged which allows one task to be executed by
several vehicles, and thus trading computational resources for delay reduction.
The optimal task replication policy is of key interest. We first formulate the
problem as a finite-horizon sampled-time Markov decision problem and obtain the
optimal policy by value iterations. To conquer the complexity issue, we propose
the balanced-task-assignment (BETA) policy which is proved optimal and has a
clear structure: it always assigns the task with the minimum number of
replicas. Moreover, a tight closed-form performance upper bound for the BETA
policy is derived, which indicates that the deadline violation probability
follows the Rayleigh distribution approximately. Applying the vehicle
speed-density relationship in the traffic flow theory, we find that vehicle
mobility benefits VCC systems more compared with road traffic systems, by
showing that the optimum vehicle speed to minimize the deadline violation
probability is larger than the critical vehicle speed in traffic theory which
maximizes traffic flow efficiency.
