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.