单机调度问题对偶集结迭代算法

具有到达时间约束、目标为最小化加权完工时间之和的单机调度问题是一个典型的NP-hard问题,采用时间下标建模的线性规划松弛方法可提供一个很强的下界,但优化求解存在维数困难.为此,本文提出了一种对偶集结优化策略,通过选择一个衰减集结矩阵集结对偶乘子变量,利用对偶理论获得模型的约束集结,从而降低计算复杂度.同时分析了集结模型的结构特性,并提出一种迭代算法来改善下界.仿真结果表明对偶集结迭代算法能够减少计算时间,同时改善下界性能,适用于大规模调度问题.

A dual aggregated iterative algorithm for single machine scheduling problems

The scheduling problem of minimizing the weighted completion time of n jobs with release dates on a single machine is strongly NP-hard. Its linear-programming relaxation based on time-indexed formulation provides a strong lower bound. However the number of constraints and variables can be large even for relative small instances. In this paper, a dual aggregated strategy is proposed to decrease the numbers of constraints by aggregating the dual multipliers with a decaying aggregation matrix. The structural properties of the aggregated model are also analyzed. An iterative method is proposed to improve the lower bound. Simulation results show that the dual aggregated iterative algorithm can reduce running time and improve lower bound. The application of these techniques still allows large-scale scheduling problems.