Minimising Waiting Time Variance in the Single Machine Problem

Abstract

The paper considers the problem of n given jobs to be processed on a single machine where it is desirable to minimise the variance of job waiting times. A theorem is presented to the effect that the optimal sequence must be V-shaped (i.e., the jobs must be arranged in descending order of processing times if they are placed before the shortest job, but in ascending order of processing times if placed after it), and an algorithm for determining the optimal solution is given. A heuristic method is proposed for solving the problem where n is large; this method requires very little computing and was found to produce very good results for a sample of problems of varying size. The concept of the “efficient set” is examined and heuristic methods for generating this set are given.