Batching in a two-stage flowshop with dedicated machines in the second stage

The problem of batching and scheduling n identical jobs of F, F greater than or equal to 2, part types in a shop made up of F + 1 machines is studied. 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. Setup times are necessary at the first stage to switch processing from a job of one part type to a job of another 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 makespan. We show that this problem is equivalent to a special case of a single machine family scheduling problem to minimize maximum lateness and therefore it can be solved in O(n(F)) time by a known algorithm. Furthermore, for the case where F = 2, we present an iterative exact algorithm with O(k(0) logL) running time, where k(0) is the maximum number of batches in a schedule created in any iteration of the algorithm and L is the problem input length in unary encoding. The algorithm finds a schedule with the minimum number of batches k* in any optimal solution. Computational experiments were conducted to investigate the relationship between k* and k(0). For all tested examples, k(0) = max{k(1)*, k(2)*}, where k(1)* (k(2)*) was the minimum number of batches in any optimal schedule starting with a batch of one part type (the other part type).