Minimizing completion time variance with compressible processing times

We introduce a new formulation of the standard completion time variance (CTV) problem with n jobs and one machine in which the job sequence and the processing times of the jobs are all decision variables. The processing time of job i (i=1, ⋯, n) can be compressed by an amount within [l_i u_i] which however will incur a compression cost. The compression cost is a general convex non-decreasing function of the amount of the job processing time compressed. The objective is to minimize a weighted combination of the completion time variance and the total compression cost. We show that under an agreeable condition on the bounds of the processing time compressions a pseudo-polynomial algorithm can be derived to find an optimal solution for the problem. Based on the pseudo-polynomial time algorithm two heuristic algorithms H1 and H2 are proposed for the general problem. The relative errors of both heuristic algorithms are guaranteed to be no more than δ where δ is a measure of deviation from the agreeable condition. While H1 can find an optimal solution for the agreeable problem H2 is dominant for solving the general problem. We also derive a tight lower bound for the optimal solution of the general problem. The performance of H2 is evaluated by complete enumeration for small n and by comparison with this tight lower bound for large n. Computational results (with n up to 80) are reported which show that the heuristic algorithm H2 in general can efficiently yield near optimal solutions when n is large.