zbMATH — the first resource for mathematics

Scheduling independent tasks to minimize the makespan on identical machines. (English) Zbl 1335.90032
Summary: In this paper we consider scheduling \(n\) tasks on \(m\) parallel machines where the task processing times are i.i.d. random variables with a common distribution function \(F\). Scheduling is done by an a priori assignment of tasks to machines. We show that if the distribution function \(F\) is a Pólya frequency function of order 2 (decreasing reverse hazard rate) then the assignment that attempts to place an equal number of tasks on each machine achieves the stochastically smallest makespan among all assignments. The condition embraces many important distributions, such as the gamma and truncated normal distributions. Assuming that the task processing times have a common density that is a Pólya frequency function of order 2 (increasing likelihood ratio), then we find that flatter schedules have stochastically smaller makespans in the sense of the “joint” likelihood ratio.

90B35 Deterministic scheduling theory in operations research
Full Text: DOI
[1] Makowski, Characterizing majorization on – N (1993)
[2] Karlin, Totalpositivity 1 (1968)
[3] DOI: 10.2307/1427482 · Zbl 0756.60014 · doi:10.2307/1427482
[4] Barlow, Statistical theory of reliability and life testing: Probability models (1975) · Zbl 0379.62080
[5] Marshall, Inequalities: Theory of majorization and its applications (1979) · Zbl 0437.26007
[6] Shaked, Stochastic orders and their applications (1994) · Zbl 0806.62009
[7] DOI: 10.1007/BF02790092 · Zbl 0045.37602 · doi:10.1007/BF02790092
[8] Ross, Stochastic processes (1983)
[9] DOI: 10.2307/1427627 · Zbl 0745.62054 · doi:10.2307/1427627
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.