Polyhedral results and valid inequalities for the Continuous Energy-Constrained Scheduling Problem

Margaux Nattaf (1) , Christian Artigues (1) , Pierre Lopez (1) , Tamás Kis (2)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
2 MTA SZTAKI - Computer and Automation Research Institute [Budapest]

This works deals with event-based mixed integer linear programming formulations for resource-constrained scheduling problems. In this context, two strongly NP-hard problems are considered: the Resource-Constrained Project Scheduling Problem (RCPSP) and the Continuous Energy-Constrained Scheduling Problem (CECSP). Several mixed integer programs have been developed so far in order to solve them [1, 2, 4]. For the RCPSP, time-indexed formulations have a much better LP relaxation than the event-based ones. However, time-indexed formulations show their weakness for instances with large planning horizons and heterogeneous task durations, while eventbased models proved to be more efficient to provide exact solutions for these types of instances [1]. For the CECSP, event-based formulations are the only ones that can provide optimal solutions. Indeed, an instance of the CECSP may have only solutions containing non-integer values and such a solution can not be reached by a time-indexed formulation [2]. In this work, we are interested in the strengthening of those event-based models.

Domaines: Recherche opérationnelle [math.OC]

Margaux Nattaf, Christian Artigues, Pierre Lopez, Tamás Kis. Polyhedral results and valid inequalities for the Continuous Energy-Constrained Scheduling Problem. 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MSPSP 2017), Jun 2017, Seeon Abbey, Germany. ⟨hal-02136583⟩