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

Abstract

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.