JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, vol.48, no.1, pp.82-89, 1997 (SCI-Expanded)
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.