Batch delivery scheduling on a single machine

Edwin Tai Chiu Cheng, V. S. Gordon

Research output: Journal article publicationJournal articleAcademic researchpeer-review

33 Citations (Scopus)


The problem of partitioning a set of independent and simultaneously available jobs into batches and sequencing them for processing on a single machine is presented. Jobs in the same batch are to be delivered together, upon completion of the last job in the batch. Jobs finished before this time have to wait until delivery. There are a delivery cost depending on the number of batches formed and an earliness cost for jobs finished before delivery. The dynamic programming approach to minimizing the total cost is considered, yielding two pseudopolynomial algorithms when the number of batches has a fixed upper bound. A polynomial algorithm for a special case of the problem is also presented.
Original languageEnglish
Pages (from-to)1211-1215
Number of pages5
JournalJournal of the Operational Research Society
Issue number10
Publication statusPublished - 1 Jan 1994


  • Batching
  • Scheduling
  • Sequencing

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing


Dive into the research topics of 'Batch delivery scheduling on a single machine'. Together they form a unique fingerprint.

Cite this