List scheduling in a parallel machine environment with precedence constraints and setup times

被引：45

作者：

Hurink, J

Knust, S

机构：

[1] Univ Twente, Fac Math Sci, NL-7500 AE Enschede, Netherlands

[2] Univ Osnabruck, Fachbereich Math Informat, D-49069 Osnabruck, Germany

来源：

OPERATIONS RESEARCH LETTERS | 2001年 / 29卷 / 05期

关键词：

scheduling; list scheduling; complexity; parallel machines; setup times;

D O I：

10.1016/S0167-6377(01)00104-3

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present complexity results which have influence on the strength of list scheduling in a parallel machine environment where additional precedence constraints and sequence-dependent setup times are given and the makespan has to be minimized. We show that contrary to various other scheduling problems, in this environment a set of dominant schedules cannot be calculated efficiently with list scheduling techniques. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：231 / 239

页数：9

共 11 条

[1]

Baker KR., 1974, Introduction to Sequencing and Scheduling

[2] An exact method for solving the multi-processor flow-shop [J].