Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime
- 1 September 1986
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 23 (3), 841-847
- https://doi.org/10.2307/3214023
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 total 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.Keywords
This publication has 3 references indexed in Scilit:
- Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtimeJournal of Applied Probability, 1982
- Scheduling tasks with exponential service times on non-identical processors to minimize various cost functionsJournal of Applied Probability, 1980
- Scheduling tasks with exponential service times on parallel processorsJournal of Applied Probability, 1979