基于模型分解的多机带时间窗口任务规划算法

计算机应用 ›› 2010, Vol. 30 ›› Issue (11): 2867-2869.

基于模型分解的多机带时间窗口任务规划算法

张利宁¹,邱涤珊²,李皓平²,黄小军²

1. 国防科技大学信息系统与管理学院指挥自动化系4室
2.

收稿日期:2010-04-12 修回日期:2010-06-20 发布日期:2010-11-05 出版日期:2010-11-01
通讯作者: 张利宁
基金资助:
面向任务的航天资源动态组织机理

Task scheduling algorithm based on model decomposition for multi-machine with time windows

Received:2010-04-12 Revised:2010-06-20 Online:2010-11-05 Published:2010-11-01

摘要/Abstract

摘要： 针对多机带时间窗口任务规划问题,提出了基于模型分解的规划求解算法。通过引入基于逻辑的Benders分解方法,将经典Benders分解算法应用扩展至带离散时间窗口的混合线性整数规划模型,实现模型分解。采用工艺级商业软件MOSEK与GECODE分别求解主、子问题,同时给出Benders剪枝函数生成方法,以迭代方式收敛解空间获得可行解。实现算法并设计测试案例,实验结果验证了算法的有效性。

关键词: 模型分解, 任务规划, 时间窗口, 组合优化

Abstract: The algorithm based on model decomposition was proposed for the problem of multi-machine task scheduling with time windows. The classical Benders decomposition was extended into the field of mixed integer linear programming model by introducing the logic based Benders decomposition. The states of art software MOSEK and GECODE were deployed to solve the master and sub-problems respectively. The method of generating Benders cuts was presented. The solution space was converged to a satisfied feasible solution through running the algorithm iteratively. The algorithm was implemented and tested by testing cases, and its effectiveness was verified.

Key words: Model decomposition, Task scheduling, Time windows, Combinatorial optimization

张利宁邱涤珊李皓平黄小军. 基于模型分解的多机带时间窗口任务规划算法[J]. 计算机应用, 2010, 30(11): 2867-2869.

[1]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[2]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.
[3]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[4]	李章洪, 梁晓磊, 田梦丹, 周文峰. 求解排列组合问题的解空间动态缩减策略[J]. 计算机应用, 2020, 40(7): 2016-2020.
[5]	杨云亭, 王鹏. 求解旅行商问题的多尺度量子自由粒子优化算法[J]. 计算机应用, 2020, 40(5): 1278-1283.
[6]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[7]	赵旭浩, 王轶群, 刘健, 徐春晖. 基于能量约束的自主水下航行器任务规划算法[J]. 计算机应用, 2019, 39(9): 2529-2534.
[8]	王吉祥, 过弋, 戚天梅, 王志宏, 李真, 汤敏伟. 嵌入互联网舆情强度的人民币汇率预测[J]. 计算机应用, 2019, 39(11): 3403-3408.
[9]	崔西宁, 董星廷, 牟明, 吴姣. 白盒攻击环境下的任务规划系统安全传输方法[J]. 计算机应用, 2017, 37(2): 483-487.
[10]	郭羽含, 张美琪, 周楠. 基于偏好矩阵遗传算法求解长期车辆合乘问题[J]. 计算机应用, 2017, 37(2): 602-607.
[11]	盛小东, 李强, 刘昭昭. 云环境下基于模板遗传算法的任务调度方法[J]. 计算机应用, 2016, 36(3): 633-636.
[12]	孙家泽, 耿国华. 基于群体智能的三维碎片全局最优匹配方法[J]. 计算机应用, 2016, 36(1): 266-270.
[13]	刘晓红, 曲志坚, 曹雁锋, 张先伟, 冯刚. 基于自适应机制的多宇宙并行量子衍生进化算法[J]. 计算机应用, 2015, 35(2): 369-373.
[14]	张晶, 吴虎胜. 改进二进制布谷鸟搜索算法求解多维背包问题[J]. 计算机应用, 2015, 35(1): 183-188.
[15]	张炎亮陈鑫李亚东. 小波神经网络模型的改进方法[J]. 计算机应用, 2013, 33(11): 3107-3110.