Batching and scheduling in a multi-machine flow shop

Chi To Ng, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

20 Citations (Scopus)


We study the problem of batching and scheduling n jobs in a flow shop comprising m, m2, machines. Each job has to be processed on machines 1,m in this order. Batches are formed on each machine. A machine dependent setup time precedes the processing of each batch. Jobs of the same batch are processed on each machine sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs of the same batch formed on machine l become available for a downstream operation on machine l+1 at the same time when the processing of the last job of the batch on machine l has been finished. The objective is to minimize maximum job completion time. We establish several properties of an optimal schedule and develop polynomial time algorithms for important special cases. They are improvements over the existing methods with regard to their generality and time efficiency.
Original languageEnglish
Pages (from-to)353-364
Number of pages12
JournalJournal of Scheduling
Issue number6
Publication statusPublished - 1 Dec 2007


  • Batching
  • Dynamic programming
  • Flow shop
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence


Dive into the research topics of 'Batching and scheduling in a multi-machine flow shop'. Together they form a unique fingerprint.

Cite this