Parallel machine scheduling with a common server

This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by a singl e server onto the relevant machine. The paper considers a number of classic al scheduling objectives in this environment, under a variety of assumption s about setup and processing times. For each problem considered, the intent ion is to provide either a polynomial- or pseudo-polynomial-time algorithm, or a proof of binary or unary NP-completeness; The results provide a mappi ng of the computational complexity of these problems. (C) 2000 Elsevier Sci ence B.V. All rights reserved.