并行机实时调度问题的 LR & CG 算法

摘要：

研究了目标函数为最小化总加权完成时间的并行机实时调度问题.建立该问题混合整数规划模型,并提出融合拉格朗日松弛(LR)和列生成(CG)的 LR & CG 混合算法.该算法包含双重迭代,在内环以次梯度法作为下界求解器和列生成器,在外环通过求解限制主问题来获得影子价格以调节拉格朗日乘子.计算实验结果表明,在相同的计算时间内, LR & CG 能够比常规的 LR 算法获得更好的上界和下界,表明了前者具有更好的收敛性能.

关键词：并行机调度、拉格朗日松弛、次梯度、列生成、状态空间松弛

分类号：TP273(自动化技术及设备)

在线出版日期：2013-06-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：829-836