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

LR & CG algorithm for parallel machine real-time scheduling problem

作　　者：汪恭书[1] 唐立新[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110819

出　　处：《控制与决策》2013年第6期829-836,共8页Control and Decision

基　　金：国家自然科学基金重点项目(71032004);国家自然科学基金青年基金项目(71202151);高等学校博士学科点专项科研基金项目(20090042120038)

摘　　要：研究了目标函数为最小化总加权完成时间的并行机实时调度问题.建立该问题混合整数规划模型,并提出融合拉格朗日松弛(LR)和列生成(CG)的LR&CG混合算法.该算法包含双重迭代,在内环以次梯度法作为下界求解器和列生成器,在外环通过求解限制主问题来获得影子价格以调节拉格朗日乘子.计算实验结果表明,在相同的计算时间内,LR&CG能够比常规的LR算法获得更好的上界和下界,表明了前者具有更好的收敛性能.@@@@The parallel machine real-time scheduling problem with objective of minimizing total weighted completed time is investigated. The problem is formulated as a mixed integer programming model, and a LR & CG hybrid algorithm which combines Lagrangian relaxation(LR) with column generation(CG) together is proposed to solve it. The LR & CG algorithm contains double loops. In the inner loop, the subgradient method is executed to calculate lower bound and generate columns, and in the outer loop the restricted master problem is solved to get shadow price which is used to adjust Lagrangian multiples. The results of computational experiment show that the LR & CG algorithm can obtain tighter lower bound and higher quality upper bound than the conventional LR algorithm within the same computational time, which implies that the previous one has better convergent performance.

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

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]