Minimizing Mean Squared Deviation of Completion Times About a Common Due Date
研究单机调度中所有工件有共同交货期且无准备时间，目标是最小化完工时间与交货期的均方偏差，提出了一种高效求解无约束问题的算法，并改进了现有完工时间方差问题的求解方法。
This paper addresses a nonpreemptive single machine scheduling problem where all jobs have a common due date and have zero ready time. The scheduling objective is to minimize mean squared deviation (MSD) of job completion times about the due date. This nonregular measure of performance is appropriate when earliness and tardiness are both penalized, and when large deviations of completion time from the due date are undesirable. A special case of the MSD problem, referred to as the unconstrained MSD problem, is shown to be equivalent to the completion time variance problem (CTV) studied by Merten and Muller (Merten, A. G., M. E. Muller. 1972. Variance minimization in single machine sequencing problems. Management Sci. 18(September) 518–528.) and Schrage (Schrage, L. 1975. Minimizing the time-in-system variance for a finite jobset. Management Sci. 21(May) 540–543.). Strong results for this latter problem are combined with several new propositions to develop a reasonably efficient procedure for solving the unconstrained MSD problem. This enables us to improve the existing procedures for the CTV problem. We also propose a branching procedure for the constrained MSD problem and present computational results.