单机调度问题对偶集结迭代算法

• 作者: 左燕 王建中 薛安克
• 来源期刊: 控制理论与应用
• 关键词: 单机调度 线性规划松弛 对偶集结 时间下标建模
• 年，卷（期）: 2010,（12）
• 页码范围: 1793-1797
• 分类号: TP273
• 语种: 中文

摘要

具有到达时间约束、目标为最小化加权完工时间之和的单机调度问题是一个典型的NP-hard问题,采用时间下标建模的线性规划松弛方法可提供一个很强的下界,但优化求解存在维数困难.为此,本文提出了一种对偶集结优化策略,通过选择一个衰减集结矩阵集结对偶乘子变量,利用对偶理论获得模型的约束集结,从而降低计算复杂度.同时分析了集结模型的结构特性,并提出一种迭代算法来改善下界.仿真结果表明对偶集结迭代算法能够减少计算时间,同时改善下界性能,适用于大规模调度问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	薛安克	杭州电子科技大学信息与控制研究所	104	687	13.0	20.0
2	左燕	杭州电子科技大学信息与控制研究所	24	53	5.0	5.0
3	王建中	杭州电子科技大学信息与控制研究所	59	341	10.0	14.0