Single machine scheduling to minimize batch delivery and job earliness penalties

T. C.Edwin Cheng*, Mikhail Y. Kovalyov, Bertrand M.T. Lin

*Corresponding author for this work

Research output: Contribution to journalArticle

29 Scopus citations

Abstract

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
Volume7
Issue number2
DOIs
StatePublished - 1 Jan 1997

Keywords

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

Fingerprint 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