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