Single machine scheduling with symmetric earliness and tardiness penalties

José A. Ventura, Sanjay Radhakrishnan

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


This research focuses on scheduling jobs with varying processing times and distinct due dates on a single machine subject to earliness and tardiness penalties. Hence, this work will find application in a just-in-time (JIT) production environment. The scheduling problem is formulated as a 0-1 linear integer program with three sets of constraints, where the objective is to minimize the sum of the absolute deviations between job completion times and their respective due dates. The first two sets of constraints are equivalent to the supply and demand constraints of an assignment problem. The third set, which represents the process time non-overlap constraints, is relaxed to form the Lagrangian dual problem. The dual problem is then solved using the subgradient algorithm. Efficient heuristics have also been developed in this work to yield initial primal feasible solutions and to convert primal infeasible solutions to feasibility. The computational results show that the relative deviation from optimality obtained by the subgradient algorithm is less than 3% for problem sizes varying from 10 to 100 jobs.

Original languageEnglish (US)
Pages (from-to)598-612
Number of pages15
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - Feb 1 2003

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Single machine scheduling with symmetric earliness and tardiness penalties'. Together they form a unique fingerprint.

Cite this