Multi-machine scheduling problem with multi-time windows: model and algorithm
-
摘要: 最小化完工费用且具有多个时间窗口的多机调度问题,一直是组合优化领域的一个研究难点.首先给出描述问题的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.
-
Key words:
- multi-machine scheduling /
- hybrid IP-CP model /
- heuristic algorithm
-
[1] Cheng T.A state-of-the-art review of parallel machine scheduling research [J]. European Journal of Operation Research,1990,47:271-292 [2] Fisher M. The Lagrangian relaxation method for solving integer programming problems [J]. Mgmt Sci,1981,27:1-18 [3] Muckstadt J A,Koening S A. An application of Lagrangian relaxation to scheduling in power-generation systems [J]. Oper Res,1977,25: 387-403 [4] Dincbas M. The constraint logic programming language CHIP [J]. Proceedings of International Conference on Fifth Generation Computer Systems, 1988,1:693-702 [5] Akker V. Time-indexed formulations for machine-scheduling problems: column generation [J]. Informs J Comput,2000,12(2):111-124 [6] Hoitomt D. Scheduling job with simple precedence constraints on parallel machines [J]. Control Syst Mag,1990,10:34-40 -
点击查看大图
计量
- 文章访问数: 3036
- HTML全文浏览量: 116
- PDF下载量: 1038
- 被引次数: 0
下载:
