Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-26T16:14:44.803Z Has data issue: false hasContentIssue false
  • English
  • Français

Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtime

Published online by Cambridge University Press:  14 July 2016

Richard R. Weber
Richard R. Weber*
Affiliation:
University of Cambridge
*
∗Postal address: Queens' College, Cambridge CB3 9ET, U.K.
Get access Rights & Permissions [Opens in a new window]

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

DYNAMIC PROGRAMMINGFLOWTIMEMAKESPANMONOTONE HAZARD RATEOPTIMAL CONTROLSIGN-CONSISTENT FREQUENCYSTOCHASTIC SCHEDULING
Type
Research Paper
Information
Journal of Applied Probability , Volume 19 , Issue 1 , March 1982 , pp. 167 - 182
Copyright
Copyright © Applied Probability Trust 1982 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Bruno, J. (1976) Sequencing tasks with exponential service times on parallel machines. Technical report, Department of Computer Science, Pennsylvania State University.Google Scholar
Bruno, J. and Downey, P. (1977) Sequencing tasks with exponential service times on parallel machines. Technical report, Department of Computer Sciences, University of California at Santa Barbara.Google Scholar
Bruno, J., Downey, P. and Frederickson, G. N. (1981) Sequencing tasks with exponential service times to minimize the expected flowtime or makespan. J. Assoc. Comput. Mach. 28, 100–113.CrossRefGoogle Scholar
Conway, R. W., Maxwell, W. L. and Miller, L. W. (1967) The Theory of Scheduling. Addison-Wesley, Reading, Ma.Google Scholar
Cox, D. R. (1959) A renewal problem with bulk ordering of components. J.R. Statist. Soc. B 21, 180–189.Google Scholar
Glazebrook, K. D. (1976) Stochastic Scheduling. Ph.D. Thesis, University of Cambridge.Google Scholar
Glazebrook, K. D. (1979) Scheduling tasks with exponential service times on parallel processors. J. Appl. Prob. 16, 685–689.Google Scholar
Karlin, S. (1968) Total Positivity, Vol. I. Stanford University Press, Stanford.Google Scholar
Nash, P. (1973) Optimal Allocation of Resources to Research Projects. Ph.D. Thesis, University of Cambridge.Google Scholar
Nash, P. (1979) Controlled jump process models for stochastic scheduling problems. Internat. J. Control 30, 1011–1026.Google Scholar
Nash, P. and Gittins, J. C. (1977) A Hamiltonian approach to optimal stochastic resource allocation. Adv. Appl. Prob. 9, 55–68.Google Scholar
Pinedo, ?. and Weiss, G. (1979) Scheduling stochastic tasks on two parallel processors. Naval Res. Logist. Quart. 27, 528–536.Google Scholar
Schrage, L. E. (1968) A proof of the shortest remaining process time discipline. Operat. Res. 16, 687–689.Google Scholar
Van Der Heyden, J. (1981) Scheduling jobs with exponential processing and arrival times on identical processors so as to minimize expected makespan. Math. Operat. Res. 6, 305–312.CrossRefGoogle Scholar
Varaiya, P. P. (1972) Notes on Optimization. Van Nostrand Reinhold, New York.Google Scholar
Weber, R. R. (1978) On the optimal assignment of customers to parallel servers. J. Appl. Prob. 15, 406–413.Google Scholar
Weber, R. R. and Nash, P. (1979) An optimal strategy in multi-server stochastic scheduling. J. R. Statist. Soc. B 40, 323–328.Google Scholar
Weber, R. R. (1980a) Optimal Organization of Multi-server Systems. Ph.D. Thesis, University of Cambridge.Google Scholar
Weber, R. R. (1980b) On the marginal benefit of adding servers to G/GI/m queues. Management Sci. 26, 946–951.Google Scholar
Weber, R. R. (1982) Scheduling stochastic jobs on parallel machines to minimize makespan or flowtime. Proceedings of the ORSA-TIMS Special Interest Meeting: Applied Probability — Computer Science, the Interface. To appear.Google Scholar
Weiss, G. and Pinedo, M. (1979) Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. J. Appl. Prob. 17, 187–202.Google Scholar