Optimal Constraint Programming Approach to the Open-Shop Problem

被引：19
|
作者：
Malapert, Arnaud [1 ,2 ]
Cambazard, Hadrien [3 ]
Gueret, Christelle [4 ]
Jussien, Narendra [1 ]
Langevin, Andre [2 ]
Rousseau, Louis-Martin [2 ]
机构：
[1] Ecole Mines Nantes, LINA, CNRS, UMR 6241, F-44307 Nantes, France
[2] Ecole Polytech Montreal, CIRRELT, Montreal, PQ H3C 3A7, Canada
[3] Natl Univ Ireland Univ Coll Cork, Dept Comp Sci, Cork Constraint Computat Ctr, Cork, Ireland
[4] Ecole Mines Nantes, IRCCyN, CNRS, UMR 6597, F-44307 Nantes, France
来源：
INFORMS JOURNAL ON COMPUTING | 2012年 / 24卷 / 02期
关键词：
production scheduling; open shop; computers; computer science; artificial intelligence; constraint programming; randomization and restart; ALGORITHMS; BACKTRACKING; OPTIMIZATION; SEARCH;
D O I：
10.1287/ijoc.1100.0446
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow us to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and it shows better results on a wide range of benchmark instances.
引用
收藏
页码：228 / 244
页数：17
相关论文
共 50 条
  • [1] An optimal constraint programming approach to the open-shop problem
    Malapert, Arnaud
    Guéret, Christelle
    Cambazard, Hadrien
    Jussien, Narendra
    Langevin, André
    Rousseau, Louis-Martin
    ICAPS 2013 - Proceedings of the 23rd International Conference on Automated Planning and Scheduling, 2013, : 478 - 479
  • [2] AN ALGORITHM FOR THE OPEN-SHOP PROBLEM
    FIALA, T
    MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (01) : 100 - 109
  • [3] THE CYCLIC COMPACT OPEN-SHOP SCHEDULING PROBLEM
    MAHADEV, NVR
    SOLOT, P
    DEWERRA, D
    DISCRETE MATHEMATICS, 1993, 111 (1-3) : 361 - 366
  • [4] Production Programming Model in Open-Shop Systems using Genetic Algorithms Approach
    Blanco-Canon, A.
    Sierra, C. A.
    2016 IEEE LATIN AMERICAN CONFERENCE ON COMPUTATIONAL INTELLIGENCE (LA-CCI), 2016,
  • [5] A branch & bound algorithm for the open-shop problem
    Brucker, P
    Hurink, J
    Jurisch, B
    Wostmann, B
    DISCRETE APPLIED MATHEMATICS, 1997, 76 (1-3) : 43 - 59
  • [6] A new lower bound for the open-shop problem
    Guéret, C
    Prins, C
    ANNALS OF OPERATIONS RESEARCH, 1999, 92 (0) : 165 - 183
  • [7] Hybrid Genetic Algorithms for the Open-Shop Scheduling Problem
    Kokosinski, Zbigniew
    Studzienny, Lukasz
    INTERNATIONAL JOURNAL OF COMPUTER SCIENCE AND NETWORK SECURITY, 2007, 7 (09): : 136 - 145
  • [8] The routing open-shop problem on a network: Complexity and approximation
    Averbakh, Igor
    Berman, Oded
    Chernykh, Ilya
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 173 (02) : 531 - 539
  • [9] A position-based propagator for the open-shop problem
    Monette, Jean-Noel
    Deville, Yves
    Dupont, Pierre
    INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING FOR COMBINATORIAL OPTIMIZATION PROBLEMS, PROCEEDINGS, 2007, 4510 : 186 - +
  • [10] Competitive genetic algorithms for the open-shop scheduling problem
    Christian Prins
    Mathematical Methods of Operations Research, 2000, 52 : 389 - 411
12345