The minimization of the weighted completion time variance in a single machine: A specialized cutting-plane approach

This study addresses the problem of minimizing the weighted completion time variance (WCTV) in single-machine scheduling. Unlike the unweighted version, which has been extensively studied, the weighted variant introduces unique challenges due to the absence of theoretical properties that could guide the design of efficient algorithms. We propose a mathematical programming framework based on a novel decomposition of the WCTV measure and show that its baseline form provides a valid lower bound for both the WCTV minimization and the minimization of the sum of weighted mean squared deviations from a common due date. To improve computational efficiency, we develop a specialized cutting-plane algorithm that incorporates lazy constraints. The methodology is evaluated through extensive numerical experiments, demonstrating the strength of the derived bounds, which consistently outperform existing benchmarks.