The multiprocessor scheduling of precedence-constrained task systems in the presence of interprocessor communication delays
成果类型：
Article
署名作者：
Baruah, SK
署名单位：
University of Vermont
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.46.1.65
发表日期：
1998
页码：
65-72
关键词：
摘要：
The problem of scheduling precedence-constrained task systems characterized by interprocessor communication delays is addressed. It is assumed that task duplication is permitted. The target machine is a homogenous multiprocessor with an unbounded number of processors. The general problem is known to be NP-hard; however, when communication delays are small relative to task execution times, the C.P.M. based approach of Colin and Chretienne (1991) yields an optimal schedule in polynomial time. Extensions to this method of Colin and Chretienne are presented here, which allow for polynomial-time optimal schedule generation for certain categories of task systems with arbitrary precedence relations, processing times, and communication delays.