We consider the problem of minimizing the weighted sum of earliness and tardiness of jobs scheduled around a common due date, d. The weight of a job may vary, depending upon whether that job is early or late, as well as varying between jobs. We assume that d is late enough not to influence the schedule. The problem can be equivalently stated as an unconstrained quadratic zero-one program. We demonstrate that the optimal solution of problem instances with up to 50 jobs (compared to 20 jobs in the best previous study) is possible, and provide computational results. A heuristic procedure based on tabu search techniques is designed and tested. For problem instances with up to 500 jobs, the heuristic solutions generated are routinely very close to optimal in cost. Moreover, we demonstrate statistically that the relative gap between heuristic solution cost and an easily found lower bound on optimal cost decreases exponentially with the number of jobs. Finally, we describe several special cases of the problem which are optimally solvable in pseudo-polynomial, or in polynomial, time.
Published April 1992 , 22 pages