Single-machine earliness-tardiness scheduling about a common due date with tolerances

Michael X. Weng, Jose A. Ventura

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


In this paper the problem of minimizing the mean absolute deviation (MAD) of job completion times about a given common due date with different sizes of tolerance in an n-job, single-machine scheduling environment is considered. We describe some optimality conditions and show that the problem is NP-complete. A heuristic algorithm is proposed to find an approximate solution to the problem. A pseudo-polynomial dynamic programming algorithm is also proposed to optimally solve the problem if the agreement condition defined in the paper holds. The dynamic programming algorithm can also be used to find a lower bound for the problem by adjusting the tolerances of some jobs. An example is provided to illustrate the proposed methods. A computational study on randomly generated test problems is conducted to investigate the performance of the proposed heuristic and the quality of lower bounds generated by the dynamic programming method. Computational results are reported.

Original languageEnglish (US)
Pages (from-to)217-227
Number of pages11
JournalInternational Journal of Production Economics
Issue number3
StatePublished - Apr 1 1996

All Science Journal Classification (ASJC) codes

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Single-machine earliness-tardiness scheduling about a common due date with tolerances'. Together they form a unique fingerprint.

Cite this