##
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.

Abstract

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**