Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

Scheduling a set of n jobs on a single machine so as to minimize the comple tion time variance is a well-known NP-hard problem. In this paper, we propo se a sequence, which can be constructed in O(n log n) time, as a solution f or the problem. Our primary concern is to establish the asymptotical optima lity of the sequence within the framework of probabilistic analysis. Our ma in result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically o ptimal in the sense that its relative error converges to zero in probabilit y as n increases. Other theoretical results are also derived, including (i) When the processing times follow a symmetric structure, the problem has 2 (right perpendicular (n-1)/2 left perpendicular) Optimal sequences, which i nclude our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2( right perpendicular (n-1)/2 left perpen dicular) 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 approximati on in the literature, is interestingly the worst. (C) 1999 John Wiley & Son s, Inc.