An efficient algorithm for the single machine total tardiness problem


Creative Commons License

Tansel B., Kara B., Sabuncuoglu İ.

IIE TRANSACTIONS, vol.33, no.8, pp.661-674, 2001 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 33 Issue: 8
  • Publication Date: 2001
  • Doi Number: 10.1023/a:1010931215795
  • Title of Journal : IIE TRANSACTIONS
  • Page Numbers: pp.661-674

Abstract

This paper presents an exact algorithm for the single machine total tardiness problem (1//SigmaT(i)). We present a new synthesis of various results from the literature which leads to a compact and concise representation of job precedences, a simple optimality check, new decomposition theory, a new lower bound, and a check for presolved subproblems. These are integrated through the use of an equivalence concept that permits a continuous reformation of the data to permit early detection of optimality at the nodes of an enumeration tree. The overall effect is a significant reduction in the size of the search tree, CPU times, and storage requirements. The algorithm is capable of handling much larger problems (e.g., 500 jobs) than its predecessors in the literature (less than or equal to 150). In addition, a simple modification of the algorithm gives a new heuristic which significantly outperforms the best known heuristics in the literature.