Stochastic limit laws for schedule makespans

A basic multiprocessor version of the makespan scheduling problem requires that n tasks be scheduled on m identical processors so as to minimize the latest task finishing time. In the standard probability model considered here, the task durations are i.i.d. random variables with a general distribution F having finite mean. Our main objective is to estimate the distribution of the makespan as a function of mn and F under the on-line greedy policy, i.e., where the tasks are put in sequence and assigned in order to processors whenever they become idle. Because of the difficulty of exact analysis, we concentrate on the asymptotic behavior as n→∞ or as both m→∞ and n→∞with m≥n. The focal point is the Markov chain giving the remaining processing times of the m - 1 tasks still running at task completion epochs. The theory of stationary marked point processes is used to show that the stationary distribution of this Markov chain coincides with the order statistics of m - 1 independent random variables having the equilibrium residual-life distribution associated with F. Convergence theory for general-state Markov chains is then applied to establish convergence results for the Markov chain of interest. Finally, central limit theorems are applied to show that what we can gain from a good list scheduling policy is asymptotically negligible compared to our degree of uncertainty about the makespan (i.e., its standard deviation)