On the solution region for certain scheduling problems with preemption

被引：4

作者：

Brasel, H

Shakhlevich, N

机构：

[1] Univ Magdeburg, Fak Math, D-39106 Magdeburg, Germany

[2] Acad Sci Belarus, Minsk 220012, BELARUS

来源：

ANNALS OF OPERATIONS RESEARCH | 1998年 / 83卷 / 0期

关键词：

parallel machine problem; open shop problem; scheduling polytope;

D O I：

10.1023/A:1018999711765

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The paper deals with parallel machine and open shop scheduling problems with pre-emptions and an arbitrary nondecreasing objective function. An approach to describing the solution region for these problems and to reducing them to minimization over polytopes is proposed. Properties of the solution regions for certain problems are investigated. It is proved that open shop problems with unit processing times are equivalent to certain parallel machine problems, where preemption is allowed at arbitrary times. A polynomial algorithm is presented, transforming a schedule of one type into a schedule of the other type.

引用

页码：1 / 21

页数：21