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

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

作　　者：张利宁[1] 邱涤珊[1] 李皓平[2] 黄小军[1] 

机构地区：[1]国防科学技术大学C4ISR技术重点实验室,长沙410073 [2]北方电子设备研究所,北京100191

出　　处：《计算机应用》2010年第11期2867-2869,2909,共4页journal of Computer Applications

基　　金：国家973计划项目(97361361)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]