A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling

Please always quote using this URN: urn:nbn:de:0297-zib-11180
  • We propose a hybrid approach for solving the resource-constrained project scheduling problem which is an extremely hard to solve combinatorial optimization problem of practical relevance. Jobs have to be scheduled on (renewable) resources subject to precedence constraints such that the resource capacities are never exceeded and the latest completion time of all jobs is minimized. The problem has challenged researchers from different communities, such as integer programming (IP), constraint programming (CP), and satisfiability testing (SAT). Still, there are instances with 60 jobs which have not been solved for many years. The currently best known approach, lazyFD, is a hybrid between CP and SAT techniques. In this paper we propose an even stronger hybridization by integrating all the three areas, IP, CP, and SAT, into a single branch-and-bound scheme. We show that lower bounds from the linear relaxation of the IP formulation and conflict analysis are key ingredients for pruning the search tree. First computational experiments show very promising results. For five instances of the well-known PSPLIB we report an improvement of lower bounds. Our implementation is generic, thus it can be potentially applied to similar problems as well.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Author:Timo Berthold, Stefan Heinz, Marco E. Lübbecke, Rolf H. Möhring, Jens Schulz
Document Type:ZIB-Report
Tag:conflict analysis ; constraint integer programming ; cumulative constraint ; resource-constrained project Scheduling; scheduling
MSC-Classification:65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
Contributing Corporation:TU Berlin
Date of first Publication:2010/03/15
Series (Serial Number):ZIB-Report (10-03)
Published in:App. in: CPAIOR 2010, Proceedings, Andrea Lodi et al. (eds.) Springer 2010, LNCS 6140, pp. 313-317

$Rev: 13581 $