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

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 ≤ 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.