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 s ingle machine that minimizes the total weighted earliness and tardiness pen alties with respect to arbitrary rational due-dates is formulated as an int eger programming problem. We show that if the penalties meet a certain crit erion, called the Dominance Condition, then there exists an extremal optima l solution to the LP-relaxation that is integral, leading to a polynomial-t ime solution procedure. The general weighted symmetric penalty structure is one cost structure that satisfies the Dominance Condition; we point out ot her commonly found penalty structures that also fall into this category.