Flow and energy based satisfiability tests for the Continuous Energy-Constrained Scheduling Problem with concave piecewise linear functions

Margaux Nattaf (1) , Christian Artigues (1) , Pierre Lopez (1)

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

A set of tasks consuming a continuous, cumulative and renewable resource with limited capacity, has to be scheduled. The consumption profile of the task is a decision variable of the problem that can vary continuously over time and must lie within a minimum and a maximum value once the task is started. The task is completed as soon as the integration over its time window of a non-decreasing and continuous efficiency function of the consumption profile has reached a predefined amount of energy. The goal is to find a feasible schedule, which is an NP-complete problem. For the case where functions are concave and piecewise linear, we present two satisfiability tests. The first one is the adaptation to concave functions of the variant of the energetic reasoning based satisfiability test previously proposed in [11] for linear functions. The second test is a flow-based linear program. Finally, the complementarity of the tests is assessed via their integration in a hybrid branch-and-bound.

Mots clés: continuous scheduling; continuous resources; concave piece-wise linear functions; energy constraints; energetic reasoning

Domaines: Recherche opérationnelle [math.OC]

Margaux Nattaf, Christian Artigues, Pierre Lopez. Flow and energy based satisfiability tests for the Continuous Energy-Constrained Scheduling Problem with concave piecewise linear functions. Doctoral Program, 21th International Conference on Principles and Practice of Constraint Programming , Aug 2015, Cork, Ireland. pp 70-81. ⟨hal-01288033⟩