Scheduling batches on parallel machines with major and minor set-ups (Q918855)

An interesting scheduling problem to minimize makespan on identical parallel machines is considered with major set-up times between different families of parts, and minor set-up times between different part types. A two-level heuristic is proposed based on the Multifit Method, where the first level assigns families to machines, and the second level determines the batch size. A tight lower bound on the makespan is derived and used to evaluate the effectiveness of the algorithm. Computational experiments prove that near-optimal schedules are generated.