New insights on the single machine total tardiness problem


Creative Commons License

Tansel B., Sabuncuoglu İ.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, cilt.48, ss.82-89, 1997 (SCI İndekslerine Giren Dergi)

  • Cilt numarası: 48 Konu: 1
  • Basım Tarihi: 1997
  • Doi Numarası: 10.1057/palgrave.jors.2600321
  • Dergi Adı: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Sayfa Sayısı: ss.82-89

Özet

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.