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

Abstract

The problem of batching and scheduling n identical jobs of F, F ≥ 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 ⁰log L) running time, where k ⁰ 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 ⁰. For all tested examples, k ⁰ = max {k∗₁,k∗₂}, where k∗₁ (k∗₂) was the minimum number of batches in any optimal schedule starting with a batch of one part type (the other part type).

Acknowledgements

This research was supported in part by The Hong Kong Polytechnic University under grant number G-S818 and the Croucher Foundation under a Croucher Senior Research Fellowship for the first author. The second author was also supported by INTAS (Projects 96-0820 and 00-217).