Optimal Scheduling of Exponential Tasks with In-Tree Precedence Constraints on Two Parallel Processors Subject to Failure and Repair

V. G. Kulkarni and P. F. Chimento
Additional contact information
V. G. Kulkarni: University of North Carolina, Chapel Hill, North Carolina
P. F. Chimento: IBM Corporation, Research Triangle Park, North Carolina

Operations Research, 1992, vol. 40, issue 3-supplement-2, S263-S271

Abstract: In this paper, we consider the problem of scheduling n tasks on two processors. The processing times of the n tasks are i.i.d. exponential random variables. The precedence constraints among the n tasks form an in-tree. The two processors are subject to failure and repair in a completely arbitrary manner, but are independent of the task processing times. We introduce the concept of stochastic partial ordering on random in-trees and show that among all policies, the highest level first (HLF) policy produces the smallest in-tree of unfinished tasks under the stochastic partial ordering. This implies that the HLF policy stochastically minimizes the makespan even when the two processors are subject to failures and repairs. As a special case, we also show that the HLF policy minimizes the dynamic failure probability when the processors are subject to failure, but no repairs can be done.

Keywords: production/scheduling; stochastic: scheduling with in-tree precedence constraints (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.3.S263 (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:40:y:1992:i:3-supplement-2:p:s263-s271

Access Statistics for this article

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