Optimal scheduling of exponential tasks with in-tree precedence constraints on two parallel processors subject to failure and repair

Optimal scheduling of exponential tasks with in-tree precedence constraints on two parallel processors subject to failure and repair

0.00 Avg rating0 Votes
Article ID: iaor199371
Country: United States
Volume: 40
Start Page Number: 119
End Page Number: 126
Publication Date: May 1992
Journal: Operations Research
Authors: ,
Keywords: stochastic processes
Abstract:

In this paper, the authors 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. The authors 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, the authors also show that the HLF policy minimizes the dynamic failure probability when the processors are subject to failure, but no repairs can be done.

Reviews

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