A column generation based destructive lower bound for resource constrained project scheduling problems

van den Akker, J.M.;Diepen, G.;Hoogeveen, J.A.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • van den Akker, J.M.
    Author
  • Diepen, G.
    Author
  • Hoogeveen, J.A.
    Author
Abstract
In this paper we present a destructive lower bound for a number of resource constrained project scheduling (RCPS) problems, which is based on column generation. We first look at the problem with only one resource. We show how to adapt the procedure by Van den Akker et al. for the problem of minimizing maximum lateness on a set of identical, parallel machines such that it can be used to solve these RCPS problems. We then consider a number of variants of the RCPS problem with one or more resources and show how these can be solved by our approach. Because of the close relation between RCPS and the cumulative constraint in constraint programming, our method can be used as an efficient filtering algorithm for the cumulative constraint as well.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

van den Akker, J. M., Diepen, G., & Hoogeveen, J. A. (2007). A column generation based destructive lower bound for resource constrained project scheduling problems. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 376-390). Springer-verlag. https://hdl.handle.net/2078.5/222046