Single-Machine Scheduling of Unit-Time Jobs with Earliness and Tardiness Penalties

The problem of determining a schedule of jobs with unit-time lengths on a single machine that minimizes the total weighted earliness and tardiness penalties with respect to arbitrary rational due-dates is formulated as an integer programming problem. We show that if the penalties meet a certain criterion, called the Dominance Condition, then there exists an extremal optimal solution to the LP-relaxation that is integral, leading to a polynomial-time solution procedure. The general weighted symmetric penalty structure is one cost structure that satisfies the Dominance Condition; we point out other commonly found penalty structures that also fall into this category.