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 pi < pj implies wi ≥ wj, where pi and wi 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 λ. The relative error of λ is guaranteed less than any pre-specified amount, and tends towards zero if W/wmin grows at a rate slower than n3 as n increases, where wmin 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 while the second one solves problems with , where pmax is the maximum processing time.