Makespan minimization in the two-machine flowshop batch scheduling problem

Edwin Tai Chiu Cheng, B. M.T. Lin, A. Toker

Research output: Journal article publicationJournal articleAcademic researchpeer-review

52 Citations (Scopus)


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
Issue number2
Publication statusPublished - 1 Jan 2000

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


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

Cite this