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

轩华¹，唐立新²

1. 东北大学教育部暨辽宁省流程工业综合自动化重点实验室2. 东北大学物流优化与控制研究所

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

关键词：实时混合流水车间调度;无等待;整数规划;拉格朗日松弛;改进的bundle法;