Single machine scheduling to minimize batch delivery and job earliness penalties

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov, Bertrand M.T. Lin

Research output: Journal article publicationJournal articleAcademic researchpeer-review

31 Citations (Scopus)


We study a problem in which a set of n jobs has to be batched as well as scheduled for processing on a single machine. A constant machine set-up time is required before the first job of each batch is processed. A schedule specifies the sequence of batches, where each batch comprises a sequence of jobs. The batch delivery time is defined as the completion time of the last job in a batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and the job completion time. The objective is to find a number B of batches and a schedule so as to minimize the sum of the total weighted job earliness and mean batch delivery time. The problem is shown to be strongly N P-hard. It remains strongly N P-hard if the set-up time is zero and B ≤ U for any variable U ≥ 2 or if B ≥ U for any constant U ≥ 2. The problem is proved to be ordinary N P-hard even if the set-up time is zero and B ≤ 2. For the case B ≤ U, a dynamic programming algorithm is presented, which is pseudopolynomial for any constant U ≥ 2. Algorithms with O(n2) running times are derived for the cases when all weights are equal or all processing times are equal. For the general problem, a family of heuristics is suggested. Computational experiments on the proposed heuristic algorithm are conducted. The results suggest that the heuristics are effective in generating near-optimal solutions quickly.
Original languageEnglish
Pages (from-to)547-559
Number of pages13
JournalSIAM Journal on Optimization
Issue number2
Publication statusPublished - 1 Jan 1997


  • Batch scheduling
  • Dynamic programming
  • N P-hardness
  • Polynomial algorithms
  • Single machine scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science


Dive into the research topics of 'Single machine scheduling to minimize batch delivery and job earliness penalties'. Together they form a unique fingerprint.

Cite this