Parallel-machine batching and scheduling to minimize total completion time

Edwin Tai Chiu Cheng, Z. L. Chen, M. Y. Kovalyov, B. M.T. Lin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

39 Citations (Scopus)


We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on m identical parallel machines. The jobs have to be batched as well as scheduled. The completion time of a job is defined as the completion time of the batch containing it. A constant set-up time is incurred whenever a batch is formed. The problem is to batch and schedule jobs so that the total completion time of the jobs is minimized. We first present some properties and then develop a dynamic programming algorithm to solve this problem. The running time of our algorithm is O(mnm+1). When job processing times are identical, we show that the problem reduces to the corresponding single-machine problem, which has been well solved in the literature.
Original languageEnglish
Pages (from-to)953-956
Number of pages4
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number11
Publication statusPublished - 1 Jan 1996

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Cite this