| 引用本文: | 左燕,薛安克,王建中.单机调度问题对偶集结迭代算法[J].控制理论与应用,2010,27(12):1793~1797.[点击复制] |
| ZUO Yan,XUE An-ke,WANG Jian-zhong.A dual aggregated iterative algorithm for single machine scheduling problems[J].Control Theory and Technology,2010,27(12):1793~1797.[点击复制] |
|
| 单机调度问题对偶集结迭代算法 |
| A dual aggregated iterative algorithm for single machine scheduling problems |
| 摘要点击 1739 全文点击 1489 投稿时间：2010-05-07 修订日期：2010-10-13 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/j.issn.1000-8152.2010.12.PCTA100519 |
| 2010,27(12):1793-1797 |
| 中文关键词 单机调度 线性规划松弛 对偶集结 时间下标建模 |
| 英文关键词 single machine scheduling linear-programming relaxation dual aggregation time-indexed formulation |
| 基金项目 国家“973”计划资助项目(2009CB320602); 国家自然科学基金资助项目(40974102,61004119). |
|
| 中文摘要 |
| 具有到达时间约束、目标为最小化加权完工时间之和的单机调度问题是一个典型的NP-hard问题, 采用时间下标建模的线性规划松弛方法可提供一个很强的下界, 但优化求解存在维数困难. 为此, 本文提出了一种对偶集结优化策略, 通过选择一个衰减集结矩阵集结对偶乘子变量, 利用对偶理论获得模型的约束集结, 从而降低计算复杂度. 同时分析了集结模型的结构特性, 并提出一种迭代算法来改善下界. 仿真结果表明对偶集结迭代算法能够减
少计算时间, 同时改善下界性能, 适用于大规模调度问题. |
| 英文摘要 |
| The scheduling problem of minimizing the weighted completion time of n jobs with release dates on a single machine is strongly NP-hard. Its linear-programming relaxation based on time-indexed formulation provides a strong lower bound. However the number of constraints and variables can be large even for relative small instances. In this paper, a dual aggregated strategy is proposed to decrease the numbers of constraints by aggregating the dual multipliers with a decaying aggregation matrix. The structural properties of the aggregated model are also analyzed. An iterative method is proposed to improve the lower bound. Simulation results show that the dual aggregated iterative algorithm can reduce running time and improve lower bound. The application of these techniques still allows large-scale scheduling problems. |