Lower Bounds for Resource Constrained Project Scheduling Problem

Emmanuel Neron (1) , Christian Artigues (2) , Philippe Baptiste (3) , Jacques Carlier (4) , Jean Damay , Sophie Demassey (5) , Philippe Laborie (6)

1 LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours
2 LAAS - Laboratoire d'analyse et d'architecture des systèmes
3 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
4 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes [Compiègne]
5 LINA - Laboratoire d'Informatique de Nantes Atlantique
6 ILOG SA [Gentilly]

We review the most recent lower bounds for the makespan minimization variant of the Resource Constrained Project Scheduling Problem. Lower bounds are either based on straight relaxations of the problems (e.g., single machine, parallel machine relaxations) or on constraint programming and/or linear programming formulations of the problem.

Domaines: Recherche opérationnelle [math.OC]

Emmanuel Neron, Christian Artigues, Philippe Baptiste, Jacques Carlier, Jean Damay, et al.. Lower Bounds for Resource Constrained Project Scheduling Problem. J. Weglarz and J. Józefowska. Perspectives in modern project scheduling, 92, Springer-Verlag, pp.167-204, 2006, International Series in Operations Research and Management Science, 978-0-387-33643-5. ⟨10.1007/978-0-387-33768-5_7⟩. ⟨hal-00482953⟩