NEW RESULTS ON THE COMPLETION-TIME VARIANCE MINIMIZATION

A single machine scheduling problem where the objective is to minimize the variance of job completion times is considered. The model is appl icable to many environments where it is desirable to provide jobs, cus tomers or computer files, with approximately the same service. It is s hown that the problem can be formulated as a problem of maximizing a z ero-one quadratic function which is a submodular function with a speci al cost structure. It immediately follows from the cost structure that value of the function for a sequence that minimizes total absolute de viation about a common unrestrictive due date is at most 100% smaller than the one for an optimal sequence for the completion time variance problem. The Monge property holds for the costs. Other simple properti es of the function are also presented. A pair of dynamic programs for maximizing the function is proposed. The worst case time complexity of the best of the pair is O (n(2)spt), where spt is the mean flow time of an SPT-schedule for all jobs except the longest one.