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

International audienceA 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