A note on "event-based MILP models for resource-constrained project scheduling problems"

Christian Artigues 1 Peter Brucker 2 Sigrid Knust 2 Oumar Koné 3 Pierre Lopez 1 Marcel Mongeau 4
1 LAAS-MOGISA
LAAS - Laboratoire d'analyse et d'architecture des systèmes
2 Department of Mathematics/Computer Science
3 Laboratoire de Mathématiques et Informatique, UFR-SFA
4 MAIA-OPTIM - ENAC Equipe MAIAA-OPTIM
MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
Abstract : Recently, new mixed integer linear programming formulations for the resource-constrained project scheduling problem were proposed by Kone et al. [3]. Unfortunately, the presentation of the first new model (called start/end-based formulation SEE) was not correct. More precisely, a set of necessary constraints representing the relative positioning of start and end events of activities was unintentionally omitted in the paper although it was present in the integer program used for the computational experiments. After presenting a counterexample showing the incorrectness, we provide a disaggregated and an aggregated variant of the set of necessary constraints, the disaggregated formulation yielding in theory a better linear programming relaxation. We present computational results showing that although the linear programming relaxations of both formulations yield equivalently poor lower bounds, the disaggregated formulation shows in average a better performance for integer solving of a well-known set of 30-activity instances.
Keywords : Resource-constrained project scheduling Event MILP formulation
Document type :
Journal articles
Complete list of metadatas
https://hal-enac.archives-ouvertes.fr/hal-00918016
Contributor : Laurence Porte <>
Submitted on : Thursday, March 8, 2018 - 11:01:52 AM
Last modification on : Friday, January 10, 2020 - 9:10:08 PM

Identifiers

Collections

MAIAA-OPTIM | MAIAA | CNRS | INSMI | TDS-MACS | INSA-TOULOUSE | OPTIM | ENAC | LAAS | INSA-GROUPE | UNIV-TLSE3 | UT1-CAPITOLE | UNIV-TLSE2 | RPAS

Citation

Christian Artigues, Peter Brucker, Sigrid Knust, Oumar Koné, Pierre Lopez, et al.. A note on "event-based MILP models for resource-constrained project scheduling problems". Computers and Operations Research, Elsevier, 2013, 40 (4), pp.1060-1063. ⟨10.1016/j.cor.2012.10.018⟩. ⟨hal-00918016⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

364