Pseudopolynomial algorithms for CTV minimization in single machine scheduling

The problem of scheduling jobs on a single machine so as to minimize completion time variance (CTV) is considered. In this article, we have derived two dominance criteria and used them in the development of a new pseudopolynomial algorithm. This algorithm is an implicit enumeration scheme based on a binary branching strategy, with larger jobs fixed at early stages, and is superior to those of De et al . and Kubiak in terms of computational complexity. It is observed that this algorithm is very good when the job processing times are quite heterogeneous, while the algorithm of De et al . is excellent for homogeneous processing times. By making use of these contrasting merits, another pseudopolynomial algorithm is then proposed. Results of extensive numerical investigation on the performances of the algorithms are also reported.