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

33 Citations (Scopus)

Abstract

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
Volume28
Issue number7
DOIs
Publication statusPublished - 1 Jun 2001

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this