MINIMIZATION OF AGREEABLY WEIGHTED VARIANCE IN SINGLE-MACHINE SYSTEMS

This paper considers the variance minimization problem with job-dependent weights. We show that an optimal job sequence must be V-shaped in terms of weighted processing time when the problem is agreeably weighted, in the sense that p(i) < p(i) implies w(i) greater than or equal to w(i), where p(i). and w(i) are the processing time and the weight of job i, respectively. An O(nWP) algorithm is proposed to find an optimal solution, where n is the number of jobs, W is the sum of weights, and P is the sum of processing times. Furthermore, an O(nP) algorithm is derived to obtain a sub-optimal solution lambda(lozenge). The relative error of lambda(lozenge) is guaranteed less than any pre-specified amount, and tends towards zero if W/w(min) grows at a rate slower than n(3) as n increases, where w(min) is the minimum weight. Particularly we show that, in the special case where all weights are equal, the O(nP) algorithm can find a solution with relative error bounded above by 3/((n - 1)(n - 2)) when n > 2. Numerical results are reported, which indicate that the O(nP) algorithm generated an optimal solution for almost every problem tested. Finally, two fully polynomial approximation schemes are presented for problems in which the weights are bounded above by a polynomial in n. The first one solves problems with p(max) less than or equal to 1/2P while the second one solves problems with p(max) > 1/2P, where p(max) is the maximum processing time