Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtime
- 1 March 1982
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 19 (1) , 167-182
- https://doi.org/10.2307/3213926
Abstract
A number of identical machines operating in parallel are to be used to complete the processing of a collection of jobs so as to minimize either the jobs' makespan or flowtime. The total processing required to complete each job has the same probability distribution, but some jobs may have received differing amounts of processing prior to the start. When the distribution has a monotone hazard rate the expected value of the makespan (flowtime) is minimized by a strategy which always processes those jobs with the least (greatest) hazard rates. When the distribution has a density whose logarithm is concave or convex these strategies minimize the makespan and flowtime in distribution. These results are also true when the processing requirements are distributed as exponential random variables with different parameters.Keywords
This publication has 13 references indexed in Scilit:
- Scheduling Stochastic Jobs on Parallel Machines to Minimize Makespan or FlowtimePublished by Springer Nature ,1982
- Scheduling Jobs with Exponential Processing and Arrival Times on Identical Processors so as to Minimize the Expected MakespanMathematics of Operations Research, 1981
- Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or MakespanJournal of the ACM, 1981
- Scheduling tasks with exponential service times on non-identical processors to minimize various cost functionsJournal of Applied Probability, 1980
- Scheduling of stochastic tasks on two parallel processorsNaval Research Logistics Quarterly, 1979
- Scheduling tasks with exponential service times on parallel processorsJournal of Applied Probability, 1979
- Controlled jump process models for stochastic scheduling problemsInternational Journal of Control, 1979
- An Optimal Strategy in Multi-Server Stochastic SchedulingJournal of the Royal Statistical Society Series B: Statistical Methodology, 1978
- On the optimal assignment of customers to parallel serversJournal of Applied Probability, 1978
- Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time DisciplineOperations Research, 1968