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

Journal of Applied Probability - Tập 19 Số 1 - Trang 167-182 - 1982
Richard Weber1
1University of Cambridge

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

10.1287/opre.16.3.687

Glazebrook K. D. (1976) Stochastic Scheduling. Ph.D. Thesis, University of Cambridge.

Nash P. (1973) Optimal Allocation of Resources to Research Projects. Ph.D. Thesis, University of Cambridge.

10.1145/322234.322242

Weber, 1979, An optimal strategy in multi-server stochastic scheduling, J. R. Statist. Soc., B 40, 323

10.1017/S0021900200046921

10.1017/S0021900200107843

Conway, 1967, The Theory of Scheduling.

Karlin, 1968, Total Positivity, I

10.1287/moor.6.2.305

Bruno, 1976, Sequencing tasks with exponential service times on parallel machines

10.1017/S0021900200045678

10.1080/00207177908922746

Weber R. R. (1980a) Optimal Organization of Multi-server Systems. Ph.D. Thesis, University of Cambridge.

Pinedo, 1979, Scheduling stochastic tasks on two parallel processors, Naval Res. Logist. Quart., 27, 528

Bruno, 1977, Sequencing tasks with exponential service times on parallel machines

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.

10.1287/mnsc.26.9.946

Varaiya, 1972, Notes on Optimization.

Cox, 1959, A renewal problem with bulk ordering of components, J.R. Statist. Soc., B 21, 180

10.1017/S0001867800043111