Christian Artigues
email: christian.artigues@laas.fr

Pierre Lopez
email: pierre.lopez@laas.fr

Energetic reasoning for energy-constrained scheduling with a continuous resource

Keywords: scheduling with continuous resources, energy requirement, energetic reasoning satisfiability test, complexity

This paper addresses a scheduling problem with continuous resources and energy constraints. Given a set of non-preemptive activities, each activity requires a continuously-divisible resource whose instantaneous usage is limited in maximum and minimum, its processing satisfying a time window and a total energy (time × resource-usage) requirement. The goal consists in getting a schedule satisfying all the constraints. The problem, which we refer to as the Energy-Constrained Scheduling Problem with Continuous Resources (CECSP), is a generalization of the well-known cumulative scheduling problem for which the "energetic reasoning" or "left-shift/right-shift" necessary feasibility condition yielded a popular polynomially computable satisfiability test. The paper presents a generalization of the energetic reasoning for the CECSP, defining precisely the activity minimum consumptions and exhibiting a polynomial number of relevant time intervals on which it is sufficient to apply the satisfiability tests. A strongly polynomial energetic reasoning satisfiability test can be derived for the considered generalization, which also yields a short proof for the complexity of the original algorithm. Some limits of the approach, as well as an approximation framework for more general resource consumption functions, are also addressed.

Introduction

The control of energy consumption is now an important and rapidly growing matter of concern in most industrial sectors. This major preoccupation appears in many areas such as production [START_REF] Nolde | Electrical load tracking scheduling of a steel plant[END_REF], transportation [START_REF] Gaoua | Energy management for an electric vehicle based on combinatorial modeling[END_REF], smart buildings [START_REF] Jacomino | Robust energy planning in buildings with energy and comfort costs[END_REF], embedded systems [START_REF] Irani | Algorithmic problems in power management[END_REF], or technology studies [START_REF] Lizarralde | A decision support system to schedule design activities with interdependency and resource constraints[END_REF]. This issue becomes crucial in industrial organizations, in which the increased cost of energy, the new environmental constraints and the supplying difficulties have a big impact on the company activities and the production systems are affected in first place.

To address this problem we propose to focus on the propagation of energy constraints induced by resource power consumptions. This issue can be generally addressed by modeling the scheduling problem with continuous resources. The idea is to consider the energetic reasoning propagation algorithm [START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF][START_REF] Lopez | Consistency enforcing in scheduling: A general formulation based on energetic reasoning[END_REF][START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF] and to propose its generalization for considering continuous resource constraints where the resource-usage profile of an activity can take any shape bounded by a time window and minimum and maximum resource requirements, provided that a fixed amount of energy is brought to each activity. We refer to this problem as the Energy-Constrained Scheduling Problem with Continuous Resources (or Continuous Energy-Constrained Scheduling Problem, in short CECSP).

Energetic reasoning is part of constraint-based scheduling. Constraintbased scheduling can be defined as a topic that studies how to solve scheduling problems using constraint programming [START_REF] Baptiste | Constraint-based scheduling[END_REF][START_REF] Mercier | Strong polynomiality of resource constraint propagation[END_REF]. A popular global constraint useful for a large variety of scheduling problems is the cumulative constraint. Given a resource of limited capacity and a set of activities, each having a release date, a due date, a duration and a resource requirement, the cumulative constraint states that each activity is scheduled in its time window while, at any time, the cumulative resource requirement of the ongoing activities does not exceed the resource capacity. The decision problem embedded inside the cumulative constraint is called the cumulative scheduling problem (CuSP). Deciding whether a cumulative constraint can be satisfied amounts to deciding whether a CuSP has a solution and this is strongly NP-complete. Necessary feasibility conditions (or satisfiability tests) have been developed for constraint propagation. In particular, energetic reasoning yielded the powerful polynomially computable "left-shift/right-shift" satisfiability test and time-bound adjustments proposed in [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]. As a counterpart of its strength, the test has a relatively high complexity, which limited its use in branch-and-bound trees. However, recently, efficient implementa-tions and approximations were proposed to drastically reduce the computational requirements and considerably increasing the energetic reasoning appeal for future applications [START_REF] Berthold | An approximative criterion for the potential of energetic reasoning[END_REF].

The constraint propagation techniques developed so far in the literature cannot tackle directly the peculiarity of the CECSP. As the resource is continuously divisible, the activity requirement may change at any moment, and even under the assumption of continuous time, a fundamental question arises whether a strongly polynomial energetic reasoning-based satisfiability test can be defined for this constraint. This amounts to find a set of relevant intervals of polynomial cardinality, on which it is sufficient to apply energetic reasoning. This is the main objective of this paper.

The paper and its contributions are organized as follows: Section 2 provides a short background on the scheduling theory regarding energy constraints. Section 3 defines the CECSP, establishes the complexity of special cases and discusses the interest of the CECSP for solving more general energy-constrained problems, in particular scheduling problems with continuously-divisible resources and non-linear power processing rate functions. In Section 4, we consider energetic reasoning for the CECSP. We show that the energetic reasoning satisfiability test for the CSCSP can be computed in strongly polynomial time, as there actually exists a set of relevant intervals, the cardinality of which is bounded by a quadratic function of the number of activities. The interest of approximating general energy-constrained scheduling problems by a CECSP is illustrated through an example derived from the literature. In Section 5, we provide analytic expressions of all relevant intervals in function of the problem instance parameters. These findings additionally provide a shorter proof for correctness of the polynomial satisfiability test proposed for the CuSP in [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]. In Section 6, some limits of energetic reasoning for the CECSP are underlined. Concluding remarks and perspectives are drawn in Section 7. A theorem proof is developed in the appendix.

Background

The scheduling problem with a cumulative constraint, a.k.a. the Cumulative Scheduling Problem (CuSP) can be seen as a subproblem of the wellknown RCPSP (Resource-Constrained Project Scheduling Problem). In a CuSP, precedence constraints are relaxed and a single limited-capacity resource is considered at a time. Each activity is processed without interrup-tion and the execution is constrained by a time window and an instantaneous resource consumption. A few methods have been proposed to solve the CuSP as such, e.g., constraint programming [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF], column generation [START_REF] Van Den Akker | A column generation based destructive lower bound for resource constrained project scheduling problems[END_REF], and more recently, efficient SAT encodings through lazy clause generation [START_REF] Schutt | Explaining the cumulative propagator[END_REF]. More generally, the methods proposed in the vast literature on the RCPSP or its generalizations can be adapted to solve the CuSP, such as, again, recent SAT-based techniques [START_REF] Coelho | Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers[END_REF][START_REF] Horbach | A Boolean satisfiability approach to the resourceconstrained project scheduling problem[END_REF][START_REF] Schutt | Solving RCPSP/max by lazy clause generation[END_REF].

Considering more particularly constraint-based scheduling, necessary conditions have been developed for constraint propagation to cope with the NP-completeness of the problem. One of the most successful ones are the left-shift/right-shift conditions [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF], also known as energetic reasoning [START_REF] Lopez | Consistency enforcing in scheduling: A general formulation based on energetic reasoning[END_REF]. Energetic reasoning simultaneously encompasses considerations on time constraints and resource constraints yielding a (necessary) satisfiability test as well as time-bound adjustments. The central concept is the minimum energy consumption of an activity over a given time interval called the mandatory consumption. The satisfiability test consists in verifying that there does not exist any interval such that the sum of the mandatory consumptions over this interval exceeds the total available energy equal to the resource capacity times the length of the interval under consideration. In [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF], Baptiste et al. show that for the cumulative constraint, the satisfiability test can be limited to a quadratic number of intervals.

