实时无等待HFS调度的一种拉格朗日松弛算法

研究了实时无等待HFS调度问题，并建立一个整数规划模型，提出运用拉格朗日松弛算法来求解，在此算法中，常采用次梯度方法更新拉格朗日乘子，但它随着迭代数的增加收敛速度会减慢，因此设计了一个改进的bundle方法。将以前的次梯度累积到bundle中，以获得一个更好的乘子更新方向．仿真实验表明，与次梯度方法相比，所设计的bundle法不仅在较少的迭代数内得到了更快的收敛速度而且改进了优化性能，对于大规模问题效果更为显著。

Lagrangian Relaxation Algorithm for Real-time Hybrid Flowshop Scheduling with No-wait in Process

The no-wait hybrid flowshop scheduling problem in a real-time environment is formulated as an integer programming model which has been proven NP-hard. A solution methodology based on Lagrangian relaxation is presented. In this method, the subgradient algorithm is commonly used to update Lagrange multipliers. However, the zigzagging behavior of subgradient optimization motivates the development of an improved bundle approach that accumulates the past subgradients in a bundle to achieve a better direction. Testing results show that the designed bundle approach provides a faster convergence and a better performance within less iteration, especially for largescale problems, comparing with subgradient method.