Scheduling Jobs with Exponentially Distributed Processing Times and Intree Precedence Constraints on Two Parallel Machines

Michael Pinedo and Gideon Weiss
Additional contact information
Michael Pinedo: Columbia University, New York, New York
Gideon Weiss: Georgia Institute of Technology, Atlanta, Georgia and Tel Aviv University, Tel Aviv, Israel

Operations Research, 1985, vol. 33, issue 6, 1381-1388

Abstract: We consider n jobs with independent exponentially distributed processing times that are to be processed on two machines operating in parallel. The jobs are subject to precedence constraints that have the form of an intree, i.e., each job, except for the last one, has one direct successor. A job is at level l if its successor is at level l − 1 (the last job is at level 0). We assume that all jobs at level l have i.i.d. exponentially distributed processing times, with mean 1/μ l . Under these assumptions, we show that the policy that schedules HLF (highest level first) minimizes the expected makespan in the class of preemptive as well as nonpreemptive schedules. This conclusion generalizes a previous result of Chandy and Reynolds.

Keywords: 566 distributions; 572 stochastic model applications; 581 production/scheduling (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.6.1381 (application/pdf)

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:inm:oropre:v:33:y:1985:i:6:p:1381-1388

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().