New insights on the single machine total tardiness problem

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