An exact algorithm for batching and scheduling two part types in a mixed shop: A technical note

We consider the problem of scheduling jobs consisting of two part types in a shop made up of three machines. The processing of each job comprises two stages. The first stage is undertaken on the machine common to all jobs and the second stage is undertaken on the machine specific to a particular part type. Set-up times are necessary at the first stage to switch processing from a job of one part type to a job of the other part type. Jobs of the same part type processed contiguously at the first stage form a batch. The objective is to find a batch schedule minimizing the makespan. An integer programming formulation and a heuristic algorithm for this problem have been reported in the literature. We present a dynamic programming algorithm which solves the problem optimally in a time polynomial in the number of jobs.