Stochastic dispatching of multi-priority jobs to heterogeneous processors

S.H. Xu, P.B. Mirchandani, S.P.R. Kumar, and R.R. Weber, J. Appl. Prob. 27 852-861, 1990.

Abstract

A number of multi-priority jobs are to be processed on two heterogeneous
processors.  Of the jobs waiting in the buffer, jobs with the highest priority
have the first option of being dispatched for processing when a processor
becomes available.  On each processor, the processing times of the jobs within
each priority class are stochastic, but have known distributions with decreasing
mean residual (remaining) processing times.  Processors are heterogeneous in the
sense that, for each priority class, one has a lesser average processing time
than the other.  It is shown that the non-preemptive scheduling strategy for
each priority class to minimize its expected flowtime is of threshold type.  For
each class, the threshold values, which specify when the slower processor is to
be utilized, may be readily computed.  It is also shown that the social and
individual optimality coincide.

back to list of papers