Scheduling parallel machines with a single server.

This paper investigates scheduling parallel machines with a single sever as well as additional constraints on setups and removals. It generalizes classical parallel machine scheduling problem with a single server which needs to perform setup operation of each job only. This model is motivated by a key course of batch annealing process in the steel industry: heating or cooling. The objective is to minimize makespan. For this problem, we first give some complexity results by reduction. Some optimal properties are derived. Based on the properties, a LPT heuristics is proposed which generates a tight worst-case bound 3/2 – 1/2m. [ABSTRACT FROM PUBLISHER]