Minimizing the flow-time variance in single-machine systems

In this paper the authors deal with an n-job, single-machine scheduling problem. All jobs are available from the start, and the objective is to minimize the variance of job flow-times. A heuristic procedure which is based on the complementary pair-exchange principle is proposed. It has been concluded that this heuristic procedure provides improved results (in terms of objective-function value) when compared with other heuristics. The present heuristic procedure has the complexity of O(nlogn).