TY - GEN
T1 - A column generation based destructive lower bound for resource constrained project scheduling problems
AU - Van Den Akker, J. M.
AU - Diepen, G.
AU - Hoogeveen, J. A.
PY - 2007
Y1 - 2007
N2 - 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. [1] 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.
AB - 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. [1] 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.
KW - Column generation
KW - Cumulative constraint
KW - Generalized precedence constraints
KW - Linear programming
KW - Resource constrained project scheduling
UR - http://www.scopus.com/inward/record.url?scp=37149014590&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72397-4_27
DO - 10.1007/978-3-540-72397-4_27
M3 - Conference contribution
AN - SCOPUS:37149014590
SN - 354072396X
SN - 9783540723967
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 376
EP - 390
BT - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 4th International Conference, CPAIOR 2007, Proceedings
PB - Springer
T2 - 4th International Conference on Integration of Artificial Intelligence, Constraint Programming, and Operations Research Techniques for Combinatorial Optimization Problems, CPAIOR 2007
Y2 - 23 May 2007 through 26 May 2007
ER -