We consider the problem of minimising variance of completion times when n-jobs are to be processed on a single machine. This problem is known as the CTV problem. The problem has been shown to be difficult. In this paper we consider the polytope Pn whose vertices are in one-to-one correspondence with the n! permutations of the processing times [p1, p2, …, pn]. Thus each vertex of Pn represents a sequence in which the n-jobs can be processed. We define a V-shaped local optimal solution to the CTV problem to be the V-shaped sequence of jobs corresponding to which the variance of completion times is smaller than for the sequences adjacent to it on Pn. We show that this local solution dominates V-shaped feasible solutions of the order of 2n-3 where 2n-2 is the total number of V-shaped feasible solutions. Using adjacency structure of Pn, we develop a heuristic for the CTV problem which has a running time of low polynomial order, which is exact for n = 10, and whose domination number is O(2n-3). In the end we mention two other classes of scheduling problems for which also ADJACENT provides solutions with the same domination number as for the CTV problem.
