A branch and price algorithm for single-machine completion time variance

Abstract This paper studies a single machine scheduling problem to minimize the completion time variance (CTV) of all jobs. A new time-indexed quadratic programming formulation is proposed, in which the quadratic terms are further linearized into a mixed integer programming (MIP) with non-negative continuous variables. To solve the problem to optimality, a branch and price (BP) algorithm is designed, which combines the Lagrangian relaxation with clusters. Extensive computational experiments on three sets of benchmark problem instances and randomly generated ones are conducted and the results show that the proposed BP algorithm outperforms state-of-the-art approaches.