Single machine scheduling to minimize weighted earliness subject to maximum tardiness

In this paper, the authors study the problem of scheduling n jobs on a single machine to minimize the weighted earliness subject to a maximum tardiness for each job. This generalizes earlier work which is subject to deadline constraints. They derive several precedence relationship between jobs. These relationships are incorporated in a branch and bound solution procedure to curtail the enumeration. Because of the computational complexity of the problem, a heuristic algorithm in O(n²) time is developed. Both algorithm are tested via as computational study.