Parallel machine scheduling: A probabilistic analysis

Nanda Piersma and H. Edwin Romeijn

Naval Research Logistics (NRL), 1996, vol. 43, issue 6, 897-916

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 goes 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. © 1996 John Wiley & Sons, Inc.

Date: 1996
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199609)43:63.0.CO;2-#

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:43:y:1996:i:6:p:897-916

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().