Parallel machine scheduling: A probabilistic analysis

Parallel machine scheduling: A probabilistic analysis

0.00 Avg rating0 Votes
Article ID: iaor1997557
Country: United States
Volume: 43
Issue: 6
Start Page Number: 897
End Page Number: 916
Publication Date: Sep 1996
Journal: Naval Research Logistics
Authors: ,
Abstract:

The minimum makespan of the general parallel machine scheduling problem with m machines and n jobs is studied. As for a number of other important combinatorial problems, the theory of empirical processes proves to be a very elegant and powerful tool for the probabilistic analysis of the solution value. It is used in this paper to derive a scheduling constant θ such that, for random processing times, the minimum makespan almost surely grows as θn when n does to infinity. Moreover, a thorough probabilistic analysis is performed on the difference between the minimum makespan and θn. Explicit expressions for the scheduling constant are given for an arbitrary number of unrelated machines with identically distributed processing times (with an increasing failure rate), and for an arbitrary number of uniform machines and generally distributed processing times.

Reviews

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