An efficient algorithm for the single machine total tardiness problem

Creative Commons License

Tansel B., Kara B., Sabuncuoglu İ.

IIE TRANSACTIONS, cilt.33, sa.8, ss.661-674, 2001 (SCI İndekslerine Giren Dergi) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 33 Konu: 8
  • Basım Tarihi: 2001
  • Doi Numarası: 10.1023/a:1010931215795
  • Sayfa Sayıları: ss.661-674


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.