Scheduling to minimize weighted earliness and tardiness about a common due-date

This paper examines the problem of sequencing a set of independent jobs on a single processor so as to minimize the sum of weighted absolute deviations of job completion times about a specified due-date. In contrast with prior research on this topic, no restriction is imposed on the due-date. The resulting problem is known to be computationally difficult. It is shown that the solution to this problem can be derived from solutions to different subproblems. Properties of these subproblems are identified and used to develop exact algorithm of pseudo-polynomial complexity. The same algorithms are modified to yield a fully polynomial approximation scheme with a constant performance guarantee. The paper also discusses interesting special cases which are amenable to easier solutions.