OPTIMAL SCHEDULING OF EXPONENTIAL TASKS WITH IN-TREE PRECEDENCE CONSTRAINTS ON 2 PARALLEL PROCESSORS SUBJECT TO FAILURE AND REPAIR
成果类型：
Article
署名作者：
KULKARNI, VG; CHIMENTO, PF
署名单位：
International Business Machines (IBM); IBM USA
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.3.S263
发表日期：
1992
页码：
S263-S271
关键词：
摘要：
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.