Single machine scheduling to minimize total weighted tardiness

Edwin Tai Chiu Cheng, Chi To Ng, J. J. Yuan, Z. H. Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

42 Citations (Scopus)

Abstract

The problem of minimizing the total weighted tardiness in single machine scheduling is a well-known strongly NP-hard problem. In this paper, we present an O(n2) time approximation algorithm for the problem, where n is the number of jobs. We further investigate different sub-models of the problem and obtain interesting properties and results. We begin with the model where the job due dates are affine-linear functions of their processing times and the job tardiness weights are proportional to their processing times. For this model, we classify the NP-hardness of the problem with respect to different affine-linear functions, and provide an O(nlogn) algorithm for each of the polynomially solvable problems. The second model we investigate is one where all job due dates have equal slacks, namely the SLK due-date model. Results for this model include: the problem is NP-hard in the ordinary sense; a pseudo-polynomial algorithm with time complexity O(n2P) is derived, where P is the sum of all of the processing times; and a fully polynomial-time approximation scheme is constructed.
Original languageEnglish
Pages (from-to)423-443
Number of pages21
JournalEuropean Journal of Operational Research
Volume165
Issue number2
DOIs
Publication statusPublished - 1 Sep 2005

Keywords

  • Due dates
  • Processing-plus-wait
  • Single machine scheduling
  • SLK due-dates
  • Tardiness

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this