Despite its fundamental interest, the cumulative constraint suffers from limitations already identified in the literature. One of these limitations is that there are many practical applications where the duration and resource requirement of activities may vary over time in a discrete or continuous way. For example, in a scheduling problem with malleable tasks [START_REF] Kovalyov | Preemptable malleable task scheduling problem[END_REF], the activities must be processed on several processors at the same time and the processing speed depends on the number of assigned processors; the set of processors assigned to the same activity can change over time [START_REF] Barketau | Scheduling arbitrary number of malleable tasks on multiprocessor systems[END_REF]. The time/resource tradeoff problem addressed in [START_REF] Ranjbar | A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling[END_REF] also falls into this category. Several authors propose variants of the cumulative constraint and associated filtering algorithms to relax the constant or fixed resource requirement assumption. Baptiste et al. [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF] consider the fully elastic case where an activity has a constant energy requirement but its resource requirement at each (discrete) time is a variable whose domain varies from 0 to the resource capacity. The same authors also defined the partially elastic case without any limitation on the activity consumptions. Beldiceanu and Poder [START_REF] Beldiceanu | A continuous multi-resources cumulative constraint with positive-negative resource consumptionproduction[END_REF] define an activity as a sequence of continuous trapezoid sub-activities with variable duration and heights. Vilím [START_REF] Vilím | Max energy filtering algorithm for discrete cumulative resources[END_REF] considers activities where duration and resource re-quirement are defined by intervals. In the two latest studies, no fixed energy requirement is set for the activities. Finally, Fündeling and Trautmann have considered the RCPSP with work-content constraints and proposed priority rule-based heuristics to solve it [START_REF] Fündeling | A priority-rule method for project scheduling with work-content constraints[END_REF]. The work-content constraint is very close to the scheduling problem addressed in this paper. The main differences lie in the pure discrete feature of resource requirements contrary to our study where resource requirements take continuous values. Apart from the latter reference, the CECSP can be defined, to summarize, as a previously unconsidered generalization of the CuSP where the amount of resource required by an activity in progress at each time instant can be modulated between a minimum and a maximum value.

The CECSP is also linked to other energy-constrained scheduling problems with continuous resources [START_REF] Segal | Scheduling computer and manufacturing processes[END_REF][START_REF] Waligóra | Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan[END_REF][START_REF] Wȩglarz | Project scheduling with continuously-divisible, doubly constrained resources[END_REF]. In [START_REF] Segal | Scheduling computer and manufacturing processes[END_REF], the resources are distinguished according to their divisibility. Thus, a resource can be either discretely-divisible (discrete) or continuously-divisible (continuous). In our work, we will consider the case of continuous resources, which can be allocated at each time to each activity in an arbitrary and unknown in advance amount that must lie within a given interval. Practical applications dealing with real continuous resources are numerous, in particular all situations involving power limitations (electrical energy for example). Continuous resources may also serve as a relaxation of discrete resources, providing an aggregated reasoning and therefore getting rid of the combinatorial feature coming from the various alternative amounts to process an activity. The authors of [START_REF] Segal | Scheduling computer and manufacturing processes[END_REF] study several models for task processing according to the resource amount allotted. In particular, they study problems with one continuous, renewable resource in addition to: 1) parallel, identical processors and a continuously variable task processing speed; 2) a single processor and a continuously variable task processing time.

We consider in this paper an energetic consumption constraint (in short, energy constraint) associated with each activity processing, as defined in [START_REF] Artigues | The energy scheduling problem: Industrial case study and constraint propagation techniques[END_REF]. The energy is generically defined as the product of a time duration by a resource quantity. This gives an aggregate amount comparable to a surface, which can be expressed in units of [time × resource] (man-day, kW.h, ...). The concept of energy is of great interest, especially when it is more easy to measure accurately the activity energy while some parameters (activity duration, resource amount) remain incompletely specified. Compared to the energy requirement considered in problems with continuous resources, for which the energy brought to an activity is computed by integrating a power processing rate function on the scheduling horizon [START_REF] Segal | Scheduling computer and manufacturing processes[END_REF][START_REF] Waligóra | Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan[END_REF], the CECSP corresponds to the significant restriction to identity power processing rate functions. On the other hand, the scheduling problems considered in [START_REF] Segal | Scheduling computer and manufacturing processes[END_REF][START_REF] Waligóra | Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan[END_REF] do not consider minimum and maximum resource requirement constraints. We refer to [START_REF] Artigues | The energy scheduling problem: Industrial case study and constraint propagation techniques[END_REF] for a presentation of an industrial application of the discrete variant of the CECSP.

r i ≤ st i ≤ f t i ≤ d i (i ∈ A) (1)
b min i ≤ b i (t) ≤ b max i (i ∈ A ; t ∈ [st i , f t i ]) (2)
b i (t) = 0 (i ∈ A ; t ∈ T \ [st i , f t i ]) (3)
f t i st i b i (t)dt = W i (i ∈ A) (4) i∈A b i (t) ≤ R (t ∈ T ) (5)
Constraints (1) impose each activity being processed inside its time window. Constraints (2)-(3) state that the resource-usage profile of every activity must satisfy minimum and maximum resource requirements when the activity is in process, and equals zero otherwise. Constraints (4) express the energy requirement of each activity. Constraints (5) prevent the total amount of resource used by the activities simultaneously in process at every time t to exceed the resource capacity. We define the activity duration as

p i = f t i -st i .
Consider now the following remarkable particular case.

If b min i = b max i = b i then p i = W i /b i
is a constant and the solution is fully determined by activity start times st i . If, in addition, all b i and p i are integer we notice that we can restrict the search space to integer start times. With these additional assumptions, we obtain the CuSP. It follows from this remark that the CECSP is NP-complete.

CECSP with fixed starting/finishing times

If starting and finishing times are fixed, functions b i (t), i ∈ A, remain the only unknowns, and Theorem 1 shows that the CECSP is easy to solve. Theorem 1. For fixed (st i , f t i ) i∈A the feasibility of the CECSP ( 1)-( 5) can be checked polynomially in function of n.

Proof. Consider a feasible solution b i (t) of a CECSP and the increasing series (t q ) q=1..Q of distinct start time and end time values (Q ≤ n 2 ). For every t, we have i∈A b i (t) ≤ R. Integrating on interval [t q , t q+1 ] yields

t q+1 tq i∈A b i (t)dt ≤ (t q+1 -t q )R and consequently, i∈A t q+1 tq b i (t)dt t q+1 -tq ≤ R. Let b iq = t q+1 tq b i (t)dt.
It follows that b i (t) can be set to constant value b iq /(t q+1t q ) on interval [t q , . . . , t q+1 ] while keeping the solution feasible. In other words, there is no need to change the amount of resource allocated to an activity at time point that does not coincide with the start or the end of another activity. It follows that by replacing b i (t) by decision variable b iq /(t q+1t q ) for t ∈ {t q , . . . , t q+1 -1}, in (2)- [START_REF] Barketau | Scheduling arbitrary number of malleable tasks on multiprocessor systems[END_REF], where b iq is the (continuous) amount of energy allocated to i in interval q, yields a linear program with a number of variables and constraints polynomial in n. Equivalently, the problem amounts to a feasible flow problem in a network made of a unique source node, a unique sink node, a node per activity and a node per interval I q = [t q , t q+1 ]. An arc of capacity W i links the source to each node i. An arc of minimal capacity b min i and maximal capacity b max i links each node i to each node I q such that I q ⊆ [st i , f t i ]. Lastly, an arc of capacity [t q+1t q ] * B connects each node I q to the sink node. The CECSP with fixed start times has a solution if and only if there exists a flow of value i∈A W i in the network.

Note that the CECSP with fixed start and end times considered in this section is equivalent to a variant of the CECSP with zero minimum resource requirement (b min i = 0) and time-varying resource capacity. Indeed, when start and end times are fixed, the time window of each activity can be reduced to [r ′ i = st i , d ′ i = f t i ] and each activity must receive its minimum requirement during its entire time window. It follows that we can define an equivalent time-varying resource capacity function B ′ (t) where i , for each activity i ∈ A. Conversely, from any CECSP with zero minimum resource requirement and time varying resource capacity, we easily obtain an equivalent CECSP with fixed start and end times by defining fixed activities corresponding to capacity changes. It follows from Theorem 1 that the CECSP with zero minimum resource requirement and time varying resource capacity is polynomial. In particular the case where the capacity is constant (which can be defined as the continuous fully elastic problem by reference to the discrete one presented in [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]) is also polynomial.

B ′ (t) = R -i∈A|t∈[r i ,d i ] b min i for each t ∈ T and define a new demand W ′ i = W i - b min i (t 2 -t 1 )

Interest for other energy-constrained problems

This paper is mainly devoted to a necessary feasibility condition for the CECSP. Hence, such a condition holds for any generalization of this problem. For example, if T is discrete, b min i = 0, b max i = R, we obtain the (polynomially solvable) fully elastic constraint [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]. If b i (t) is constrained to take only discrete values, the necessary condition will also hold (see for example the work-content problem considered in [START_REF] Fündeling | A priority-rule method for project scheduling with work-content constraints[END_REF]).

Consider now a continuous resource model where the power processing rate of an activity is no more equal to its instantaneous resource requirement (see for example the models presented in [START_REF] Segal | Scheduling computer and manufacturing processes[END_REF][START_REF] Waligóra | Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan[END_REF]). The latter modeling amounts to replacing the energy constraints (4) by the following, more general, constraints:

