PARALLEL MACHINE SCHEDULING PROBLEMS WITH A SINGLE-SERVER

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single s erver. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP- hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines whe n all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and ana lyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the c ase of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.