Batching and scheduling to minimize the makespan in the two-machine flowshop

Edwin Tai Chiu Cheng, Guoqing Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

40 Citations (Scopus)


In this paper, we consider a class of batching and scheduling problems in the two-machine flowshop where one of the machines is a discrete processor and the other one is a batch processor. The jobs are processed separately on the discrete processor and processed in batches on the batch processor. The processing time of a batch is equal to the total processing time of the jobs contained in it, and the completion time of a job in a batch is defined as the completion time of the batch containing it. A constant setup time is incurred whenever a batch is formed on the batch processor. The problem is to find the optimal batch compositions and the optimal schedule of the batches so that the makespan is minimized. All problems in this class are shown to be NP-complete in the ordinary sense. We also identify some polynomially solvable cases by introducing their corresponding solution methods.
Original languageEnglish
Pages (from-to)447-453
Number of pages7
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number5
Publication statusPublished - 1 Jan 1998

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Cite this