f t i st i f i [b i (t)]dt = W i (i ∈ A) (6)
where f i (b) is a continuous non-decreasing power processing rate function.

When the power processing rate functions are linear, i.e.,

f i (b) = a i b+c i , with a i , b i ∈ R, a i > 0, c i ≥ 0,
we provide an approximation of this general problem by a CECSP. In this case, constraints (6) can be written

a i f t i st i b i (t)dt + c i f t i st i dt = W i (i ∈ A) which yields f t i st i b i (t)dt = W i a i - c i a i (f t i -st i ) (i ∈ A) (7)
We must first underline that the CECSP or its generalization, which are decision problems, can be transformed into equivalent minimization problems, introducing objective function

min i∈A W i (8)
and replacing, for the CECSP, constraints (4) by constraints

f t i st i b i (t)dt ≥ W i (i ∈ A) (9)
and, for the generalized CECSP, constraints (6) by constraints

f t i st i f i [b i (t)]dt ≥ W i (i ∈ A) (10)
while keeping other constraints. As time is continuous, it is never advantageous to provide more energy to the activity than the required one, and there is no constraint that would make the problems feasible only by allocating to an activity more than W i . So both decision problems will be feasible as soon as their minimization counterpart are feasible and vice-versa.

Whenever f i (b) ≤ b, approximating f i [b i (t)
] by b i (t) gives precisely the energy constraint (4) and a valid relaxation. We can propose another relaxation scheme of the generalized problem with linear power processing rate functions by defining an upper bound p max i of f t ist i . The maximal duration is obtained by scheduling with the minimal resource requirement b min i . From equation [START_REF] Berthold | An approximative criterion for the potential of energetic reasoning[END_REF], it yields:

b min i p max i = W i a i - c i a i p max i hence p max i = W i a i b min i + c i
The following constraint must hold

f t i st i b i (t)dt ≥ W i a i - c i a i p max i therefore, using the expression of p max i , f t i st i b i (t)dt ≥ W i b min i a i b min i + c i By defining W ′ i = W i b min i a i b min i + c i and considering constraints f t i st i b i (t)dt ≥ W ′ i , i ∈ A,
we obtain a CECSP, which is a valid relaxation of the general problem with linear power processing rate functions.

Illustrative example

As an illustration, we propose an extension of an example problem presented in [START_REF] Waligóra | Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan[END_REF].

Consider a problem with n = 4, R = 1 and power processing rate functions of activities of the form

f i (b) = b 1/q i with q i ∈ {1, 2}, i = 1, 2, . . . , n.
The energy requirements of the activities, and their values of q i are defined by the vectors: W = [START_REF] Waligóra | Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan[END_REF]36,64,47] As some power processing rate functions are non-linear (activities 2 and 4), we address here a generalized CECSP. Note that for 0

≤ b ≤ 1, √ b ≥ b, so we cannot approximate f i (b i (t)) by b i (t) for f 2 (b) = f 4 (b) = √ b.
However, the square root function can standardly be approximated from above by its tangent line f ′ at any point. For activity 2, we are thus looking for We have now a linear function

f ′ 2 (b) = a ′ 2 b + c ′ 2 .
f ′ 2 (b) = b 2 √ 0.4 + √ 0.4 2
as the power processing rate function for activity 2 and we can approximate its energy constraint with the method described in the previous section. We compute

p max 2 = W 2 a ′ 2 b min 2 + c ′ 2 = 36 0.3 2. √ 0.4 + √ 0.4 2 = 720 7 √ 0.4 ≈ 65.0526
Then we have

W ′ 2 = W 2 a ′ 2 - c ′ 2 a ′ 2 p max 2 = 216 7 √ 0.4 ≈ 19.5158
Similarly for activity 4 we can approximate

f 4 (b) = √ b by its tangent f ′ 4 (b) = a ′ 4 b + c ′ 4 at point (0.3, √ 0.3), which yields a ′ 4 = 1 2 √ 0.3 and c ′ 4 = √ 0.3 2 .
In the same way we compute a lower bound for the energy requirement at power processing rate

f ′ 4 (b) = b 2 √ 0.3 + √ 0.3 2 by computing p max 4 = 188 √ 0.3 ≈ 102.9718
Then we have

W ′ 4 = 188 5 √ 0.3 ≈ 20.5943
With same data but replacing W 2 by W ′ 2 and W 4 by W ′ 4 we now have a CECSP, which is a relaxation of the original problem with non-linear power processing rate, in the sense that if the CECSP is infeasible then the original problem is also infeasible.

Energetic reasoning-The"left-shift/right-shift" necessary condition

Energetic reasoning has been successful implemented in the cumulative global constraint. Our objective is here to extend its principle to the case of continuous resources for the CECSP. The cornerstone of all this reasoning is based on an accurate evaluation of the real available energy for the activity execution over a continuous time interval, according to the other activity consumptions. Thanks to this evaluation, various energetic balances can put in evidence an energy lack over certain intervals. This can produce forbidden activity locations, yielding sequencing conditions between activities, time window narrowing coming from time-bound adjustments, or "holes" in the associated underlying interval. In this paper we concentrate on the necessary condition yielding a satisfiability test.

A necessary feasibility condition

When starting and finishing times must be determined, as our problem generalizes CuSP, deciding whether the scheduling problem with continuous resources and energy constraint has a solution is NP-complete. It is consequently of interest to establish necessary feasibility conditions, i.e., an incomplete satisfiability test that ensures the constraint cannot be satisfied if the test returns false while we can not conclude on the constraint satisfiability if the test returns true. For the CuSP, the energetic reasoning triggers a successful incomplete satisfiability test used in commercial solvers [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF][START_REF] Lopez | Consistency enforcing in scheduling: A general formulation based on energetic reasoning[END_REF].

A first elementary satisfiability test consists in checking whether the activity data are consistent. This can be expressed as: 1)-( 5) has no solution.

