Restrictions and preassignments in preemptive open shop scheduling

被引：15

作者：

deWerra, D

Hoffman, AJ

Mahadev, NVR

Peled, UN

机构：

[1] IBM CORP,THOMAS J WATSON RES CTR,YORKTOWN HTS,NY 10598

[2] NORTHEASTERN UNIV,DEPT MATH,BOSTON,MA 02115

[3] UNIV ILLINOIS,DEPT MATH STAT & COMP SCI,CHICAGO,IL

来源：

DISCRETE APPLIED MATHEMATICS | 1996年 / 68卷 / 1-2期

关键词：

chromatic scheduling; open shop scheduling; timetabling; production; edge-coloring;

D O I：

10.1016/0166-218X(95)00055-V

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Preemptive open shop scheduling can be viewed as an edge coloring problem in a bipartite multigraph. In some applications, restrictions of colors (in particular preassignments) are made for some edges. We give characterizations of graphs where some special preassignments can be embedded in a minimum coloring (number of colors = maximum degree). The case of restricted colorings of trees is shown to be solvable in polynomial time.

引用

页码：169 / 188

页数：20