Minimizing the mean squared deviation from a common due date: unconstrained and constrained cases

Abstract

The problem of minimizing the mean squared deviation (MSD) of completion times from a common due date in both unconstrained and constrained cases is addressed. It is shown that the unconstrained MDS function is unimodal for n ≤ 6, where n is the number of jobs. The constrained case is shown to be unimodular for n ≤ 3, The unconstrained case is shown, by counterexample, not to be unimodular for n = 8. The constrained case is shown not to be unimodular for n = 5. For the unimodular cases, a proposed search routine can find the optimum solution in less than three CPU seconds for n = 100. It provides an excellent heuristic solution otherwise. Computational results are shown in both cases.

Keywords:

• scheduling
• earliness
• tardiness