Minimizing Single-Machine Completion Time Variance
研究单机调度中最小化完工时间方差的问题，提出新的二次整数规划模型和拉格朗日松弛方法求下界，并设计两阶段启发式算法，在100-500个作业的测试中表现优于已知算法。
In this article the problem of minimizing the completion time variance in n-job, single-machine scheduling is considered. The release times for all jobs are assumed to be zero. A new quadratic integer programming formulation is introduced. A Lagrangian relaxation (LR) procedure is developed to find a lower bound (LB) to the optimal objective value. When the number of jobs is between 100 and 500, our computational study shows that the lower bounds obtained by the LR procedure are very close to the best known objective values. A new heuristic algorithm is also described. The first phase of the heuristic algorithm is a construction procedure whose purpose is to identify a good initial sequence. The second phase is an improvement procedure based on pairwise interchanges. The new heuristic algorithm provides improved solutions compared to the best known heuristic.