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

摘要：

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

关键词：单机调度、线性规划松弛、对偶集结、时间下标建模

所属期刊栏目：27

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

资助基金：国家"973"计划资助项目2009CB320602;国家自然科学基金资助项目40974102,61004119

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

页数：共5页

页码：1793-1797