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(nF) time by a known algorithm. Furthermore, for the case where F = 2, we present an iterative exact algorithm with O(k0log L) running time, where k0is 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 k0. For all tested examples, k0= max{k1*, k2*}, where k1* (k2*) was the minimum number of batches in any optimal schedule starting with a batch of one part type (the other part type).
Original language | English |
---|---|
Pages (from-to) | 87-93 |
Number of pages | 7 |
Journal | IIE Transactions (Institute of Industrial Engineers) |
Volume | 36 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2004 |
ASJC Scopus subject areas
- Industrial and Manufacturing Engineering