In this paper we discuss a single machine scheduling problem with the objective of minimizing the variance of job completion times. The CTV problem has been proved to be NP hard and no polynomial time algorithm exists to find an optimal solution for CTV minimization on single machine. Hence enumerative techniques and heuristics are used to get optimal and near optimal solutions, respectively. We present a branch and bound algorithm and extend the same algorithm to generate epsilon optimal solutions for large sized problems (i.e., number of jobs > 30). The algorithm has been computationally tested, with randomly generated problems involving up to 100 jobs, using a personal computer (PC) with a 64 MB RAM capacity. The computational time required for generating optimal solutions are a few seconds for problems with jobs between 25 and 30. The performance of the branch and bound algorithm is compared with the pseudo-polynomial algorithm for small sized problems. For problems with greater number of jobs, the epsilon optimal solutions obtained using branch and bound algorithm are compared with results of simulated annealing, tabu search and the heuristic proposed by Manna and Prasad.
