Scheduling with multiple servers

What is it about?

We consider the problem of scheduling a set of jobs on a set of identical parallel machines. The complexity of such problems for the minimization of the makespan is investigated. For the problem with equal processing times and equal setup times we give a polynomial algorithm. For the problem with unit setup times, m machines and m − 1 servers, we give a pseudopolynomial algorithm. In addition, recent algorithms for some parallel machine scheduling problems with constant precessing times are generalized to the corresponding server problems for the case of constant setup times. A worst case analysis of two list scheduling algorithms for makespan minimization is also done.

Featured Image