Stochastic limit laws for schedule makespans

Stochastic limit laws for schedule makespans

0.00 Avg rating0 Votes
Article ID: iaor20002554
Country: United States
Volume: 12
Issue: 2
Start Page Number: 215
End Page Number: 243
Publication Date: May 1996
Journal: Communications in Statistics - Stochastic Models
Authors: , ,
Keywords: markov processes
Abstract:

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 independent identically distributed 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 m, n, 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).

Reviews

Required fields are marked *. Your email address will not be published.