Constraint propagation for cumulative scheduling problems with precedences

被引：2
作者：
Liu S.-X. [1 ,2 ]
Guo Z. [1 ,2 ]
Tang J.-F. [1 ,2 ]
机构：
[1] College of Information Science and Engineering, Northeastern University
[2] Key Laboratory of Process Industry Automation, Northeastern University
来源：
Zidonghua Xuebao/ Acta Automatica Sinica | 2010年 / 36卷 / 04期
关键词：
Constraint programming; Constraint propagation (CP); Cumulative scheduling problem (CuSP); Precedence;
D O I：
10.3724/SP.J.1004.2010.00603
中图分类号：
学科分类号：
摘要：
Constraint propagation is one of the key elements of constraint programming. After presenting supporting theories of constraint propagation for cumulative scheduling problems (CuSP), the authors propose a constraint propagation algorithm in which both precedence constraints and activity time bound constraints are taken into consideration. By citing two sets of benchmark problems of PSPLIB to test the algorithm, experimental results show that the new algorithm outperforms existing constraint propagation algorithms for the testing problems. Moreover, the new algorithm and the energetic reasoning algorithm may complement each other. A hybrid one of the two algorithms is promising. Copyright © 2010 Acta Automatica Sinica. All rights reserved.
引用
收藏
页码：603 / 609
页数：6
相关论文
共 20 条
  • [1] Carlier J., Pinson E., An algorithm for solving the job shop problem, Management Science, 35, 2, pp. 164-176, (1989)
  • [2] Muth J.F., Thompson G.L., Industrial Scheduling, (1963)
  • [3] Baptiste P., Le Pape C., Nuijten W., Constraint Based Scheduling, (2001)
  • [4] Nuijten W., Time and resource constrained scheduling: a constraint satisfaction approach, (1994)
  • [5] Mercier L., Hentenryck P.V., Strong polynomiality of resource constraint propagation, Discrete Optimization, 4, 3-4, pp. 288-314, (2007)
  • [6] Mercier L., Hentenryck P.V., Edge finding for cumulative scheduling, Informs Journal on Computing, 20, 1, pp. 143-153, (2008)
  • [7] Tercinet F., Neron E., Lente C., Energetic reasoning and binpacking problem, for bounding a parallel machine scheduling problem, 4OR: A Quarterly Journal of Operations Research, 4, 4, pp. 297-317, (2006)
  • [8] Carlier J., Pinson E., Adjustments of heads and tails for the job shop problem, European Journal of Operational Research, 78, 2, pp. 146-161, (1994)
  • [9] Clautiaux F., Jouglet A., Carlier J., Moukrim A., A new constraint programming approach for the orthogonal packing problem, Computers and Operations Research, 35, 3, pp. 944-959, (2008)
  • [10] Brucker P., Jurisch B., Kramer A., The job shop problem and immediate selection, Annals of Operations Research, 50, 1, pp. 73-114, (1994)
12