Single machine scheduling with batch deliveries

Edwin Tai Chiu Cheng, Valery S. Gordon, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

115 Citations (Scopus)


The single machine batch scheduling problem is studied. The jobs in a batch are delivered to the customer together upon the completion time of the last job in the batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and its completion time. The objective is to minimize the sum of the batch delivery and job earliness penalties. A relation between this problem and the parallel machine scheduling problem is identified. This enables the establishment of complexity results and algorithms for the former problem based on known results for the latter problem.
Original languageEnglish
Pages (from-to)277-283
Number of pages7
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 25 Oct 1996


  • Batching
  • Parallel machine scheduling
  • Single machine scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this