On the strength of time-indexed formulations for the resource-constrained project scheduling problem

Christian Artigues (1)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes

For non-preemptive scheduling, time-indexed zero-one linear programming formulations have been deeply analyzed. This note clarifies the current knowledge about the strength of these formulations and shows that some formulations that have been proposed " new " in the literature are in fact weaker or equivalent to those already known. Much of the arguments used follow from a PhD thesis by Sousa, which has been largely overlooked in the literature.

Mots clés: on/off variables; relaxation strength; resource-constrained project scheduling; the linear programming; time-indexed variables; non-singular trans-formations

Domaines: Recherche opérationnelle [math.OC]

Christian Artigues. On the strength of time-indexed formulations for the resource-constrained project scheduling problem. Operations Research Letters, 2017, 45 (2), pp.154-159. ⟨10.1016/j.orl.2017.02.001⟩. ⟨hal-01461447⟩