Split Scheduling with Uniform Setup Times

We study a scheduling problem in which jobs may be split into parts, where the parts of a split job may be processed simultaneously on more than one machine. Each part of a job requires a setup time, however, on the machine where the job part is processed. During setup a machine cannot process or set up any other job. We concentrate on the basic case in which setup times are job-, machine-, and sequence-independent. The result that will be presented is a polynomial-time algorithm for minimizing total completion time on two parallel identical machines. We argue why the same problem with three machines is not an easy extension of the two-machine case, leaving the complexity of this case as a tantalizing open problem.

• Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars