Makespan minimization in the two-machine flowshop batch scheduling problem

T. C.E. Cheng*, Bertrand M.T. Lin, A. Toker

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part-types are to be produced in a flexible manufacturing cell organized into a two-stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP-hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics.

Original languageEnglish
Pages (from-to)128-144
Number of pages17
JournalNaval Research Logistics
Volume47
Issue number2
DOIs
StatePublished - 31 Jan 2000

Fingerprint Dive into the research topics of 'Makespan minimization in the two-machine flowshop batch scheduling problem'. Together they form a unique fingerprint.

Cite this