Proposition 1. If ∃i ∈ A such that b max i (d i -r i ) < W i , the CECSP (
Proof. This is straightforward as W i /b max i is the shortest possible duration of activity i.

Consider now the minimum energy consumption of an activity i over an interval [t 1 , t 2 ], ignoring other activities. This value, called the mandatory consumption over the interval, is denoted by w(i, t 1 , t 2 ). It is defined by

w(i, t 1 , t 2 ) = min t 2 t 1 b i (t)dt subject to (1)-(4)
Proposition 2 (Energy reasoning satisfiability test). The CECSP ( 1)-( 5) has no solution if

∃(t 1 , t 2 ) ∈ T 2 , t 2 > t 1 , SL(t 1 , t 2 ) < 0 ( 11
)
where

SL(t 1 , t 2 ) = R(t 2 -t 1 )-i∈A w(i, t 1 , t 2 ) is the slack of interval [t 1 , t 2 ],
i.e., the available energy given all the minimum energy consumptions of all activities.

Proof. Suppose that the condition is satisfied. By definition w(i, t

t 1 b i (t)dt ≥ i∈A w(i, t 1 , t 2 ) > R(t 2 -t 1 ).
We obtain a contradiction with the integration of resource constraint (5

) on interval [t 1 , t 2 ].
Proposition 2 corresponds to the well-known energetic reasoning on nonpreemptive problems, involving the "left-shift/right-shift" necessary condition transposed to our problem. In [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF], it was shown that Test [START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF] can be restricted for the CuSP to a set of dominant intervals of polynomial cardinality. A polynomial consistency-checking algorithm exists if a polynomial number of intervals [t 1 , t 2 ] are sufficient to perform the satisfiability test. The first objective is then to find a minimal set of intervals on which to apply this energetic consistency test for the CECSP. In [START_REF] Artigues | The energy scheduling problem: Industrial case study and constraint propagation techniques[END_REF], the necessary condition has been presented for the discrete time case but the question on the existence of a polynomial number of relevant intervals was left open.

Mandatory consumption

Let us first have a closer look at the mandatory consumption of an activity i ∈ A, for all intervals [t 1 , t 2 ] with t 2 > t 1 . We will show that w(i, t 1 , t 2 ) is a two-dimensional piecewise-linear continuous function decreasing in t 1 and increasing in t 2 . Each function w(i, t 1 , t 2 ), i ∈ A is defined in the polygon P = {t 1 ≥ r min , t 2t 1 ≥ 0, t 2 ≤ d max }, with r min = min i∈A r i and

d max = max i∈A d i .
Constraints [START_REF] Barketau | Scheduling arbitrary number of malleable tasks on multiprocessor systems[END_REF] are the only constraints that link variables b i (t) for different i. Actually, as these constraints have been removed in the definition of the mandatory consumption, they can be computed separately (and easily) for each activity. Given the interval [t 1 , t 2 ], it can easily be observed that the minimum consumption of an activity i inside the interval always corresponds to a configuration where the activity is either left shifted (in which case the activity starts at r i and is scheduled at its maximum resource requirement b max i between r i and t 1 ) or right shifted (in which case the activity ends at d i and is scheduled at its maximum resource requirement b max i between t 2 and d i ), or both. Depending on the relative position of t 1 , t 2 , r i , and d i , the possible configurations for minimum energy consumption of an activity i are displayed in Figure 1.

We summarize the expression of the minimum consumption for each of the possible configurations (a)-(i) as follows:

(a) If t 1 ≤ t 2 ≤ d i -W i /b max i , w(i, t 1 , t 2 ) = 0. (b) If t 1 ≤ r i ≤ t 2 ≤ d i and t 2 ≥ d i -W i /b max i , w(i, t 1 , t 2 ) = W i -(d i -t 2 )b max i (c) If r i + W i /b max i ≤ t 1 ≤ t 2 , w(i, t 1 , t 2 ) = 0 (d) If r i ≤ t 1 ≤ d i ≤ t 2 , and t 1 ≤ r i + W i /b max i , w(i, t 1 , t 2 ) = W i -(t 1 -r i )b max i (e) If t 1 ≤ r i ≤ d i ≤ t 2 , w(i, t 1 , t 2 ) = W i 13 (g) (h) (i)
000 000 000 000 000 000 000 111 111 111 111

111 111 111

(a) (b) (d) t 1 r i t 2 d i b min i r i t 2 t 1 b max i b min i b max i r i d i t 2 t 1 b min i b max i t 1 r i t 2 d i b max i b min i t 2 d i r i t 1 b min i b max i r i t 1 t 2 d i b min i b max i r i t 1 b min i b max i r i t 1 t 2 d i d i t 2 b min i b max i d i b min i t 2 t 1 b max i Figure 1: Mandatory consumption configurations (f-i) If r i ≤ t 1 ≤ r i + W i /b max i and d i -W i /b max i ≤ t 2 ≤ d i ,
w(i, t 1 , t 2 ) = min   b min i (t 2 -t 1 ), W i -(d i -t 2 )b max i , W i -(t 1 -r i )b max i 
 , which can be expressed by the following conditions:

(f) If W i -(d i -t 2 )b max i ≤ b min i (t 2 -t 1 ) and W i -(d i -t 2 )b max i ≤ W i -(t 1 -r i )b max i w(i, t 1 , t 2 ) = W i -(d i -t 2 )b max i (g) If W i -(t 1 -r i )b max i ≤ b min i (t 2 -t 1 ) and W i -(t 1 -r i )b max i ≤ W i -(d i -t 2 )b max i w(i, t 1 , t 2 ) = W i -(t 1 -r i )b max i (h) If b min i (t 2 -t 1 ) ≤ W i -(d i -t 2 )b max i and b min i (t 2 -t 1 ) ≤ W i -(t 1 -r i )b max i , w(i, t 1 , t 2 ) = b min i (t 2 -t 1 ) (i) If the activity cannot be scheduled at its minimum requirement inside [t 1 , t 2 ], i.e., W i -b max i (t 1 -r i + d i -t 2 ) ≥ b min i (t 2 -t 1 ), w(i, t 1 , t 2 ) = W i -b max i (t 1 -r i + d i -t 2 )
The conditions associated with the different expressions are linear inequalities that define a planar subdivision of polygon P into convex polygons inside which the minimum consumption is linear. Hence, the individual activity minimum consumption w(i, t 1 , t 2 ) is a bivariate continuous piecewise linear function. This remark allows us to establish the theorem stated in Section 4.4.

Back to the example

We illustrate the energetic reasoning satisfiability test on the scheduling example presented in Section 3.4. We use the modified energy requirements W ′ to work on the CECSP instead on its generalization. Consider two particular intervals It follows that the energetic reasoning satisfiability test on [t 3 , t 4 ] allows the infeasibility of the CECSP to be proven and, consequently, that of its generalization.

I 1 = [t 1 , t 2 ] = [0,

Strong polynomiality of the satisfiability test

Theorem 2 below shows that, despite the continuous nature of the CECSP yielding a potentially infinite interval space, the energetic reasoning satisfiability test can be checked in strongly polynomial time.

Theorem 2. The energetic reasoning satisfiability test [START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF] needs only be applied on a quadratic number of intervals [t 1 , t 2 ].

Proof. The slack function, as a difference of a linear function R(t 2t 1 ) and a sum of piecewise linear functions, is itself a two-dimensional piecewise linear function. The minimum of the slack function is attained on an extreme point of one of the convex polygons on which it is linear. The break line segments of the slack function are the same as the ones of the sum of the individual minimum consumption functions. Hence, from a geometrical point of view, an extreme point of the slack function is the intersection of two line segments, each being the break line segment of an individual activity minimum consumption function. It follows directly that to compute the minimum slack, it suffices to enumerate all such intersection points, and, for each of them to perform the satisfiability test [START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF]. For each activity, there is a constant number of line segments, which gives O(n 2 ) number of intersection points.

For each intersection point, the energetic reasoning satisfiability test [START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF] needs O(n) time to compute the sum of minimum consumptions, which gives a total time complexity of O(n 3 ) for a naive enumeration algorithm. Note that for the cumulative case (i.e., b min i = b max i ), this property has already been established by Baptiste, Le Pape, & Nuijten (see Proposition 6 in [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]). We will come back to these results in the next section, as Theorem 2 yields a shorter proof.

For more computational efficiency, it is now necessary to further characterize the break line segments of the individual activity minimum consumption functions, as we can observe that for a given activity some regions (a)-(i) can be skipped.

In-depth characterization of break line segments

In this section, we provide the different possible configurations for the mandatory consumption of an activity. This amounts to define analytically the break line segments defining the polygons of the bivariate piecewise linear function based on activity parameters.

To perform this analysis we first make the following observations for the minimum consumption function.

First, we observe that the function value is independent of t 1 if t 1 ≤ r i and independent of t 2 if t 2 ≥ d i . This is formally stated by: Lemma 1.

w(i, t 1 , t 2 ) = w(i, r i , t 2 ), ∀(t 1 , t 2 ∈ P ), t 1 ≤ r i w(i, t 1 , t 2 ) = w(i, t 1 , d i ), ∀(t 1 , t 2 ∈ P ), t 2 ≥ d i . Proof. For any interval [t 1 , t 2 ] such that t 1 ≤ r i , t 2 t 1 b i (t)dt = r i t 1 b i (t)dt + t 2 r i b i (t)dt = t 2 r i b i (t)dt
since b i (t) = 0 for all t ≤ r i by Constraints (1) and ( 3). The definition of the minimal energy consumption yields the first equality. The second equality is obtained by a symmetric argument.

Second we observe that the minimal energy consumption of an activity

i ∈ A inside an interval [t 1 , t 2 ] is symmetric with respect to axis t 1 + t 2 = r i + d i . Lemma 2. For all t 1 ≥ 0, t 2 ≥ t 1 , w(i, t 1 , t 2 ) = w(i, d i + r i -t 2 , d i + r i -t 1 ).

Proof. First from Lemma 1, we may restrict to an interval

[t 1 , t 2 ] ⊆ [r i , d i ]. Let t ′ 1 = d i + r i -t 2 and t ′ 2 = d i + r i -t 1
. By symmetry we have also

[t ′ 1 , t ′ 2 ] ⊆ [r i , d i ].
It follows that for both intervals the mandatory consumption is either zero or computed according to one of the configurations (f)-(i) displayed in Figure 1 and described in Section 4.2. In the case where w(i, t 1 , t 2 ) = 0, we have either

t 2 ≤ d i -W i /b max i =⇒ t ′ 1 ≥ r i + W i /b max i or t 1 ≥ r i + W i /b max i =⇒ t ′ 2 ≤ d i -W i /b max i .
In each case, the implication gives w(i, t ′ 1 , t ′ 2 ) = 0. In the case where w(i, t 1 , t 2 ) > 0, we have [

r i + W i /b max i , d i -W i /b max i ] ⊂ [t 1 , t 2 ], which also implies that [r i + W i /b max i , d i -W i /b max i ] ⊂ [t ′ 1 , t ′ 2 ]
. This means that one of the configurations among {(f),(g),(h),(i)} holds for each interval. If the conditions for configuration (f) hold for [t 1 , t 2 ], conditions for configuration (g) hold for [t ′ 1 , t ′ 2 ] and the mandatory consumptions are equal because

W i -(d i -t 2 )b max i = W i -(t ′ 1 -r i )b max i . Symmetrically, if configuration (g) holds for [t 1 , t 2 ], con- figuration (f) holds for [t ′ 1 , t ′ 2 ]
and the mandatory consumptions are equal. Finally, configurations (h) and (i) are both preserved by the transformation and we have t

2 -t 1 = t ′ 2 -t ′ 1 .
It follows that mandatory consumptions are equal in both cases.

From Lemmas (1) and (2), it is sufficient to establish the expression of w(i, t 1 , t 2 ) on the polygon (triangle) delimited by inequalities t 1 ≥ r i , t 1 + t 2 ≤ r i + d i and t 2t 1 ≥ 0. The triangle is defined by the intersection points A = (r i , d i ), B = ((r i + d i )/2, (r i + d i )/2) and C = (r i , r i ).

Inside this polygon, the unique point for which the minimum required energy is maximal is point A = (r i , d i ) and w(i, r i , d i ) = W i (see configuration (e) in Figure 1).

For ease of notation, we define activity earliest end time e min i and latest start time s max i as follows:

e min i = r i + W i /b max i , ∀i ∈ A s max i = d i -W i /b max i , ∀i ∈ A Theorem 3

. The minimum mandatory consumption function of an activity is one of the six piecewise linear bivariate functions described through the planar subdivisions displayed in Figures 2-5 and precisely described hereafter. The break line segments to consider are those of the polygons on which the function is linear.

The detailed proof of this theorem is given in appendix. We present below the seven possible configurations for the expression of the mandatory consumption of an activity, depending on the problem parameters. The seven possible piecewise linear functions are represented in Figures 2345. As each function w(i, t 1 , t 2 ) is a two-dimensional piecewise linear function, we could represent it on the 3-D space. For the sake of readability, we project it on the (t 1 , t 2 ) plane and we represent the different linear parts by shaded zones.

Case b min

i = 0
For this case, which can be stated as the continuous fully elastic case (by reference to [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]), the break line segments of the mandatory consumption functions are given in Figure 2. Inside each zone, the linear expression of the mandatory consumption (one of the expressions (a-i) defined in Section 4.2) is recalled when it is not equal to zero. Basically there are two zones, one (e) in which the mandatory consumption is maximal, as interval [t 1 , t 2 ] covers the activity time windows, and one (i) where the mandatory consumption is obtained by scheduling as many as possible amount of activity outside of the interval. The break line segments to consider are (r min , d i )A, A(r i , d max ), (r min , s max , i.e., the standard cumulative case, as considered in [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF], we obtain two possible configurations of the break line segments depending on the relative positioning of the earliest end time e min i and the latest end time s max i (Figure 3). For both configurations, as in the previously considered case, the mandatory is maximal when

[r i , d i ] ⊆ [t 1 , t 2 ],
i.e., in zone (e).

Consider the case where e min i ≤ s max i (see Figure 3(a)). As the earliest end time does not exceed the latest start time there are only two zones where the mandatory consumption is non-zero and non-maximal. The zone where the activity is left-shifted is subdivided into two sub-zones: area (d) defined by r i ≤ t 1 ≤ d i ≤ t 2 , and area (g) above line t 1 + t 2 = r i + d i . The zones where the activity is right-shifted (b,f) can be defined by symmetry. The break line segments to consider are then given by (r i , d max )A, (r min , d i )A, (r min , s max i )F , F (e min i , d max ), AF , where F = (e min i , s max i ).

Consider now the case where 3(b)). As, for any point t ∈ [s max i , e min i ], the activity is necessarily in progress, in addition to the zones mentioned in the previous case, there is a zone (h) where the mandatory consumption uses the full interval capacity. The break line segments to consider are given by (r i , d max )A, (r min , d i )A, (r min , s max i , e min i ). Now we come back to the results obtained by Baptiste et al [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF] on the set of remarkable intervals, i.e., the set of intervals on which it is sufficient to apply the energetic reasoning satisfiability test. By observing the break line segments of the minimum consumption piecewise linear function of all activities, as displayed in Figure 3, we may define S 1 as the set of all horizontal break line segments, S 2 as the set of all vertical break line segments, and S 3 as the set of all (A, H) segments. Intersection points have to be searched between segment pairs in S 1 × S 2 , S 1 × S 3 and S 2 × S 3 only. This gives an alternative proof of Proposition 6 in [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]. We still have to consider the more general case of the energy scheduling problem, where there is a non-zero minimal requirement strictly lower than the maximal requirement. In this case we have four configurations for the break line segments that are displayed in Figures 4 and5.

r i + W i /b i ≥ d i -W i /b i (see Figure
t 1 t 2 r min r i r i d max e min i s max i d max r min d i s max i e min i A B C C' D D' F G G' (e) (d) (g) (b) (f ) (a) e min i ≤ s max i (Wi = 10) t 1 t 2 r min r min r i r i e min i s max i d max d max d i s max i e min i A B H F G G' C C' D D' (e) (d) (g) (b) (f ) (h) (b) e min i ≥ s max i (Wi = 20)
We first consider the case where b min i (d ir i ) ≥ W i , i.e., the activity can be scheduled at the minimum requirement during all its processing. Hence we have a minimum energy consumption inside the interval lower than or equal to (t 2t 1 )b min i . This leads, for the break line segments, to the two configurations displayed in Figure 4

H = ( r i (b max i -b min i ) -d i b min i + W i b max i -2b min i , d i (b max i -b min i ) -r i b min i -W i b max i -2b min i ) H is the intersection point of the lines delimiting configuration (h) b min i (t 2 - t 1 ) = W i -(d i -t 2 )b max i and b min i (t 2 -t 1 ) = W i -(t 1 -r i )b max i .
We now consider the complementary case where b min i (d ir i ) ≤ W i , i.e., the activity cannot be scheduled at its minimal requirement during all its processing. This leads, for the break line segments, to the two configurations displayed in Figure 5. This is the only case where more than b min i (t 2 -t 1 ) can be required by the activity inside the interval, which corresponds to linear expression (i). The zone where (i) holds is delimited by lines

t 1 = r i , t 2 = d i and W i -b max i (t 1 -r i + d i -t 2 ) = b min i (t 2 -t 1 )
, which intersect at points A, I = (r i ,

d i b max i -r i b min i -W i b max i -b min i ) and I ′ = ( r i b max i -d i b min i +W i b max i -b min i , d i ). According
W i -b max i (t 1 -r i +d i -t 2 ) = b min i (t 2 -t 1 ) and delimited by lines b min i (t 2 -t 1 ) = W i -(d i -t 2 )b max i and b min i (t 2 -t 1 ) = W i -(t 1 -r i )b max i , on which configuration (h) is observed is either closed at point H or at points G and G ′ .
The break line segments to consider for configuration 5(a) are given by (r i , d max )A, (r min , d i )A, (r min , s max i )F , F (e min i , d max ), AI, AI ′ , II ′ , IH, I ′ H, and HF .

The break line segments to consider for configuration 5(b) are given by (r i , d max )A, (r min , d i )A, (r min , s max i )G, G ′ (e min i , d max ), AI, AI ′ , II ′ , IG and

I ′ G ′ . t 1 t 2 r min r i r i d max e min i s max i d max r min d i s max i e min i A B C C' D D' F G G' (e) (d) (g)
(b) (f ) (a) Case e min i ≤ s max i (b min i = 2, Wi = 10) t 1 t 2 r min r min r i r i e min i s max i d max d max d i s max i e min i A B H F G G' C C' D D' (e) (d) (g) (b) (f )
(h) (b) Case e min i ≥ s max i (b min i = 4, Wi = 20) Figure 4: Case (d i -r i )b min i ≥ W i (r i = 3, d i = 10, b max i = 5) t 1 t 2 r min r i r i d max e min i s max i d max r min d i s max i e min i A B C C' D D' F G G' I I' H (e) (d) (g) (b) (f ) (i) (h) (a) Case e min i ≤ s max i (b min i = 1, Wi = 10) t 1 t 2 r min r min r i r i e min i s max i d max d max d i s max i e min i A B F G G' C C' D D' I I' J (e) (d) (g) (b) (f ) (h) (i)
(b) Case e min i ≥ s max i (b min i = 2, Wi = 20) Figure 5: Case (d i -r i )b min i ≤ W i (r i = 3, d i = 10, b max i = 5) 22
Returning to the fixed starting and finishing times case, we underline here a weakness of energetic reasoning for the CECSP case compared to the CuSP case. Consider an instance of CuSP, which is a CECSP where b

min i = b max i = b i , ∀i ∈ A,
where all starting times and finishing times are fixed. It can be easily shown that applying energetic reasoning on all possible intervals yields a necessary and sufficient feasibility condition. It suffices to consider all intervals [t q , t q+1 ] defined in the proof of Theorem 1. For the CuSP, fixing the starting and finishing times precisely gives, for any activity i ∈ A, a minimal consumption inside any interval [t q , t q+1 ] equal to b i (t q+1t q ) if [t q , t q+1 ] ⊂ [st i , f t i ] or to zero otherwise. It follows that the energetic reasoning allows making all resource capacity checks for each interval [t q , t q+1 ], which is sufficient to assert feasibility (see argument for Theorem 1).

For the CECSP case, fixing start and end times of activities yields a polynomial problem, as stated by Theorem 1. Unfortunately, the energetic reasoning necessary condition may in some cases fail to prove infeasibility. Taking the intersection points of all segment pairs for which the interval length is not zero, we obtain six relevant intervals, displayed as square dots.

Consider the following example with

n = 3, R = 3, r = st = {0, 4, 0}, d = f t = {2, 6, 6}, W = {4, 4, 10}, b min = {2, 2, 1}, b max = {2,
The energetic reasoning satisfiability test can be limited to these intervals. Figure 7 illustrates the slack computation by considering all six intervals. For each interval, only activities having a non-zero minimum consumption are displayed in gray for Activity 1, vertical lines for Activity 2 and horizontal lines for Activity 3. The dotted line represent the resource capacity. It can be seen that no infeasibility is detected since, for each interval the sum of minimum consumption never exceeds the interval capacity.

Consider now the LP defined in the proof of Theorem 1, we consider three time slots corresponding to the intervals between the start and end times of the activities. Note that we have four relevant time points t 1 = 0, t 2 = 2, t 3 = 4, t 4 = 6 and that b iq corresponds to the amount of resource allocated to activity i in time slot [t q , t q+1 ]. Writing the LP, we obtain

b 11 = 4, b 12 = 0, b 13 = 0 (12) b 20 = 4, b 22 = 0, b 23 = 4 (13) 2 ≤ b 3q ≤ 4 q = 1, 2, 3 (14)
b 31 + 4 ≤ 6 (15)
b 32 ≤ 6 ( 16)

b 33 + 4 ≤ 6 (17)
b 31 + b 32 + b 33 = 10 (18)
As constraints [START_REF] Irani | Algorithmic problems in power management[END_REF][START_REF] Lizarralde | A decision support system to schedule design activities with interdependency and resource constraints[END_REF] bound b 31 and b 33 by 2, and constraint ( 14) bounds b 32 by 4, energy constraint (18) cannot obviously be satisfied. The infeasibility of the LP (or equivalently of the flow problem) proves that of the CECSP. In this paper, we have considered a scheduling problem with continuous resources and energy constraint, an extension of the cumulative scheduling problem to represent energy requirements of activities and modulation. We have proposed a strongly polynomial extension of the standard energetic reasoning scheme for this problem. One consists in designing a clever method for enumerating the extreme points of the slack polytopes to obtain an efficient energetic reasoning algorithm. Another direction consists in designing a complete tree-search method embedding energetic reasoning, linear programming and/or network flow algorithms to obtain a feasible solution or to prove that no solution exists. A complementary question is to know whether it is possible to design a single algorithm that embed the power of energetic reasoning and that of linear programming/network flow. Besides satisfiability tests, energetic reasoning for the CuSP includes time windows adjustments, that can also be extended to the CECSP. Further research includes generation of valid inequalities from energetic reasoning and their integration in a mixed integer linear program. Last, for a better application to actual scheduling problems under energy constraints, it would be necessary to make a direct extension of energetic reasoning to general, non-linear power processing rate functions. We now assume that there is a non-zero lower bound for the activity requirement. We first characterize the subregions on which the mandatory consumption is minimal and the ones on which it is maximal, which yields two configurations displayed in Figure 8 and obtained as follows.

We reason only on triangle (A, B, C) as the expression on the rest of the polygon P can be obtained by applying the properties established in Lemmas 1 and 2. Note that the minimum required energy is 0 in the triangle (A, B, C) as this value reached by setting t 2 = t 1 and the maximum required energy is W i is attained in A (and only in A) as already observed.

Looking at the geometry of the subregions in triangle (A, B, C), the line F belongs to the triangle (A, B, C) if and only if F is located on segment AB. For this, the four following inequalities must be satisfied:

t 2 = d i -W i /b max i (below
e min i ≥ r i e min i ≤ (r i + d i )/2 s max i ≤ d i s max i ≥ (r i + d i )/2
The first and third inequalities are always satisfied. The second and fourth inequalities are equivalent to inequality

r i + W i /b max i ≤ d i -W i /b max i (19)
G is located on segment BC if the reverse inequality holds.

Focusing now on line t 1 = r i + W i /b max i (to the right of which the minimum required energy is 0 as stated by condition (c)), a similar reasoning shows that it intersects line t 1 + t 2 = r i + d i also at point F and line

t 2 = t 1 at point G ′ = (r i +W i /b max i , r i +W i /b max i
). Point G ′ , as the symmetric point of G with respect to axis t 1 + t 2 = r i + d i , belongs to BC if [START_REF] Mercier | Strong polynomiality of resource constraint propagation[END_REF] holds.

The regions on which the energy is maximal (W i ) are displayed in horizontal lines and the region on which the energy is minimal (0) are displayed , i.e., the standard cumulative case, as considered in [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]. We obtain as follows two possible configurations of the break line segments (Figure 3). 8(a)). Any point (t 1 , t 2 ) located in triangle (A, D, F ) verifies t 2 ≥ d i -W i /b i . Since we have also t 1 + t 2 ≤ r i + d i , we have by subtracting the inequalities, t 1 ≤ r i + W i /b i , which means that globally:

Consider the case where

r i + W i /b i ≤ d i -W i /b i (see Figure
r i ≤ t 1 ≤ r i + W i /b i ≤ d i -W i /b i ≤ t 2 ≤ d i As b min i = b max i = b i ,
left shifting the activity before t 1 yields a consump-tion inside the interval of (r i + W i /b it 1 )b i = W i -(t 1r i )b i . Right shifting the activity after t 2 yields a consumption inside the interval of (t 2 -

d i + W i /b i )b i = W i -(d i -t 2 )b i . As d i -t 2 ≥ t 1 -r i , the mini- mal consumption inside (A, D, F ) is equal to W i -(d i -t 2 )b i .
The geometry of the subregion is displayed in Figure 3(a). By symmetry, the minimal consumption inside triangle (A, D ′ , F ) is equal to W i -(t 1r i ))b i . To sum up, in the polygon hatched with horizontal lines the energy is maximal (W i ), in the gray polygons the energy is minimal (0), in the polygon hatched with descending diagonal lines the energy is equal to W i -(d it 2 )b i , while in the polygon hatched with ascending diagonal lines the energy is equal to W i -(t 1r i ))b i . There are five break line segments to consider for slack computation.

Consider now the case where

r i + W i /b i ≥ d i -W i /b i (see Figure 8(b)). We consider two subcases. If t 1 ≥ d i -W i /b i , as we have also t 1 + t 2 ≤ r i + d i , this yields t 2 ≤ r i + W i /b i . Because r i + W i /b i ≥ d i -W i /b i and b min i = b max i = b i , the minimum consumption is equal to b i (t 2 -t 1 ). Oppositely, if t 1 ≤ d i -W i /b i , right shifting i after t 2 while considering that b min i = b max i = b i yields a consumption of (t 2 -d i +W i /b i )b i = W i -(d i -t 2 )b i .
With similar argument as Figure 8(a) case, it can be shown that this value is larger than the one obtained by left shifting the activity before t 1 . Clearly for this case, we obtain two subregions of (A, B, G, D) on which the minimum consumption is linear, separated by line t 1 = d i -W i /b i . This lines starts at G and crosses segment AB at point H = (d i -W i /b i , r i + W i /b i ). This is illustrated in Figure 3(b). By symmetry, we also obtain two subregions of (A, D ′ , G ′ , H) on which the energy consumption is linear. Overall, we have six convex polygons defining the piecewise linear function. In the polygon hatched with horizontal lines, the consumption is maximal (W i ). On the gray polygons, the consumption is minimal (0). In the polygon hatched with descending diagonal lines, the energy consumption is equal to W i -(d i -t 2 )b i . In the polygon hatched with ascending diagonal lines, the energy is equal to W i -(t 1r i )b i . In the crosshatched polygon, it is equal to (t 2t 1 )b i . There are seven break line segments to consider for slack computation. In this case we have four configurations for the break line segments that are displayed in Figures 4 and5. We obtain these configurations as follows.

We have identified two subcases depending on the relative ordering of the earliest end time r i + W i /b max i and the latest start time

d i -W i /b max i . If r i + W i /b max i ≤ d i -W i /b max i
we have to establish the expression of the minimum consumption inside triangle (A, D, F ) (see Figure 8(a)). If, oppositely,

r i + W i /b max i ≥ d i -W i /b max i
, we have to establish the expression of the minimum consumption inside polygon (A, B, G, D) (see Figure 8(b)). In both cases, we have

r i ≤ t 1 ≤ r i + W i /b max i and d i -W i /b max i ≤ t 2 ≤ d i . Before t 1 , a maximal consumption of (t 1 -r i )b max i can be scheduled. After t 2 , a maximal consumption of (d i -t 2 )b max i can be scheduled. As t 1 + t 2 ≤ r i + d i ⇔ t 1 -r i ≤ d i -t 2 ,
W i -(d i -t 2 )b max i -(t 1 -r i )b max i ≥ (t 2 -t 1 )b min i , which can be written t 2 -t 1 ≥ b max i (d i -r i )-W i b max i -b min i . In both polygons (A, D, F ) and (A, B, G, D) point A = (r i , d i ) maximizes t 2 -t 1 .
For A to satisfy the inequality, we must have

d i -r i ≥ b max i (d i -r i )-W i b max i -b min i =⇒ b min i (d i -r i ) ≤ W i 1.
We first consider the case where b min i (d ir i ) ≥ W i , i.e., the activity can be scheduled at the minimum requirement during all its processing. Hence, both in (A, D, F ) and in (A, B, G, D), we have a minimum energy consumption lower than or equal to (t 2t 1 )b min i . This leads, for the break line segments, to the two configurations displayed in To have the minimum energy precisely equal to (t 2t 1 )b min i , we must have

W i -(d i -t 2 )b max i ≥ (t 2 -t 1 )b min i , which can be written b min i t 1 + (b max i -b min i )t 2 ≥ d i b max i -W i .
We can check under which conditions the inequality is verified for each of the extreme points of (A, D, F ) and (A, B, G, D).

(a) Let us focus first on (A, D, F ) for the case

r i + W i /b max i ≤ d i - W i /b max i . For A = (r i , d i ), we get (d i -r i )b min i ≤ W i , which is never satisfied under our set of hypothesis. For D = (r i , d i - W i /b max i
), we have a smaller l.h.s. and, consequently the inequality is never satisfied. For F

= (r i + W i /b max i , d i -W i /b max i ), we obtain r i + W i /b max i ≥ d i -W i /b max i
, which is in contradiction with our hypothesis. Consequently, in (A, D, F ) the minimum energy consumption is equal to W

i -(d i -t 2 )b max i . (b) Consider now (A, B, G, D) for the case r i + W i /b max i ≥ d i - W i /b max i . For G = (d i -W i /b max i , d i -W i /b max i ), the condi- tion is always satisfied as G actually belongs to line b min i t 1 + (b max i -b min i )t 2 = d i b max i -W i . For B = ( r i +d i 2 , r i +d i 2 ), the condi- tion becomes r i + W i /b max i ≥ d i -W i /b max i
, which is also always satisfied in the considered case. It follows that, from a geometrical point of view, line b min

i t 1 + (b max i -b min i )t 2 = d i b max i -W i crosses the polygon at G and intersects segment AB at point H = ( r i (b max i -b min i )-d i b min i +W i b max i -2b min i , d i (b max i -b min i )-r i b min i -W i b max i -2b min i ).
The two subcases are illustrated in Figure 4 hold. We observe the additional case where the minimum required energy is equal to b min i (t 2t 1 ), inside the crosshatched polygon (H, G, G ′ ). This gives seven break line segments to consider.

2. We now consider the complementary case where b min i (d ir i ) ≤ W i , i.e., the activity cannot be scheduled at its minimal requirement during all its processing. This leads, for the break line segments, to the two configurations displayed in Figure 5. .

All points located in triangle (A, I, J) consequently verify w(i, t 1 , t 2 ) = W ib max i (t 1r i )b max i (d it 2 ) while all points located in polygons (I, J, D, F ) or (I, J, B, G, D) have a minimal consumption not larger than b min i (t 2t 1 ). We want to characterize the subregions of these polygons for which the minimal consumption is precisely equal to b min i (t 2t 1 ). For each such point (t 1 , t 2 ), we must have The two configurations corresponding to the case (d ir i )b min i ≤ W i , are illustrated in Figure 5. Using the symmetry of the minimum consumption, we obtain the displayed polygons in which the minimum consumption is linear. The polygon hatched with horizontal lines corresponds to w(i, t 1 , t 2 ) = W i , the white polygon corresponds to the case where w(i, t 1 , t 2 ) = W ib max i (t 1r i )b max i (d it 2 ), 35 the crosshatched polygon corresponds to the case where w(i, t 1 , t 2 ) = b min i (t 2t 1 ), the polygons hatched with descending diagonal lines correspond to the case where w(i, t 1 , t 2 ) = W i -(d i -t 2 )b max i , the polygons hatched with ascending diagonal lines correspond to the case where w(i, t 1 , t 2 ) = W i -(t 1r i )b max i .

W i -(d i -t 2 )b max i ≥ (t 2 -
For the Figure 5(a) configuration, one has ten break line segments to consider whereas for the Figure 5(b) configuration, we obtain nine break line segments. Note that the continuous fully elastic case (Figure 2) is particular case of both the cases of Figure 5 where the areas hatched by diagonal lines or crosshatched do not appear.

  and new min and max requirements b ′ min i

  and q = [1, 2, 1, 2]. In addition to the original example, we define b min = [0, 0.3, 1, 0.2] and b max = [0.5, 0.5, 1, 0.4] as well as r = [0, 16, 0, 50] and d = [58, 106, 90, 139].

  The slope of the tangent line at the middle point of interval [0.3, 0.5] is equal to a ′ 2

3 ≈= 216 7 √ 0 . 4 . 5 √ 0 . 3 - 7 √ 0 . 4 + 48 + 188 5 √ 0 . 3 -

 3704503704503 139] and I 2 = [t 3 , t 4 ] =[START_REF] Jacomino | Robust energy planning in buildings with energy and comfort costs[END_REF] 106].Since I 1 covers the entire scheduling horizon, i∈A w(i, t 1 , t 2 ) = i∈A W ′ i 129.1101 ≤ 139. For this interval the slack is positive and nothing can be concluded on the problem feasibility. Let now compute the mandatory consumption of each activity over interval I 2 = [16, 106] . Task 1 is in case (d) of Figure 1 (r 1 ≤ t 3 ≤ d 1 ≤ t 4 ) and w(1, t 3 , t 4 ) = 25 -16 × 0.5 = 17. Task 2 has precisely [t 3 , t 4 ] as time window, so w(1, t 3 , t 4 ) = W ′ 2 Task 3 is also in case (d) of Figure 1 (r 3 ≤ t 3 ≤ d 3 ≤ t 4 ) and w(3, t 3 , t 4 ) = 64 -16 × 1 = 48. Last, activity 4 is in configuration (b) of Figure 1 (t 3 ≤ r 4 ≤ t 4 ≤ d 4 ) and w(4, t 3 , t 4 ) = 188 33×0.4 ≈ 7.3944. By summing up all w(i, t 3 , t 4 ) we obtain a total energy requirement of 17 + 216 33 × 0.4 ≈ 91.9101, which is strictly larger than the interval capacity (90).

i

  )D, DD ′ and D ′ (e min i , d max ) where A = (r i , d i ), D = (r i , s max i ) and D ′ = (e min i , d i ). From Figure2onwards, a point indicated with a square stands for an intersection (remarkable interval) of two break lines of the individual mandatory consumption function of activity i. A circled point is the intersection of a break line of the mandatory consumption function of activity i with a boundary break line t 2 = d max and t 1 = r min . Other displayed intersection points are here irrelevant, as they are located on lines that are not both break lines of the mandatory function.

Figure 2 := 5 ,

 25 Figure 2: Case b min i = 0 (r i = 3, d i = 10, b max i

  G ′ (e min i , d max ), AH, GH and G ′ H, where H = (s max i , e min i ), G = (s max i , , s max i ) and G ′ = (e min

Figure 3 := 5 (r i = 3 , d i = 10 ) 5 . 3

 3531053 Figure 3: Two configurations for case b min i = b max i

  depending on the relative ordering of the earliest end time e min i and the latest start time s max i . The displayed zones, as well as the break line segments, are the same as for the b min i = b max i case, except that point H has now the expression

  to the relative ordering of the earliest end time e min i and the latest start time s max i , the region below line

  2, 2}. Note that fixing the start times amounts to setting constraint r = st and d = f t.

Figure 6

 6 displays the polygons on which the slack function is linear. Activities 1 and 2 are such that b min i > 0 and b min i = b max i . They both correspond to the degenerate case of Figure 3(b) where s max i = r i and e min i = d i . The break line segments of their mandatory consumption are displayed in dotted and dashed lines, respectively. Activity 3 is such that 0 < b min i < b max i , (d ir i )b min i ≤ W i and e min i ≥ s max i . It corresponds to the case of Figure 5(b) (also a degenerate case where s max i = r i and e min i = d i ). The break line segments of its mandatory consumption are displayed in thick.

Figure 6 :

 6 Figure 6: Slack polygons and relevant intervals

Figure 7 :

 7 Figure 7: Slack computation on the six relevant intervals

  and argmax j∈A d j = d max . Hence for slack computation one has to consider the five break line segments involving at least one square point. Case b min i > 0

  which the required energy is 0 as expressed in configuration (a)) crosses line t 1 = r i at the already defined point D = (r i , s max i ) (which belongs to segment AC), linet 1 + t 2 = r i + d i at point F = (e min i , s max i) and line t 2 = t 1 at point G = (s max i

Figure 8 :

 8 Figure 8: Minimal and maximal consumption regions (r i = 3, d i = 10, b max i

Fig- ure 4 .

 4 Note that the two configurations for activities with b min i = b max i displayed in Figure 3 are particular cases of configurations presented here.

  for an activity with r i = 3, d i = 10 and b max i = 5. Figure 4(a) corresponds to the case where W i = 10 and b min i = 2. We see that in this configuration, for which bmin i (d ir i ) ≥ W i and r i +W i /b max i ≤ d i -W i /b max ihold, the minimum required energy is maximal in the polygon hatched with horizontal lines, equal to W i -(d it 2 )b max i in the polygon hatched with descending diagonal lines and equal to W i -(t 1r i )b max i in the polygon hatched with ascending diagonal lines. Elsewhere, the minimum required energy is equal to 0. There are five break line segments to consider for minimum slack computation.

Figure 4 (

 4 Figure 4(b) illustrates the case where W i = 20 and b min i = 4, which belongs to the configuration where b min i (d i -r i ) ≥ W i and r i +W i /b max i ≥ d i -W i /b max i

  We know that in both polygons (A, D, F ) and(A, B, G, D) point A = (r i , d i ) verifies inequality t 2t 1 ≥ b max i (d i -r i )-W i b max i -b min i . We also see that for point D = (r i , d i -W i /b max i ), t 2t 1 ≤ b max i (d i -r i )-W i b max i t 1 + t 2 = r i + d i at point J = 2b max i r ib min i (r i + d i ) + W i 2(b max i b min i ) , 2b max i d ib min i (d i + r i ) -W i 2(b max i b min i )

  t 1 )b min i , which can be written b mini t 1 + (b max i b min i )t 2 ≥ d i b max i -W i .We can check under which conditions the inequality is verified for each of the extreme points of (I, J, D, F ) and (I, J, B, G, D). I is precisely the intersection point of segment AD and line b mini t 1 + (b max i b min i )t 2 = d i b max i -W i .As this line has a negative slope of -b min i /(b max i b min i ), it defines a non-empty region in the considered polygons. We can easily notice that the line crosses linet 2 = d i -W i /b max i at point G.This leads us to consider two subcases.(a) For polygon (A, D, F ), which corresponds to the case wherer i + W i /b max i ≤ d i -W i /b max i , G is after F on line t 2 = d i -W i /b max i . Hence line b min i t 1 + (b max i b min i )t 2 = d i b max i -W i crosses segmentAF at point H = ( considered for a previous configuration. To summarize there are three regions to consider inside polygon (A, D, F ): triangle (A, I, J) on which the minimum energy consumption is equal toW ib max i (t 1r i )b max i (d it 2 ), triangle (I, J, H) inside which the minimum energy consumption is equal to b min i (t 2t 1 ) and polygon (I, H, D, F ) inside which the minimum energy consumption is equal toW i -(d it 2 )b max i .(b) For polygon (A, B, G, D), which corresponds to the case wherer i + W i /b max i ≤ d i -W i /b max i, we directly obtain a decomposition in three subregions: triangle (A, I, J) inside which the minimum energy consumption is equal to Wib max i (t 1r i )b max i (d it 2 ),polygon (I, J, B, G) inside which the minimum energy consumption is equal to b min i (t 2t 1 ), and triangle (I, D, G) inside which the minimum energy consumption is equal to W i -(d it 2 )b max i .

  , d i ∈ R, for each activity i ∈ A. Let T = [min i∈A r i , max i∈A d i ] denote the continuous time horizon. Solving the CECSP consists in determining, for each activity i, a start time st i , a finishing time f t i , and the resource quantity allocated b i (t) for all t ∈ T such that the following constraints are satisfied:

	3 Problem statement and properties
	3.1 Definition of the CECSP
	Formally, the problem takes as input a set of n activities A = {1, 2, . . . , n}. Such activities have to be executed using a continuous resource of maximal
	availability R (capacity). Every activity i has an energy requirement W i ,
	a resource requirement between b min i	and b max i	, and it has to be realized
	within a time window [r i , d i ]. No restriction is assumed on parameter values,
	i.e., R ∈ R and W i , b min i , b max i	, r i

  the minimal consumption inside [t 1 , t 2 ] can always be attained by right-shifting the activity in its time window. Hence there remains W i -(d it 2 )b max i units to schedule before t 2 . Can we have a minimal energy larger than (t 2 -t 1 )b min i inside [t 1 , t 2 ] ? This can only happen if

Acknowledgments

This research was part of OCrE project supported by CNRS/INSIS (Centre National de la Recherche Scientifique/Institut des Sciences de l'Ingénierie et des Systèmes). The authors are indebted to David Rivreau for enlightening discussions. A preliminary version of this work was presented as a "Late breaking abstract" at CPAIOR 2011, Berlin, and we thank an anonymous referee for pointing out to us the interest of studying the fixed start time case. Finally, the authors warmly thank Margaux Nattaf for her help on improving the revised version of the paper.

Appendix -Proof of theorem 3

Proof. We enumerate all possible configurations concerning the parameters of an activity, starting with the minimum requirement b min i .

Case b min i = 0

We now focus on the case where b min i = 0 (corresponding to the continuous variant of fully elastic problem [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]). The break line segments of the minimum energy consumption piecewise linear function of such an activity are displayed in Figure 2, and obtained as follows.

In this case, for any interval [t 1 , t 2 ] strictly included in [r i , d i ], the minimum required energy consumption in [t 1 , t 2 ] is attained by scheduling as much energy as possible before t 1 and after t 2 . Hence, the energy is clearly equal to max(0,

In the triangle defined by inequalities t 1 ≥ r i , t 1 +t 2 ≤ r i +d i and t 2 ≥ t 1 , the points for which the minimum required energy is non-zero are precisely such that t

), respectively. From this analysis, it follows that we have inside the triangle two regions separated by the segment joining this two points on which the energy is linear.

By applying the symmetry property, we obtain the full description of the minimum energy consumption in the case b min i = 0 as depicted in Figure 2. Points indicated with a prime (i.e., D ′ and C ′ ) have been obtained by symmetry. The function is linear inside three polygons (that can de decomposed in seven convex polygons). In the polygon hatched with horizontal lines, we have w(i, t 1 , t 2 ) = W i . In the polygon(s) hatched with vertical lines, we have

In the gray polygon(s), we have w(i, t 1 , t 2 ) = 0. Nodes indicated with a square are the intersection points of break line segments. Circle points correspond to intersections of a break line of w(i, t 1 , t 2 ) with boundary t 1 = d max and t 2 = r min , which are break line segments of the mandatory consumption of activities argmin j∈A r j = r min