New insights on the single machine total tardiness problem


Creative Commons License

Tansel B., Sabuncuoglu İ.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, vol.48, no.1, pp.82-89, 1997 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 48 Issue: 1
  • Publication Date: 1997
  • Doi Number: 10.1057/palgrave.jors.2600321
  • Title of Journal : JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Page Numbers: pp.82-89

Abstract

Virtually all algorithmic studies on the single machine total tardiness problem use Emmons' theorems that establish precedence relations between job pairs. In this paper, we investigate these theorems with a geometric viewpoint. This approach provides a compact way of representing Emmons' theorems and promotes better insights into dominance properties. We use these insights to differentiate between certain classes of easy and hard instances.