Enhanced Energetic Reasoning-Based lower bounds for the Resource constrained project scheduling problem

Abstract : We present new and effective lower bounds for the resource constrained project scheduling problem. This problem is widely known to be notoriously difficult to solve due to the lack of lower bounds that are both tight and fast. In this paper, we propose several new lower bounds that are based on the concept of energetic reasoning. A major contribution of this work is to investigate several enhanced new feasibility tests that prove useful for deriving new lower bounds that consistently outperform the classical energetic reasoning-based lower bound. In particular, we present the results of a comprehensive computational study, carried out on 1560 benchmark instances, that provides strong evidence that a deceptively simple dual feasible function-based lower bound is highly competitive with a state-of-the-art lower bound while being extremely fast. Furthermore, we found that an effective shaving procedure enables to derive an excellent lower bound that often outperforms the best bound from the literature while being significantly simpler.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2012, 39 (5), pp.1187-1194. 〈10.1016/j.cor.2011.05.022〉
Liste complète des métadonnées

https://hal-univ-tours.archives-ouvertes.fr/hal-01003842
Contributeur : Vincent T'Kindt <>
Soumis le : mardi 10 juin 2014 - 17:30:12
Dernière modification le : mardi 9 octobre 2018 - 11:46:06

Identifiants

Collections

Citation

Mohamed Haouari, Anis Kooli, Emmanuel Neron. Enhanced Energetic Reasoning-Based lower bounds for the Resource constrained project scheduling problem. Computers and Operations Research, Elsevier, 2012, 39 (5), pp.1187-1194. 〈10.1016/j.cor.2011.05.022〉. 〈hal-01003842〉

Partager

Métriques

Consultations de la notice

68