Parallel machine scheduling problems with a single server

What is it about?

We consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length as well as the forced idle time. This paper presents a pseudopolynomial algorithm for the case of two machines when 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 analyze some list scheduling heuristics for this problem. We also prove unary NP-hardness of the problem of minimizing forced idle time on two machines even for the case of constant setup times. Moreover, some polynomially solvable cases are given.

Featured Image