Batch scheduling in the no-wait two-machine flowshop to minimize the makespan

Bertrand M.T. Lin, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

34 Citations (Scopus)


We consider a scheduling problem where a set of jobs are simultaneously available for processing in a no-wait two-machine flowshop. The objective is to minimize the makespan, i.e. the maximum completion time of the jobs. The operations of all jobs are processed on both machines in batches. A constant setup time is incurred whenever a batch is formed on the machines. The processing time of a batch is defined as the setup time plus the sum of all processing times of the jobs it contains. The completion time of a job is defined as the time at which the batch containing it is completely processed on machine two. The no-wait scheduling problem in the two-machine flowshop without batching is known as polynomially solvable. We show that several restricted versions of the problem under study in this paper are strongly N P-hard, which imply that the general problem is also strongly N P-hard. We then establish some interesting properties and exploit them to design solution methods for two special cases.
Original languageEnglish
Pages (from-to)613-624
Number of pages12
JournalComputers and Operations Research
Issue number7
Publication statusPublished - 1 Jun 2001


  • Batching
  • Computational complexity
  • Flowshop scheduling
  • Makespan
  • No-wait

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Batch scheduling in the no-wait two-machine flowshop to minimize the makespan'. Together they form a unique fingerprint.

Cite this