CPM SCHEDULING WITH SMALL COMMUNICATION DELAYS AND TASK DUPLICATION

被引：70

作者：

COLIN, JY ^{[1
]}

CHRETIENNE, P ^{[1
]}

机构：

[1] UNIV PARIS 06,DEPT COMP SCI,F-75230 PARIS 05,FRANCE

来源：

OPERATIONS RESEARCH | 1991年 / 39卷 / 04期

关键词：

D O I：

10.1287/opre.39.4.680

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper addresses a machine scheduling problem that arises in the case of scheduling tasks over an idealized distributed multiprocessor. Precedence constraints with small communication delays have to be taken into account and task duplication is allowed. A critical path-like algorithm is presented, which is shown to construct an optimal schedule in polynomial time.

引用

页码：680 / 684

页数：5

共 6 条

[1] A POLYNOMIAL ALGORITHM TO OPTIMALLY SCHEDULE TASKS ON A VIRTUAL DISTRIBUTED SYSTEM UNDER TREE-LIKE PRECEDENCE CONSTRAINTS [J].