Stochastic limit laws for schedule makespans

Stochastic limit laws for schedule makespans

0.00 Avg rating0 Votes
Article ID: iaor19971696
Country: United States
Volume: 12
Issue: 2
Start Page Number: 215
End Page Number: 243
Publication Date: Feb 1996
Journal: Communications in Statistics - Stochastic Models
Authors: , ,
Keywords: scheduling
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 i.i.d. random variables with a general distribution F having finite mean. The present 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, the authors 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 the authors can gain from a good list scheduling policy is asymptotically negligible compared to the present degree of uncertainty about the makespan (i.e., its standard deviation).

Reviews

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