CON due-date determination and sequencing

We consider a CON due-date problem where the objective is to determine an optimal sequence S* and the associated optimal due-date d* which will minimize the total weighted earliness and tardiness of jobs. Except in some special cases, moderate to large instances of the problem cannot be solved in reasonable time with the existing methodology. This paper presents solution strategies that are more effective. A 0–1 quadratic programming formulation, branch and bound schemes based on recursion, and dynamic programming algorithms are used for finding exact solutions to the problem. A simple heuristic based on the 0–1 programming approach is also proposed. Results of a computational study are reported to show the relative effectiveness of the different methods.