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

Edwin Tai Chiu Cheng, M. Y. Kovalyov, K. N. Chakhlevich

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)


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 languageEnglish
Pages (from-to)87-93
Number of pages7
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number1
Publication statusPublished - 1 Jan 2004

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Batching in a two-stage flowshop with dedicated machines in the second stage'. Together they form a unique fingerprint.

Cite this