Stochastic scheduling on parallel processors and minimization of concave functions of completion times

R.R. Weber, In W. Fleming and P.L. Lions, editors, Stochastic Differential Systems, Stochastic Control Theory and Applications volume 10, pages 601-609. Springer-Verlag, New York, 1988.


We consider a scheduling problem in which $n$ jobs are to be scheduled on $m$ 
identical processors which operate in parallel.  The processing times of the 
jobs are not known in advance but they have known distributions with hazard 
rates $\rho_1(t),\ldots,\rho_n(t)$.  It is desired to minimize the expected 
value of $\kappa(C)$, where $C_i$ is the time at which job $i$ is completed,
$C=(C_1,\ldots,C_n)$, and $\kappa(C)$ is increasing and concave in $C$.
Suppose processor $i$ first becomes available at time $\tau_i$.  We prove that 
if there is a single static list priority policy which is optimal for every
$\tau=(\tau_1,\ldots,\tau_n)$, then the minimal expected cost must be increasing 
and concave in $\tau$.  Moreover, if $\kappa(C)$ is supermodular in $C$ then 
this cost is also supermodular in $\tau$.  This result is used to prove that 
processing jobs according to the static list priority order $(1,\ldots,n)$ 
minimizes the expected value of $\sum w_i h(C_i)$, when $h(\cdot)$ is a 
nondecreasing, concave function, $w_1\geq\cdots\geq w_n$, and 
$\rho_1(t_1)w_1\geq\cdots\geq \rho_n(t_n)w_n$ for all $t_1,\ldots,t_n$.

back to list of papers