Review of properties of different precedence graphs for scheduling problems

被引：11

作者：

Blazewicz, J ^{[1
]}

Kobler, D

机构：

[1] Politechn Poznanska, Inst Informat, Poznan, Poland

[2] PAN, Inst Bioorgan Chem, Poznan, Poland

[3] EPFL, Dept Math, CH-1015 Lausanne, Switzerland

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2002年 / 142卷 / 03期

关键词：

scheduling; precedence constraints; graph theory;

D O I：

10.1016/S0377-2217(01)00379-4

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Precedence constraints are a part of a definition of any scheduling problem. After recalling, in precise graph-theoretical terms, the relations between task-on-arc and task-on-node representations, we show the equivalence of two distinct results for scheduling problems. Furthermore, again using these links between representations, we exhibit several new polynomial cases for various problems of scheduling preemptable tasks on unrelated parallel machines under arbitrary resource constraints, (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：435 / 443

页数：9

共 26 条

[1] ON LINEGRAPH OF A DIRECTED GRAPH [J].