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