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

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