Event-based MILP models for resource-constrained project scheduling problems

Oumar Koné 1 Christian Artigues 1 Pierre Lopez 1 Marcel Mongeau 2
1 LAAS-MOGISA
LAAS - Laboratoire d'analyse et d'architecture des systèmes
2 MAIA-OPTIM - ENAC Equipe MAIAA-OPTIM
MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
Abstract : In this paper we make a comparative study of several mixed integer linear programming (MILP) formulations for resource-constrained project scheduling problems (RCPSPs). First, we present three discrete and continuous time MILP formulations issued from the literature. Second, instead of relying on the traditional discretization of the time horizon, we propose two original MILP formulations for the RCPSP based on the concept of event : the Start/End formulation and the On/Off formulation. These formulations present the advantage of involving fewer variables than the formulations indexed by time. Because the variables of this type of formulations are not function of the time horizon, we have a better capacity to deal with instances of very large scheduling horizon. We also illustrate our contribution with a series of tests on various types of instances with the three MILP formulations issued from the literature together with our two new formulations, and we draw some conclusions on their use.
Document type :
Journal articles
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00361395
Contributor : Christian Artigues <>
Submitted on : Saturday, February 14, 2009 - 11:26:23 AM
Last modification on : Wednesday, November 20, 2019 - 1:23:18 AM
Long-term archiving on: Tuesday, June 8, 2010 - 10:27:06 PM

Files

Soumission-COR.pdf
Files produced by the author(s)

Identifiers

Citation

Oumar Koné, Christian Artigues, Pierre Lopez, Marcel Mongeau. Event-based MILP models for resource-constrained project scheduling problems. Computers and Operations Research, Elsevier, 2011, 38 (1), pp.3-13. ⟨10.1016/j.cor.2009.12.011⟩. ⟨hal-00361395⟩

Share

Metrics

Record views

604

Files downloads

2531