北京航空航天大学学报 ›› 2009, Vol. 35 ›› Issue (3): 330-333.

• 论文 • 上一篇    下一篇

多机多窗口优化调度问题的模型与算法

刘 伟, 孟 新, 郑建华   

  1. 中国科学院空间科学与应用研究中心, 北京 100190
  • 收稿日期:2008-03-11 出版日期:2009-03-31 发布日期:2010-09-16
  • 作者简介:刘 伟(1981-),男,安徽合肥人,博士生,wei_liu@cssar.ac.cn.

Multi-machine scheduling problem with multi-time windows: model and algorithm

Liu Wei, Meng Xin, Zheng Jianhua   

  1. Center for Space Science and Applied Research,Chinese Academy of Science, Beijing 100190, China
  • Received:2008-03-11 Online:2009-03-31 Published:2010-09-16

摘要: 最小化完工费用且具有多个时间窗口的多机调度问题,一直是组合优化领域的一个研究难点.首先给出描述问题的2种模型:整数规划IP(Integer Programming)模型,约束规划CP(Constraint Programming)模型.通过对IP模型和CP模型各自缺点的讨论,引出一个新的模型——混合IP-CP模型,重点讨论了该混合模型的求解方法,给出一个模型求解的启发式算法,经测试表明新模型和算法能极大地提高问题求解效率,为解决此类大规模优化调度问题提供了方法.

Abstract: With regard to the multi-machine scheduling problem with multi-time windows for minimizing the cost,how to solve the question quickly and effectively remains to be a hard problem in combination optimization research field. Firstly two models were established to describe the simplified questions during the study of optimization,including an integer programming(IP)model and a constraint programming (CP) model. By discussing the defects of the IP model and CP model,a new hybrid IP-CP model was constructed. In addition,a heuristic algorithm was applied to solve the hybrid IP-CP model. Result of the tests indicate that the hybrid IP-CP model and heuristic algorithm developed are proved to be feasible and effective for the multi-machine scheduling problem with multi-time windows,especially for the large-scale scheduling problem.

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发