Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem
研究了单机调度中最小化完工时间方差的NP难问题，提出一个O(n log n)时间构造的序列，证明在加工时间服从均匀分布时该序列渐近最优，相对误差依概率收敛到零。
Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well-known NP-hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optimality of the sequence within the framework of probabilistic analysis. Our main result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically optimal in the sense that its relative error converges to zero in probability as n increases. Other theoretical results are also derived, including: (i) When the processing times follow a symmetric structure, the problem has 2⌊(n−1)/2⌋ optimal sequences, which include our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2⌊(n−1)/2⌋ sequences are used as approximate solutions for a general problem, our proposed sequence yields the best approximation (in an average sense) while another sequence, which is commonly believed to be a good approximation in the literature, is interestingly the worst. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 373–398, 1999