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 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 48 Issue: 1
  • Publication Date: 1997
  • Doi Number: 10.1057/palgrave.jors.2600321
  • Journal Name: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Page Numbers: pp.82-89
  • Abdullah Gül University Affiliated: No

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.