##
Scheduling jobs with stochastically ordered processing requirements to
minimize expected flowtime

###
R.R. Weber, P. Varaiya and J. Walrand
*J. Appl. Prob.* **23**, 841-847, 1986.

Abstract

A number of jobs are to be processed using a number of identical
machines which operate in parallel. The processing times of the jobs
are stochastic, but have known distributions which are stochastically
ordered. A reward r(t) is acquired when a job is completed at time t.
The function r(t) is assumed to be convex and decreasing in t. It is
shown that within the class of non-preemptive scheduling strategies
the strategy SEPT maximizes the expected reward. This strategy is one
which whenever a machine becomes available starts processing the
remaining job with the shortest expected processing time. In
particular, for r(t) = -t, this strategy minimizes the expected
flowtime.

**back to list of papers**