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

共 13 条

[1]

BALAS E, 1985, MATH PROGRAM STUD, V24, P179, DOI 10.1007/BFb0121051

[2]

Barany I., 1982, Szigma, V15, P177

[3]

Brucker P., 1993, ZOR, Methods and Models of Operations Research, V37, P59, DOI 10.1007/BF01415528

[4] SCHEDULING INDEPENDENT TASKS TO REDUCE MEAN FINISHING TIME [J].

BRUNO, J ;

COFFMAN, EG ;

SETHI, R .

COMMUNICATIONS OF THE ACM, 1974, 17 (07) :382-387

[5] MINIMIZING MEAN FLOW TIME IN 2-MACHINE OPEN SHOPS AND FLOW SHOPS [J].

DU, JZ ;

LEUNG, JYT .

JOURNAL OF ALGORITHMS, 1993, 14 (01) :24-44

[6]

Graham R. L., 1979, Discrete Optimisation, P287

[7]

LIVSHITS AM, 1972, COMPUTATIONAL MATH C, V3, P78

[8] SCHEDULING WITH DEADLINES AND LOSS FUNCTIONS [J].

MCNAUGHTON, R .

MANAGEMENT SCIENCE, 1959, 6 (01) :1-12

[9]

Queyranne M, 1994, 4081994 TU BERL

[10]

STRUSEVICH VA, 1988, VESTNIK BGU IMENI 1, V1, P44

← 1 2 →