Vladik Kreinovich

Amélie Levray

Karim Tabia

Qualitative conditioning in an interval-based possibilistic setting (Preprint) Salem Benferhat 1

Keywords: Interval-based possibilistic logic, conditioning, possibility theory

Possibility theory and possibilistic logic are well-known uncertainty frameworks particularly suited for representing and reasoning with uncertain, partial and qualitative information. Belief update plays a crucial role when updating beliefs and uncertain pieces of information in the light of new evidence. This paper deals with conditioning uncertain information in a qualitative interval-valued possibilistic setting. The first important contribution concerns a set of three natural postulates for conditioning intervalbased possibility distributions. We show that any interval-based conditioning satisfying these three postulates is necessarily based on the set of compatible standard possibility distributions. The second contribution consists in a proposal of efficient procedures to compute the lower and upper endpoints of the conditional interval-based possibility distribution while the third important contribution provides a syntactic counterpart of conditioning interval-based possibility distributions in case where these latter are compactly encoded in the form of possibilistic knowledge bases.

Introduction

Many problems and applications need efficient formalisms for encoding and reasoning with uncertain, partial information or knowledge. Possibility theory and possibilistic logic [START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF][START_REF] Dubois | Generalized possibilistic logic: Foundations and applications to qualitative reasoning[END_REF][START_REF] Lang | Possibilistic logic: complexity and algorithms[END_REF][START_REF] Dubois | Generalized possibilistic logic[END_REF][START_REF] Dellunde | Extending possibilistic logic over gödel logic[END_REF] are uncertainty frameworks particularly suited for representing and reasoning with uncertain, incomplete, prioritized and qualitative information. In the literature, many extensions have been proposed for possibilistic logic to deal for instance with imprecise certainty degrees [START_REF] Benferhat | Interval-based possibilistic logic[END_REF][START_REF] Benferhat | Compatible-based conditioning in interval-based possibilistic logic[END_REF], symbolic certainty weights [START_REF] Benferhat | Encoding formulas with partially constrained weights in a possibilistic-like manysorted propositional logic[END_REF][START_REF] Cayrol | Symbolic Possibilistic Logic: Completeness and Inference Methods (regular paper)[END_REF], multi-agent beliefs [START_REF] Belhadi | Multiple agent possibilistic logic[END_REF], temporal and uncertain information [START_REF] Dubois | Timed possibilistic logic[END_REF], uncertain conditional events [START_REF] Coletti | Finitely maxitive t-conditional possibility theory: Coherence and extension[END_REF][START_REF] Coletti | Finitely maxitive conditional possibilities, bayesian-like inference, disintegrability and conglome Fuzzy Sets and[END_REF][START_REF] Coletti | Coherent t-conditional possibility envelopes and nonmonotonic reasoning[END_REF], generalized possibilistic logic [START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF][START_REF] Dubois | Generalized possibilistic logic[END_REF][START_REF] Dubois | Stable models in generalized possibilistic logic[END_REF], justified beliefs [START_REF] Fan | A logic for reasoning about justified uncertain beliefs[END_REF], etc.

Interval-based uncertainty representations extend the underlying uncertainty settings in order to encode uncertainty by means of intervals of possible degrees instead of single values. Such extensions allow more flexible representations especially to deal with poor information, imprecise or ill-known beliefs, confidence intervals and multi-source information [START_REF] Nguyen | How to fully represent expert information about imprecise properties in a computer system: random sets, fuzzy sets, and beyond: an overview[END_REF][START_REF] Dubois | Possibility theory and statistical reasoning[END_REF]. Such representations are very widely used in some applications such as sensitivity analysis. In this paper, we are interested in interval-based possibilistic logic [START_REF] Benferhat | Interval-based possibilistic logic[END_REF] which extends the standard possibilistic logic setting to allow intervals of possible degrees instead of single values attached to the formulas of the knowledge base.

Conditioning is an important task for updating the current uncertain information when a new sure piece of information is received. A conditioning operator is designed to satisfy some desirable properties such as giving priority to the new information and ensuring minimal change while transforming an initial distribution into a conditional one. Conditioning in standard (single-valued) possibility theory has been addressed in many works [START_REF]Conditional possibilities independence and non interaction[END_REF][START_REF] De Campos | Possibilistic independence[END_REF]21,[START_REF] Fonck | A comparative study of possibilistic conditional independence and lack of interaction[END_REF][START_REF] Dubois | Bayesian conditioning in possibility theory[END_REF][START_REF] Baets | Conditioning in possibility theory with strict order norms[END_REF][START_REF] De Cooman | Integration and conditioning in numerical possibility theory[END_REF][START_REF] Hsia | Possibilistic conditioning and propagation[END_REF][START_REF] Benferhat | Syntactic Computation of Hybrid Possibilistic Conditioning under Un in: IJCAI[END_REF]. There are two major definitions of a possibility theory: min-based (or qualitative) possibility theory and product-based (or quantitative) possibility theory. At the semantic level, these two theories share the same definitions, including the concepts of possibility distributions, necessity measures, possibility measures and the definition of normalization conditions. However, they differ in the way they define possibilistic conditioning. Indeed, in possibility theory, there are two main definitions of possibilistic conditioning. The first one is called min-based conditioning [START_REF]Conditional possibilities independence and non interaction[END_REF][START_REF] Dubois | The logical view of conditioning and its application to possibility and evidence theories[END_REF] (or qualitative-based conditioning) which is appropriate in situations where only the ordering between events is important. In this case, the unit interval [0, 1] is viewed as an ordinal scale where only the minimum and the maximum operations are used for propagating uncertainty degrees. The second definition of conditioning is called product-based conditioning (or quantitative-based conditioning) where the unit interval is used in a general sense. In this case, the product operation can also be used in the propagation of uncertainty degrees. In the context of interval-based possibility theory [START_REF] Benferhat | Interval-based possibilistic logic[END_REF][START_REF] Benferhat | Compatible-based conditioning in interval-based possibilistic logic[END_REF][START_REF] Dubois | Timed possibilistic logic[END_REF], an extension of a conditioning operator is proposed for the interval-based setting. This is only done for the product-based conditioning. This extension is based on conditioning compatible possibility distributions and a syntactic counterpart for conditioning possibilistic logic bases is also proposed. In [START_REF] Coletti | Finitely maxitive t-conditional possibility theory: Coherence and extension[END_REF][START_REF] Coletti | Finitely maxitive conditional possibilities, bayesian-like inference, disintegrability and conglome Fuzzy Sets and[END_REF], the authors dealt with some issues regarding inference (propagating possibility and necessity bounds) and independence where the beliefs are encoded using the concept of uncertain conditionals in a possibilistic setting. This paper is primarily oriented to the study of min-based conditioning in an interval-based possibilistic setting and contains three major contributions:

• The first contribution (Section 4, Theorem 1) deals with conditioning in an interval-based possibility theory setting. We first propose three natural postulates for an interval-based conditioning. We show that any interval-based conditioning satisfying these postulates is necessarily based on applying minbased conditioning on each compatible standard possibility distribution.

• The second contribution (Section 4) consists in providing the exact lower and upper endpoints of minbased conditioning an interval-based distribution and a proposal of efficient procedures to compute the lower and upper endpoints of the conditional interval-based possibility distribution.

• The third contribution (Section 5) concerns syntactic computations of conditioning where intervalbased possibility distributions are compactly represented by interval-based knowledge bases. We show that interval-based conditioning has the same computational complexity as the standard min-based conditioning.

Before presenting these contributions, let us first provide a brief refresher on possibility theory and possibilistic logic.

Brief reminder on possibility theory and possibilistic logics

Possibility theory [START_REF] Dubois | Possibility theory and its applications: Where do we stand?[END_REF][START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] is a well-known alternative uncertainty theory. This framework was coined by L. Zadeh [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] and it is developed by several researchers (eg. Dubois and Prade [START_REF] Dubois | Possibility theory[END_REF], Yager [START_REF] Yager | Fuzzy Set and Possibility Theory: Recent Developments[END_REF] and Borgelt and Kruse [START_REF] Borgelt | Learning possibilistic graphical models from data, Fuzzy Systems[END_REF]). Possibility theory is based on a pair of dual measures allowing to evaluate the knowledge/ignorance relative to the event in hand. Among the main concepts of this framework are the ones of possibility distribution and possibilistic knowlegde base.

Possibility distributions

A possibility distribution, denoted π, is a mapping that attaches to every state ω of the world Ω (the universe of discourse or the set of states of the world) a degree in the unit interval [0, 1] expressing a partial knowledge over the world. The degree π(ω) associated with a state ω represents the degree of compatibility (or consistency) of the state ω with the available knowledge. By convention, π(ω)=1 means that ω is fully consistent with the available knowledge, while π(ω)=0 means that ω is impossible. π(ω)>π(ω ′ ) simply means that ω is more compatible than ω ′ . A possibility distribution π is said to be normalized if there exists an interpretation ω such that π(ω)=1, it is said to be subnormalized otherwise (subnormalized possibility distributions encode inconsistent sets of beliefs).

A possibility distribution allows to define two dual functions from 2 Ω to [0, 1] called possibility and necessity measures and denoted by Π and N respectively. They are defined as follows: Π(φ) = max{π(ω) : ω ∈ φ}, and

N (φ) = 1 -Π(φ).
Note that φ denotes the complement of φ in Ω (namely, φ=Ω\φ). Π(φ) measures to what extent the event φ is compatible with the available knowledge encoded by π while N (φ) measures to what extent it is entailed from π with certainty.

As already mentioned, possibility degrees are interpreted either i) qualitatively (in min-based possibility theory) where only the ordering of the values matters, or quantitatively (in product-based possibility theory) where the possibilistic scale [0, 1] is quantitative as in probability theory.

Conditioning a possibility distribution

In the standard possibilistic setting, conditioning comes down to updating a possibility distribution π encoding the current knowledge when a completely sure event called evidence or observation, denoted by φ⊆Ω, is received. This results in a conditional possibility distribution denoted by π(.|φ). There are many definitions of conditioning operators in the standard possibilistic setting [START_REF]Conditional possibilities independence and non interaction[END_REF][START_REF] De Campos | Possibilistic independence[END_REF]21,[START_REF] Fonck | A comparative study of possibilistic conditional independence and lack of interaction[END_REF][START_REF] Dubois | Bayesian conditioning in possibility theory[END_REF]. Hisdal [START_REF]Conditional possibilities independence and non interaction[END_REF] proposed that the definition of a conditioning operator in the qualitative setting should satisfy the condition: ∀ω ∈ φ, π(ω) = min(π(ω|φ), Π(φ)).

Dubois and Prade [START_REF] Dubois | The logical view of conditioning and its application to possibility and evidence theories[END_REF] proposed to select the largest conditional possibility distribution satisfying this condition, leading to the following conditioning operator.

Definition 1 (min-based conditioning). Let π be a possibility distribution, φ ⊆ Ω be a sure event. We define min-based conditioning of π by φ, simply denoted π(.| m φ) as:

∀ω∈ Ω, π(ω| m φ) =    1 if π(ω)=Π(φ) and ω∈φ; π(ω) if π(ω)< Π(φ) and ω∈φ; 0 otherwise. (1)
When Π(φ)=0, then by convention ∀ω∈Ω, π(ω| m φ)=1. Conditioning a possibility distribution π with a completely sure piece of information φ⊆Ω using Equation (1) results in a new and updated possibility distribution π ′ =π(.| m φ) that is normalized (namely, max ω∈Ω (π ′ (ω)=1) and fully accepting φ (namely, ∀ω / ∈φ, π ′ (ω)=0).

In case where possibility degrees are interpreted quantitatively like in the probabilistic setting, conditioning a possibility distribution is done using the so-called product-based conditioning [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF], defined as follows (for Π(φ) = 0):

π(ω i | * φ) = π(ωi) Π(φ) if ω i ∈ φ ; 0 otherwise. (2)
A possibility distribution can be compactly encoded in the form of possibilistic logic knowledge bases [START_REF] Lang | Possibilistic logic: complexity and algorithms[END_REF] or by means of possibilistic graphical models [START_REF] Borgelt | Learning possibilistic graphical models from data, Fuzzy Systems[END_REF]. In this paper, we deal only with possibility distributions compactly encoded in the form of possibilistic logic knowledge bases.

Possibilistic logic knowledge bases

Possibilistic knowledge bases [START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF][START_REF] Dubois | On various ways of tackling incomplete information in statistics[END_REF][START_REF] Lang | Possibilistic logic: complexity and algorithms[END_REF][START_REF] Dubois | Generalized possibilistic logic[END_REF][START_REF] Dellunde | Extending possibilistic logic over gödel logic[END_REF] are one of the well-known compact representations of possibility distributions. In possibilistic logic, weights are attached to formulas instead of elementary worlds. A possibilistic formula is a pair (ϕ, α) where ϕ is a propositional logic formula and α∈[0, 1] is a certainty degree associated with ϕ. The higher the certainty degree α is, the more important is the formula ϕ . A possibilistic base K = {(ϕ i , α i ), 1 ≤ i ≤ n} is simply a set of possibilistic formulas as shown in the following example.

Example 1. In this example, we consider a toy example from the medical area. The knowledge base K is given as follows:

Formulas Weights Flu ∨ Cold 1 ¬Fever 1 Cold ⇒ Sneezing .9 Flu ⇒ Cough .7 Flu .6
Given a possibilistic base K, we can generate a unique possibility distribution where interpretations ω satisfying all propositional formulas in K have the highest possible degree π(ω)=1 (since they are fully consistent), whereas the others are pre-ordered with respect to the highest formulas they falsify. More formally: Definition 2. Let K be a possibilistic knowledge base. Then, the corresponding possibility distribution π K is given by: ∀ω ∈ Ω,

π K (ω) = 1 if ∀(ϕ, α) ∈ K, ω ϕ 1 -max{α i : (ϕ i , α i ) ∈ K, ω ϕ i } otherwise. (3)
Ω here denotes the set of propositional interpretations. ω ϕ means that ω is a model of (or satisfies) ϕ in the sense of propositional logic. In this example, we have five propositional variables in the knowledge base K. Hence, the possibility distribution π K is over 2 5 states. Note that all the missing ones are associated with a zero possibility degree.

Example 2. (Example 1 continued) The possibility distribution induced by the knowledge base of

An important notion that plays a central role in the inference process and conditioning is the one of strict α-cut. Let α be a positive real number. A strict α-cut, denoted by K α , is a set of propositional formulas defined by K α = {ϕ : (ϕ, β) ∈ K and β > α}. The strict α-cut is useful to measure the inconsistency degree of K denoted by Inc(K) and defined by:

Inc(K) = 0 if K 0 is consistent max{α : K α is inconsistent} otherwise (4)
If Inc(K)=0 then K is said to be completely consistent. If a possibilistic base K is partially inconsistent, then Inc(K) can be seen as a threshold below which every formula is considered as not enough entrenched to be taken into account in the inference process.

The concept of α-cut can be used to provide the syntactic counterpart of conditioning a possibilistic knowledge base with a propositional formula: Definition 3. Let K be a possibilistic knowledge base and φ be a sure piece of information. The result of conditioning K by φ, denoted K φ is defined as follows:

K φ ={(φ, 1)} ∪ {(ϕ, α) : (ϕ, α) ∈ K and K ≥α ∧ φ is consistent.}
Namely, K φ is obtained by considering φ with a certainty degree '1', plus weighted formulas (ϕ, α) of K such that their α-cut is consistent with φ (the notation K ≥α means the formulas of K associated with degrees greater or equal to α). It can be checked that:

∀ω ∈ Ω, π K φ (ω) = π K (ω|φ).
Next section briefly recalls main concepts of interval-based possibility theory and interval-based possibilistic logic.

Interval-based extension of possibilistic logic

Before giving a refresher on interval-based possibility theory [START_REF] Benferhat | Interval-based possibilistic logic[END_REF], let us first start with an example to motivate the current work.

Example 3. Let us choose an example from the football competitions area. Suppose we are interested in betting on football competitions. To increase our chances, we decided to do a survey on the Internet concerning the upcoming Euro championship. This survey is concerned with the views of football fans and supporters about the chances of two national teams we are interested in to reach the final. For the sake of simplicity, assume that we are interested only in the chances that the french and german teams have to get into the final match. We denote in the remainder of this example by f (resp. g) the statement that the french (resp. german) team will get into the final. To collect people's opinions, we posted a question on a specialized Internet survey platform. In addition, we also asked people to specify how much they believe in their answers using a unit scale [0, 1] with the convention that the degree 1 should be attached to the most plausible scenario1 while the degree 0 totally excludes the corresponding scenario. Values in between allow to rank order the other scenarios. Assume that we've got answers from five people p 1 ,..,p 5 . We've got the plausibility levels of these people with respect to the different scenarios summarized as follows:

In this example, the confidence degrees provided by the responders can be viewed as possibility degrees. Now, suppose that we got hundreds or thousands of answers or suppose that there is a large number of variables, then it makes sense to find a compact way to encode the obtained answers and more importantly to reason with them (answer any request of interest and update the available information when new sure information is obtained). Interval-valued possibility theory is suited for encoding and reasoning with this kind Let us now formally introduce the concept of interval-based possibility distributions and interval-based possibilistic knowledge bases.

p 1 p 2 p 3 p 4 p 5 f g 1 1 1 .8 .

Interval-based possibility distributions

As illustrated in Table 2, in the interval-based possibilistic setting, the available knowledge is encoded by an interval-based possibility distribution Iπ where each state ω is associated with an interval Iπ(ω) = [Iπ(ω),Iπ(ω)] of possible values of the possibility degree π(ω) [START_REF] Benferhat | Interval-based possibilistic logic[END_REF]. If I is an interval, then we denote by I and I its upper and lower endpoints respectively. When all I's associated with interpretations (or formulas) are singletons (meaning that I = I), we refer to standard distributions (resp. standard possibilistic bases). Here, Iπ(ω) (resp. Iπ(ω)) denotes the lower (resp. upper) endpoints of the possibility degree of ω.

Definition 4 (Interval-based possibility distribution). An interval-valued possibility distribution Iπ is a mapping Iπ : Ω→I from the universe of discourse Ω to the set I of all subintervals of the interval [0, 1], with the normalization property requiring that max ω∈Ω Iπ(ω)=1.

As in [START_REF] Benferhat | Interval-based possibilistic logic[END_REF], we also interpret an interval-based possibility distribution as a family of compatible standard possibility distributions defined by: Definition 5. Let Iπ be an interval-based possibility distribution. A normalized possibility distribution π is said to be compatible with Iπ if and only if ∀ω ∈ Ω, π(ω) ∈ Iπ(ω).

An interval-based possibility distribution accepts at least one compatible distribution. We denote by C(Iπ) the set of all compatible possibility distributions with Iπ.

Example 4. Let Iπ be a possibility distribution described in the Table 3. Then following Definition 5, the possibility distribution π 1 and π 2 (from Table 3) are compatible with Iπ. However, π 3 is not compatible with Iπ since π 3 (f g)=.2 ∈ [.5, 1]=Iπ(f g).

The following defines the concept of interval closure of a set of uncertainty degrees Definition 6 (Interval closure). Let A be a set of degrees between 0 and 1. We define the interval closure of A, denoted by IntCl(A), as the smallest (narrowest) interval that contains all the elements of A.

ω∈Ω Iπ(ω) Let us now first provide a brief reminder of interval-based possibilistic logic bases [START_REF] Benferhat | Syntactic Computation of Hybrid Possibilistic Conditioning under Un in: IJCAI[END_REF] which allow to compactly represent interval-based possibility distributions.

ω∈Ω π 1 (ω) π 2 (ω) π 3 (ω) f g [ .5, 1] f g .8 1 .2 f ¬g [ .7, 1] f ¬g 1 .8 1 ¬f

Interval-based possibilistic logic

Contrary to the standard possibilistic logic where the uncertainty is described with single values, intervalbased possibilistic logic uses intervals. We use closed sub-intervals I⊆[0, 1] to encode the uncertainty associated with formulas or interpretations.

Iπ IK (ω) = Iπ IK (ω), Iπ IK (ω)
where:

Iπ IK (ω) = 1 if ∀(ϕ, I) ∈ IK, ω |= ϕ 1 -max{I : (ϕ, I) ∈ K, ω ϕ} otherwise.
and

Iπ IK (ω) = 1 if ∀(ϕ, I) ∈ IK, ω |= ϕ 1 -max{I : (ϕ, I) ∈ K, ω ϕ} otherwise.
Given an interval-based possibilistic base IK, we define two particular compatible possibilistic bases IK and IK by selecting either lower endpoints of intervals or upper endpoints of intervals:

• IK = {(ϕ, α) : (ϕ, [α, β]) ∈ IK } • IK = {(ϕ, β) : (ϕ, [α, β]) ∈ IK }

Three natural requirements for the interval-based conditioning

The first natural requirement concerns the degenerate case, namely when each interval Iπ(ω) contains exactly one single degree π(ω). The result of the new conditioning procedure should coincide with the result π(.| m φ) of the original conditioning procedure (Definition 1). For each possibility distribution π, by [π, π] we denote its interval-valued representation, i.e., an interval-valued possibility distribution for which, for every ω∈Ω, we have Iπ(ω)=[π(ω),π(ω)]. In these terms, the above requirement takes the following form: The second requirement is related to the fact that we do not know the exact values π(ω) since we only have partial information about them. In principle, if we can get some additional information about these values, then this would lead, in general, to narrower intervals (indeed, the width of an interval captures the ignorance regarding the exact value of π(ω)). Let us define the concepts of meta-specificity between interval-based possibility distributions: Definition 9. Let Iπ and Iπ ′ be two interval-based possibility distributions. Then Iπ is said to be more meta-specific than Iπ ′ , denoted Iπ⊆Iπ ′ , if Iπ(ω)⊆Iπ ′ (ω) holds for all ω∈Ω It is reasonable to require that if we have new information about the original values π(ω), this should help us also to narrow down the corresponding values of conditional distributions:

P2. If Iπ is more meta-specific than Iπ ′ (namely, Iπ⊆Iπ ′ ) then Iπ(.|φ) is more meta-specific than Iπ ′ (.|φ) (namely, Iπ(.|φ)⊆Iπ ′ (.|φ)).
It is obvious that postulates P1 and P2 are not sufficient to fully characterize the new extension. For example, we can take ([π, π])(.|φ)=[π(.| m φ), π(.| m φ)] for degenerate interval-valued possibility distributions and Iπ(ω|φ)=[0, 1] for all other Iπ. To avoid such extensions, it is reasonable to impose the following minimality condition: P3. Iπ(.|φ) is the narrowest interval-based distribution satisfying P1-P2. Namely, there exist no operation Iπ(.| 1 φ) that satisfies both properties P1-P2 and for which:

• Iπ(ω| 1 φ) ⊆ Iπ(ω|φ) for all Iπ, ω, and φ,

• Iπ(ω| 1 φ) = Iπ(ω|φ) for some Iπ, ω, and φ.

P3. ensures that Iπ(.|φ) computed applying the min-based conditoning on the compatible distributions cannot be narrowed further using another conditioning operator while satisfying properties P1, P2.

The following theorem provides our first main result where we show that there is only one interval-based conditioning satisfying P1-P3 and where the interval conditional possibility degree Iπ(ω|φ) is defined as the interval closure of the set of all π(.| m φ), where π is compatible with Iπ.

Theorem 1. There exists exactly one interval-based conditioning, denoted by Iπ(.| m φ), that satisfies the properties P1-P3, and which is defined by: ∀ω ∈ Ω,

Iπ(ω| m φ) = IntCl({π(ω| m φ) : π ∈ C(Iπ)}) ( 5
)
where IntCl is the interval closure given in Definition 6.

Proof. 1 • . We need to prove:

• that this closure Iπ(.| m φ) satisfies the properties P1-P3, and

• that every operation Iπ(.|φ) that satisfies the properties P1-P3 coincides with the interval closure of Iπ(.| m φ). Since the set Iπ(ω|φ) is an interval, it therefore contains, with the set {π(ω|φ) : π∈C(Iπ)}, its interval closure, i.e., the set Iπ(ω| m φ). Thus, we conclude that Iπ(ω| m φ) ⊆ Iπ(ω|φ) for all ω.

The statement is proven.

4

• . We can now prove that Iπ(.| m φ) also satisfies the property P3. Indeed, if there is some other operation | 1 that satisfies P1 and P2, and for which Iπ(ω| 1 φ) ⊆ Iπ(ω| m φ) for all ω, then, since we have already proven the opposite enclosure in Part 3 of this proof, we conclude that Iπ(ω| 1 φ) = Iπ(ω| m φ) for all ω, so indeed no narrower conditioning operation is possible. 5 • . To complete the proof and show that there is only one solution, let us show that if some Iπ(.|φ) satisfies the properties P1-P3, then it coincides with Iπ(.| m φ).

Indeed, by Part 3 of this proof, we have Iπ(ω| m φ) ⊆ Iπ(ω|φ) for all ω. If we had Iπ(ω| m φ) = Iπ(ω|φ) for some ω and φ, this would contradict the minimality property P3. Thus, indeed, Iπ(.| m φ) = Iπ(.|φ). Uniqueness is proven, and so is for the proposition.

We can now go one step beyond Theorem 1 and provide the exact bounds of intervals associated with Iπ(.| m φ).

Computing lower and upper endpoints of conditional interval-based possibility distributions

The aim of this section is to compute the lower and upper endpoints of the conditional interval-based possibility distribution.

Proposition 1. Let Iπ be an interval-based distribution. Then the interval-based conditional distribution, satisfying P1-P3, is described by Iπ(ω| m φ)=[Iπ(ω| m φ), Iπ(ω| m φ)], such that ∀ω∈Ω:

Iπ(ω| m φ)=    0 if ω ∈ φ 1 if ∀ω ′ = ω, ω ′ ∈ φ and Iπ(ω) ≥ Iπ(ω ′ ) Iπ(ω) otherwise and Iπ(ω| m φ)=    0 if ω ∈ φ 1 if Iπ(ω) ≥ IΠ(φ), Iπ(ω) otherwise
Let us briefly comment Proposition 1. Let ω∈Ω be an interpretation. First, for ω ∈φ, whatever the considered compatible possibility distribution π, we have π(ω| m φ)=0. Hence, Iπ(ω| m φ)=[0, 0]. Assume now that ω∈φ and ∀ω ′ ∈φ, Iπ(ω)≥Iπ(ω ′ ). This means that whatever is the considered compatible possibility distribution π, we have π(ω)≥max{π(ω): ω∈φ}=Π(φ). Hence, π(ω| m φ)=1 and Iπ(ω| m φ)= [START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF][START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF]. Now, the last case for determining lower endpoint concerns the case where ∃ω ′ ∈φ such that Iπ(ω)<Iπ(ω ′ ). This means that there exists a compatible possibility distribution π such that π(ω)=Iπ(ω)<Π(φ), hence π(ω| m φ)=Iπ(ω) which is the smallest possible value. Similar reasoning goes for upper endpoints.

Example 7. Let Iπ of Table 5 (left side table) be the interval-based possibility distribution that we want to condition with the new piece of information φ=¬c. min-based conditional distribution Iπ(.| m φ) given in Table 5 (right side table) is obtained using either Proposition 1 or Theorem 1. For instance, for ω=ab¬c, whatever the considered compatible possibility distribution π, we have π(ab¬c|φ) between .1 and 1. Thus, the interval closure of Iπ(ab¬c|

m φ)=[.1, 1]. ω∈Ω Iπ(ω) ω∈Ω Iπ(ω|φ) abc [ 1, 1 ] abc [ 0, 0 ] a¬bc [ .4,.6] a¬bc [ 0, 0 ] ¬abc [ .3,.6] ¬abc [ 0, 0 ] ¬a¬bc [ .3,.6] ¬a¬bc [ 0, 0 ] ab¬c [ .1,.7] ab¬c [ .1, 1] a¬b¬c [ .4,.6] a¬b¬c [ .4, 1] ¬ab¬c [ .1,.6] ¬ab¬c [ .1, 1] ¬a¬b¬c [ .3,.6] ¬a¬b¬c [ .3, 1]
Table 5: Interval-based distribution Iπ and its conditioned distribution Iπ(.|φ)

Syntactic computations of interval-based conditioning

In this section, we provide the syntactic counterpart of the interval-based conditioning presented above.

Computing conditioned knowledge bases

Given an interval-based possibilistic knowledge base IK and a new evidence φ, our aim is to compute the conditional base IK φ corresponding to conditioning the information encoded in IK with φ. As illustrated in Figure 1, the aim of this subsection is therefore to propose the syntactic characterization of conditioning such that:

∀ω ∈ Ω, Iπ IK (ω| m φ) = Iπ IK φ (ω),
where Iπ IK φ is the interval-based distribution associated with IK φ , and Iπ IK (.| m φ) is the result of conditioning Iπ IK using the conditioning operator presented in the previous subsection (Proposition 1 or Theorem 1), and [φ] is the set of models of φ. We first need to introduce some notations.

IK Iπ IK IK φ Iπ IK (.|φ) Iπ IK φ (.)
• α = Inc(IK ∪ {(φ, 1)}) and β = Inc(IK ∪ {(φ, 1)}), Intuitively, α and β compute inconsistency degree intervals resulting from assuming that φ is fully true. This offers a characterization of IΠ(φ)=1 -β and IΠ(φ)=1 -α.

• Let ω * be a model of {ψ : (ψ, I) ∈ IK and I>β} ∪ {φ}.

Let IK ¬ω * =IK ∪ {(¬ω * , [1, 1]
)} be a base obtained by adding the negation of ω * , then we compute γ = Inc(IK ¬ω * ∪ {(φ, 1)}). Models ω of {ψ : (ψ, I) ∈ IK and I > β} are exactly those having Iπ(ω)=IΠ(φ). γ computes the second best value of models of φ (since a model ω * is excluded from IK) which is very useful for characterizing Iπ(ω| m φ).

With the help of these notations, we are now ready to present the third contribution of this paper. The knowledge base IK φ resulting from conditioning IK with φ is composed of three parts:

• The first consists in adding φ as a fully certain information, {(φ, [1, 1])}. From Definition 8, all worlds that are outside φ (not satisfying φ) are excluded. This is in accordance with Proposition 1.

• The second part, {(ϕ, I) : (ϕ, I)∈IK, and I>α}, contains a subbase of IK where the intervals are unchanged. This encodes the third item of definition of Iπ(ω) and Iπ(ω) in Proposition 1 (recall that 1 -α=IΠ(φ)).

• The last part encodes exactly the situation where some possibility degrees (in Proposition 1) are shifted up to 1. This is reflected in possibilistic knowledge bases by shifting down some certainty degrees to 0.

Indeed, the knowledge base IK φ is composed of three parts: i) the new sure piece of evidence φ associated with the interval [START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF][START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF], ii) the formulas in IK that belong to the consistent part of IK with φ (the intervals associated with this second part are kept unchanged) while iii) the last part, namely formulas in the inconsistent part of IK with φ will see their intervals changed to allow satisfying the normalization condition at semantic level. Recall that to ensure a possibility degree of 1 at the semantic level, the insconsistency degree of at least one compatible base should be 0.

Proof. In order now to prove the theorem we have to show that ∀ω∈Ω, Iπ IK φ =Iπ IK (.| m [φ]). First note that if an interpretation ω is not a model of φ, then by definition we have:

Iπ IK φ (ω) = Iπ IK (ω| m [φ]) = [0, 0]
This is explained by the presence of (φ, [START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF][START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF]) in IK φ . Now, for ω|=φ, we have two distinct cases:

• The case where ω falsifies a formula from: {(ϕ, I) : (ϕ, I)∈IK, and I>α} then: 5. Let φ=¬c (and φ=[φ] the set of models of ¬c) be the new evidence. For the computation of IK φ , let us first compute the values of α, β and γ. Then, we have: α=Inc({(a∧b, .6), (a, .7), (c∨¬b, .9), (¬c, 1)})=.6, β=Inc({(a∧b, .4), (a, 0), (c∨¬b, .3), (¬c, 1)})=.3 and γ=.4.

Iπ IK φ (ω) =
Hence, according to Theorem 2, the result of conditioning IK by φ is given by: IK φ ={(a∧b, [0, .6]), (a, [0, .7]), (c∨¬b, [0, .9]), (¬c, [START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF][START_REF] De Clercq | Multilateral negotiation in boolean games with incomplete information using generalized possibilistic logic[END_REF])}. And if we compare with Example 7, where the distribution Iπ(.| m φ) is conditioned according to Proposition 1 then the associated interval-based distribution to IK φ is exactly the same. Hence, Theorem 2 indeed provides a compact encoding of the conditioning procedure.

The following proposition gives the computational complexity of conditioning an interval-based possibilistic knowledge base IK according to Theorem 2. Proposition 2. Let IK be an interval-based possibilistic knowledge base and φ be the new evidence. Let IK φ be an interval-based possibilistic knowledge base computed according to Theorem 2. Then IK φ have the same size as IK and computing IK φ is in O(log 2 (m).SAT ) where SAT is a satisfiability test of a set of propositional clauses and m is the number of different weights in IK and IK.

Clearly, once the parameters α, β, γ are computed, computing IK φ from {IK, φ, α, β, γ} is straightforward and it is done in linear time. Indeed, computing α, β, γ mainly comes down to compute the inconsistency degrees of IK and IK. This needs log 2 (m) calls to a SAT solver exactly as in standard possibilistic logic [START_REF] Lang | Possibilistic logic: complexity and algorithms[END_REF]. Hence, the syntactic counterpart of conditioning an interval-based possibilistic base has exactly the same computational complexity as computing the min-based conditioning of a standard possibilistic base.

Concluding remarks and discussions

This paper addressed the issue of conditioning in a qualitative interval-based possibilistic setting. The interval-based extension of the standard possibilistic setting offers a flexible model for encoding multiple source information. However, no form of qualitative conditioning has been proposed in this framework. This work fills this gap by proposing an efficient extension of the min-based conditioning to the interval-based setting. Three main contributions are presented: i) A set of three natural postulates P1-P3 ensuring that any interval-based conditioning satisfying these three postulates is necessarily based on min-based conditioning the set of compatible standard possibility distributions. The first postulate P1 aims to recover the standard min-based conditioning in case where all the intervals contain singleton values (all lower endpoints coincide with upper endpoints).

The second postulate P2 captures a kind of meta-specificity regarding conditioning interval-based sets of beliefs while the third postulate P3 aims to ensure a minimality condition.

ii) Efficient procedures to compute the lower and upper endpoints of the conditional interval-based possibility distribution. Such procedures exclude any state of the world that is inconsistent with the new evidence in hand and perform some kind of normalization based on the concept of compatible possibility distribution without generating the whole set of compatible distributions.

iii) A syntactic counterpart of conditioning interval-based possibilistic bases. This counterpart performs some tests and does some modifications on the formulas of the original knowledge base such that the new evidence is integrated with a certainty degree of 1. This ensures the same result as if the knowledge base were conditioned at the semantic level.

Interestingly enough, the syntactic counterpart has the same complexity as conditioning standard possibilistic knowledge bases. More precisely, conditioning an interval-based possibilistic knowledge base does not require extra computational cost compared with conditioning a standard possibilistic base.

Our approach can be applied in many applications, especially when dealing with multiple sources or imprecise qualitative information. The approach is appealing since it allows a compact representation of knowledge while the conditioning operation is performed in time complexity equivalent to conditioning a standard possibilistic knowledge base. Indeed, the proposed approach generalizes the standard qualitative possibilistic conditioning and allows to update the current knowledge a syntactic way without any extra cost compared to conditioning standard possibilistic knowledge bases.

In [START_REF] Benferhat | Compatible-based conditioning in interval-based possibilistic logic[END_REF], a set of seven postulates IC1-IC7 have been proposed for product-based conditioning (which is another form of conditioning in a standard but quantitative possibility theory, see Equation 2). To relate our postulates P1-P3 to postulates IC1-IC7, note that IC1-IC7 use the product-based operator while P1-P3 use the min-based conditioning. Now, if P1 is replaced by P'1 stating that:

Then we can show that an interval-based conditioning that satisfies P'1, P2, P3 necessarily satisfies IC1-IC7 but the converse is false. Indeed, as pointed out in [START_REF] Benferhat | Compatible-based conditioning in interval-based possibilistic logic[END_REF], using the unique conditioning satisfying properties IC1-IC7 may lead in some situations to discontinuous intervals if we rely on the min-based conditioning.

In [START_REF] Coletti | Finitely maxitive t-conditional possibility theory: Coherence and extension[END_REF][START_REF] Coletti | Finitely maxitive conditional possibilities, bayesian-like inference, disintegrability and conglome Fuzzy Sets and[END_REF][START_REF] Coletti | Coherent t-conditional possibility envelopes and nonmonotonic reasoning[END_REF], the authors deal with some issues like inference and conditioning in a possibilistic setting where the available knowledge consists in a set of conditional events. In particular, the authors deal with such issues using different t-norms including the min-based operator. While they refer to classes of conditional possibility measures, there is no reference to interval-based possibility distributions or interval-based knowledge bases as representations encoding the available knowledge. The current paper proposes the first min-based conditioning operator for interval-based possibilistic knowledge bases.

Recently, in [START_REF] Benferhat | Set-valued conditioning in a possibility theory setting[END_REF], we proposed a set-valued extension to possibility theory. We provide a characterization of set-valued possibilistic logic bases and set-valued possibility distributions in terms of compatible possibilistic logic bases and compatible possibility distributions respectively. The main difference between the interval-based representation proposed in this paper and the set-based one in [START_REF] Benferhat | Set-valued conditioning in a possibility theory setting[END_REF] is that summarizing a set of knowledge bases (resp. a set of possibility distributions) within an interval-based knowledge base (resp. interval-based possibility distribution) incurs more information loss. However, both representations are non trivial and guarantee that the semantics given to the interval-based/set-based representation in terms of compatible bases/distributions contains the initial knowledge bases or possibility distributions. Moreover, the interval-based representation requires less computations when it comes to reasoning and conditioning.

As a future work, we will address conditioning in another form of compact representations of intervalbased possibility distributions which are interval-based possibilistic networks [START_REF] Benferhat | Interval-based possibilistic networks[END_REF].

Definition 7 .

 7 The syntactic representation of interval-based possibilistic logic generalizes the notion of a possibilistic base to an interval-based possibilistic knowledge base. Formally, An interval-based possibilistic knowledge base, denoted by IK, is a set of propositional formulas associated with intervals of certainty degrees:IK = {(ϕ, I), ϕ ∈ L and I is a closed sub-interval of [0, 1]}In Definition 7, ϕ∈L denotes a formula of a propositional language L. As in standard possibilistic logic, an interval-based knowledge base IK is also a compact representation of an interval-based possibility distribution Iπ IK[START_REF] Benferhat | Interval-based possibilistic logic[END_REF]. Definition 8. Let IK be an interval-based possibilistic base. Then :

Example 6 .

 6 Let IK={(a∧b, [.4, .5]), (¬a∨b, [.3, .9])} be an interval-based possibilistic base. The intervalbased possibility distribution corresponding to IK according to Definition 8 is given in Table4.From the knowledge base IK, we can compute Inc(IK) (with IK={(a∧b, .4), (¬a∨b, .3)}) which is 0 since IK is fully consistent. ω Iπ IK (ω) ab [ 1, 1 ] a¬b [.1, .6] ¬ab [.5, .6] ¬a¬b [.5, .6] Table 4: Example of an interval-based distribution induced by an interval-based knowledge base. This is for the representation part of the interval-based possibilistic setting. The question now is how to extend the min-based conditioning operator for conditioning interval-valued possibility distributions and interval-valued possibilistic logic knowledge bases? 4 Conditioning interval-valued possibility distributions Before presenting our interval-based extension to the min-based possibilistic conditioning, let us first focus on some natural properties that an interval-based conditioning should satisfy in a possibilistic setting.

P1.

  For all π, φ⊆Ω and ω∈Ω, ([π, π])(ω|φ)= [π(ω| m φ), π(ω| m φ)]. In other terms, let π be any possibility distribution and Iπ such that ∀ω, Iπ(ω)=[π(ω), π(ω)]. Then ∀φ, Iπ(ω|φ)=[π(ω| m φ), π(ω| m φ)].

2 •

 2 . One can easily check that Iπ(.| m φ) satisfies the properties P1-P2. 3 • . Let us now prove that if an operation Iπ(.|φ) satisfies the properties P1-P2, then for every Iπ and φ, we have Iπ(.| m φ) ⊆ Iπ(.|φ). Then, for every distribution π∈C(Iπ), we have ([π, π]) ⊆ Iπ and thus, due to the postulate P2, we have ([π, π])(.|φ) ⊆ Iπ(.|φ). By the property P1, we have ([π, π])(ω|φ) = [π(ω|φ), π(ω|φ)]. Thus, the above inclusion means that π(.|φ) ∈ Iπ(.|φ). The interval Iπ(ω|φ) therefore contains all the values π(ω|φ) corresponding to all possible π∈C(Iπ): {π(ω|φ) : π ∈ C(Iπ)} ⊆ Iπ(ω|φ).

Figure 1 :

 1 Figure 1: Conditioning interval-valued possibilistic information at the semantic and syntactic levels

Theorem 2 .

 2 Let IK be an interval-based knowledge base. Let Iπ IK be its associated possibility distribution. Let IK φ ={(φ, [1, 1])} ∪ {(ϕ, I) : (ϕ, I)∈IK, and I>α} ∪ {(ϕ, [0, I]) : (ϕ, I)∈IK, and I<α and I>γ}. Then: ∀ω, Iπ IK (ω| m φ) = Iπ IK φ (ω); where Iπ IK (.| m φ) is the result of applying min-based interval conditioning on Iπ IK (see Proposition 1 and Theorem 1), and Iπ IK φ is the interval-based distribution associated with IK φ using the Definition 8.

Example 8 .

 8 1-max{I : (ϕ, I) ∈ IK and I>α}. = 1-max{I : (ϕ, I) ∈ IK and I>Inc(IK ∪ {(φ, 1)})} = 1-max{I : (ϕ, I) ∈ IK and I>1-IΠ([φ])} = 1-max{I : (ϕ, I) ∈ IK and 1-I<IΠ([φ])} = Iπ(ω) if Iπ(ω)<IΠ([φ]) = Iπ IK (ω| m [φ]).Iπ IK φ (ω) = 1-max{I : (ϕ, I) ∈ IK and I>α}.= 1-max{I : (ϕ, I) ∈ IK and I>Inc(IK ∪ {(φ, 1)})} = 1-max{I : (ϕ, I) ∈ IK andI>1-IΠ([φ])} = 1-max{I : (ϕ, I) ∈ IK and 1-I<IΠ([φ])} = Iπ(ω) if Iπ(ω)<IΠ([φ]) = Iπ IK (ω| m [φ]).• The case where ω falsifies a formula from: {(ϕ, [0, I]) : (ϕ, I)∈IK, and I≤α and I>γ} then:As γ computes the second best value of models of φ, for this proof, we use secondbest(IK) to determine γ and secondbest(IK) = 1-secondbest(Iπ IK ).Iπ IK φ (ω) =1-max{I : (ϕ, I) ∈ IK and I≤α and I>γ} = 1-max{I : (ϕ, I) ∈ IK and I≤Inc(IK ∪ {(φ, 1)}) and I>secondbest(IK)} = 1-max{I : (ϕ, I) ∈ IK and I≤1-IΠ([φ]) and I>1-secondbest(Iπ IK )} = 1-max{I : (ϕ, I) ∈ IK and 1-I≥IΠ([φ]) and 1-I<secondbest(Iπ IK )} = Iπ(ω) if Iπ(ω)≥IΠ([φ]) and Iπ(ω)<secondbest(Iπ IK ) = Iπ IK (ω| m [φ]). Iπ IK φ (ω) = 1-max{0 : (ϕ, I) ∈ IK and I≤α and I>γ}. = 1-max{0 : (ϕ, I) ∈ IK and I≤Inc(IK ∪ {(φ, 1)}) and I>secondbest(IK)} = 1-max{0 : (ϕ, I) ∈ IK and I≤1-IΠ([φ]) and I>1-secondbest(Iπ IK )} = 1-max{0 : (ϕ, I) ∈ IK and 1-I≥IΠ([φ]) and 1-I>secondbest(Iπ IK )} = 1 if Iπ(ω)≥IΠ([φ]) and Iπ(ω)<secondbest(Iπ IK ) = Iπ IK (ω| m [φ]). Let us see an example to illustrate Theorem 2. Let IK be an interval-based possibilistic knowledge base such that IK={(a∧b, [.4, .6]), (a, [0, .7]), (c∨¬b, [.3, .9])}. The associated interval-based possibility distribution π IK (using Definition 8) is the same as the one given in Table

P' 1

 1 ∀π, φ ⊆ Ω and ω ∈ Ω, ([π, π])(ω|φ) = [π(ω| * φ), π(ω| * φ)].

  Example 1 is as follows:

	State (ω) πK (ω)
	Flu Cold Fever Sneezing Cough	0.0
	Flu Cold Fever Sneezing ¬Cough	0.0
	Flu Cold Fever ¬Sneezing Cough	0.0
	Flu Cold Fever ¬Sneezing ¬Cough	0.0
	Flu Cold ¬Fever Sneezing Cough	1.0
	Flu Cold ¬Fever Sneezing ¬Cough	0.3
	Flu Cold ¬Fever ¬Sneezing Cough	0.1
	Flu Cold ¬Fever ¬Sneezing ¬Cough	0.1
	Flu ¬Cold Fever Sneezing Cough	0.0
	... ... ... ... ...	...
	... ... ... ... ...	...
	¬Flu ¬Cold ¬Fever ¬Sneezing ¬Cough	0.0

Table 1 :

 1 Example of multiple sources information of information. For instance, the available knowledge from Example 3 could be summarized as an intervalvalued possibility distribution given in Table2.

	5

Table 2 :

 2 Interval-based distribution corresponding to the multiple source information of Table1.

Table 3 :

 3 g [.2, .6] Example of compatible and non compatible possibility distributions. Example 5. Assume that A is a set defined as follows: A=[.8, .9]∪{1} then the closure of A is IntCl(A)=[.8, 1]. Clearly, the interval [.8, 1] is the narrowest sub-interval of [0, 1] containing all the values of A.

		¬f g	.5	.3	.5
	¬f ¬g [.3, .6]	¬f ¬g	.5	.6	.6

In this example, the scenario f g means both French and German teams will attend the final match while the scenario f ¬g means that the french team will attend the final contrary to the german team .


Christian Artigues
email: christian.artigues@laas.fr

Pierre Lopez
email: pierre.lopez@laas.fr

Alain Ha Ït
email: alain.hait@isae.fr

May 13-15 MONTR ÉAL -CANADA Scheduling under energy constraints ⋆

Keywords: Production scheduling, energy constraints, constraint propagation, energy reasoning

In this paper we present a scheduling problem dealing with energy constraints (typically electrical energy). Mainly we propose an extension of specific resource constraint propagation techniques (known as "energy reasoning") to efficiently prune the search space and then to facilitate its resolution. We also present dominance rules and a branching scheme to solve the problem via tree search. Finally, computational results are provided.

Introduction

Since the last two decades, hard combinatorial problems, mainly in scheduling, have been the target of many approaches combining Operations Research and Artificial Intelligence techniques. These approaches are generally focussed on constraint satisfaction as a general paradigm for representing and solving efficiently such problems. At the heart of these approaches, a panel of consistency enforcing techniques is used to dramatically prune the search space.

Therefore propagation techniques dedicated to resource and time constrained scheduling problems, viewed as special instances of Constraint Satisfaction Problems (CSP), have been developed to speed up the search for a feasible schedule or to detect early an inconsistency. For instance the energy reasoning [START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF] has enabled the joint integration of both resource and time constraints in order to prevent the combinatorics of solving conflicts between activities in competition for limited resources. Furthermore, it is still of interest to search for propagating novel types of constraints according to real world problems. The new environmental constraints, but also the increase of the energy cost, should prompt us to consider as a crucial and promising issue to look into the problem of the power consumption optimization in production scheduling. Real-time (processor) scheduling theory has often addressed energy constraints. However, the consideration of energy constraints in production scheduling, and particularly focussed on constraint propagation techniques, has been relatively unexplored.

The objective of this paper is to present a formal description for the propagation of energy constraints induced by machine power consumptions. The idea is to apply the generic energy reasoning in scheduling and to extend it for the consideration of electric power consumptions. This paper is then organized as follows: Section 2 presents the problem under study. A new problem, the energy scheduling problem (EnSP), is introduced. Section 3 presents a short review of related work. Section 4 reminds the reader of the bases of the energy reasoning in scheduling. Section 5 proposes the above-mentioned extensions of this reasoning to process the energy constraints. In Section 6 we present dominance rules in order to reduce the search space. In Section 7, a branching scheme is proposed to solve the problem via tree search. Computational experiments are described in Section 8.

The scheduling problem under energy constraints

In this section we introduce the energy scheduling problem (EnSP). We first present the related cumulative scheduling problem (CuSP). Then we present the EnSP. Finally we show how we can model an industrial parallel machine scheduling problem with electrical energy constraints as an association of an EnSP and a CuSP.

The cumulative scheduling problem

A CuSP is a sub-problem of the RCPSP (resource-constrained project scheduling problem), in which precedence constraint are relaxed and a single resource is considered at a time [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF]. The problem is also called the multiprocessor task problem and is denoted P |r i , d i ; size i |in the well-known three field scheduling notation [START_REF] Drozdowski | Scheduling multiprocessor tasks -an overview[END_REF]. An instance of the CuSP can be defined as follows: a set of n activities A = {1, 2, . . . , n} is to be processed without interruption on a given resource of capacity B. To each activity i are associated its resource requirement b i , its release date r i , its deadline d i , and its processing time p i (note that capacity and resource requirements are assumed to be constant over the planning horizon). The CuSP can be stated as follows. Activity i start time (st i ) and completion time (f t i = st i + p i ) have to belong to the time window [r i , d i ]. Activities can be simultaneously processed according to the satisfaction of the cumulative constraint: i∈A b it ≤ B, for every time point t, where b it = b i if st i ≤ t < f t i and b it = 0 otherwise.

The energy scheduling problem

The energy scheduling problem (EnSP) takes as input a set of n activities A = {1, 2, . . . , n} having to be processed without interruption using an energy resource of capacity (available power) B. Instead of being defined through its duration p i and resource demand b i , each activity is defined through its required energy W i , and its minimum and maximum resource requirements b min i and b max i such that the number of allocated resource units (provided power) has to remain between b min i and b max i . Note here that for practical motivations, we consider that changes in the power allocated to an activity only occur at discrete time periods. The EnSP amounts to find a start time st i ≥ r i , a completion time

f t i ≤ d i and a power allocation b it such that b min i ≤ b it ≤ b max i for t ∈ [st i , f t i -1]
and b it = 0 otherwise. The global power limitation constraint is written i∈A b it ≤ B for any time period t. We consider both b it and p i = f t ist i as discrete variables. Last, an energy requirement constraint W i ≤ f ti-1 t=sti b it , holds for each activity i, i.e. the energy brought to i must be at least W i . We remark that enforcing equality would yield to possibly infeasible solutions in the case where the remaining energy to be brought to an activity at a given time period is strictly lower than b min i . Consequently, in accordance with practical cases, we consider the energy brought to an activity can be larger than the required one.

Consider a problem instance with B = 5 and 3 activities such that

W 1 = 12, b min 1 = 1, b max 1 = 5, r 1 = 0, d 1 = 6,W 2 = 12, b min 2 = 2, b max 2 = 5, r 2 = 2, d 2 = 6, W 3 = 6, b min 3 = b max 3 = 2, r 3 = 2, d 3 = 5.
Figure 1 displays a feasible solution for the problem. One can observe that there is no solution for which all the activities have a rectangular shape.

Industrial case modeling example

As a typical application, consider a tubing plant in the Montréal area, presented in [START_REF] Haït | Ordonnancement sous contraintes d'énergie et de ressources humaines[END_REF][START_REF] Trépanier | Modélisation des impacts du délestage énergétique sur la production[END_REF], and more precisely, the foundry where metal is melted in induction furnaces and then cast in individual billets. The melting operation has a variable duration that depends on the power given to the furnace (constrained by physical and operational considerations).

The foundry has five production lines. From a scheduling view-point, this facility can easily be recognized as a parallel machine problem. The electric power is a cumulative resource which is a generalization of a parallel-machine type resource.

A standard parallel machine problem can be modeled as a CuSP where activities require only one resource unit. In the considered context, electric power overheads must be closely managed. And knowing that the power consumption depends mainly on the activity of the foundry, we have to integrate these energy features in the production planning and scheduling of the melting facility.

In the application context, each operation has to be processed inside its time window by one furnace to be selected among a set of m equivalent furnaces. Once this assignment is done, operations assigned to the same furnace must be sequenced. On the other hand, each operation needs a predefined electrical energy amount E i . The power of each furnace can be adjusted at each time period according to a minimal and maximal value P min and P max . The power used by all furnaces at a given time period cannot exceed a global threshold P .

Hence the problem corresponds to the conjunction of a CuSP (for the parallel machine side) with B = m and b i = 1 for all operations i, and an EnSP (for the electric power side) with

W i = E i , B = P , b min i = P min , b max i = P max .
In a constraint programming framework, both subproblems can be considered separately as global constraints to perform feasibility tests and time-bound adjustments through energy reasoning. In Section 3, we show through a short literature review that feasibility tests and time-bound adjustments for the EnSP cannot be directly found in previous work. In Section 4, we recall the (standard) energy reasoning for the CuSP. In Section 5, we propose an extension of the energy reasoning for the EnSP.

Related work

In Section 4, we present the standard energy reasoning consisting in feasibility tests and adjustment rules for the CuSP [START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF]. Many variants or extensions of the CuSP have been considered, for which feasibility tests and adjustment rules have been issued. However, we show hereafter that none of these variants correspond to the EnSP.

Clearly the CuSP cannot be used to model the EnSP since activities are not necessarily of rectangular shape (see Section 4). In fact, the EnSP can be defined as a relaxation of the (continuous) CuSP. Indeed, we obtain the CuSP by setting b min

interval [r i , t] it must hold t τ =ri b iτ ≤ b i .(t -r i ).
We do not have such regularity constraints in the EnSP, so the partially elastic CuSP and the EnSP are not comparable in terms of complexity.

Another related extension of the CuSP has been proposed in [START_REF] Poder | Computing a lower approximation of the compulsory part of a task with varying duration and varying resource consumption[END_REF], aiming at considering an activity as a sequence of consecutive subtasks such that the resource consumption of each subtask is given by a function of the subtask duration. In our case the consumption of an activity at a time period t is a decision variable.

In the discrete time-resource tradeoff model [START_REF] Ranjbar | A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling[END_REF], the duration of each activity is not predetermined, but changes as a discrete non-increasing function of the amount of renewable resources assigned to it. However, the activities still have a rectangular shape.

The classical energy reasoning for the CuSP

In the energy reasoning for scheduling, the idea is to propose a smart way for simultaneously considering time and resource constraints in a unique reasoning. In that context, the energy is generically defined as the product of a time duration by a resource quantity. As an illustration, we can say that the problem of scheduling n activities of duration p i, i=1..n in an amount b i, i=1..n using a given resource available in a constant amount B over a time horizon ∆ of duration p ∆ is isomorphic to the placement problem of n rectangles of surface area p i .b i , i = 1, . . . , n, in a rectangle of surface area B.p ∆ .

To present the energy reasoning, one must consider a working time interval, an available energy and a total consumed energy over this interval.

Let [t 1 , t 2 ] be a reference time interval. Bounds of the interval are arbitrarily chosen but they also can be fixed to particular times. Over [t 1 , t 2 ] and for a resource of capacity B, the available energy is defined as B.(t 2t 1 ). We denote by w(i, t 1 , t 2 ) the consumption of activity i (i.e. how long i uses the resource) over [t 1 , t 2 ]. Two cases must be distinguished:

(1) [st i , f t i ] ∩ [t 1 , t 2 ] = ∅ ⇒ w(i, t 1 , t 2 ) = 0; (2) [st i , f t i ] ∩ [t 1 , t 2 ] = ∅ ⇒ w(i, t 1 , t 2 ) = b i . (min(f t i , t 2 ) -max(st i , t 1 )).
In Figure 2, striped areas represent the consumption of each activity from 1 to 5 between t 1 and t 2 .

One is usually especially interested in computing the lower and upper bounds of the consumption: for the consumption of activity i over interval [t 1 , t 2 ], we might derive from above equations the minimum and the maximum consumptions. The relevant notion for our purpose is obviously the minimum consumption, also called the mandatory (or compulsory) consumption: when trying to check whether i before j is feasible, we intend to take into account that another activity k will necessarily consume the resource, between st i and f t j , for at least some time T . Therefore we will not consider anymore the maximum consumption in the remainder of the paper.

The mandatory consumption of an activity i is denoted by w(i, t 1 , t 2 ). To compute it, the activity has to be shifted to its left and right utmost positions on its time window [r i , d i ], retaining the minimum value of all intersections between such positions and the reference interval. One then gets:

• the left-shifted consumption:

w L (i, t 1 , t 2 ) = b i . max{0, min(p i , t 2 -t 1 , r i + p i -t 1 )} • the right-shifted consumption: w R (i, t 1 , t 2 ) = b i . max{0, min(p i , t 2 -t 1 , t 2 -d i + p i )}
The mandatory consumption of activity i is then:

w(i, t 1 , t 2 ) = min{w L (i, t 1 , t 2 ), w R (i, t 1 , t 2 )} = b i . max {0, min(p i , t 2 -t 1 , r i + p i -t 1 , t 2 -d i + p i )}
From this definition, it yields a satisfiability test (global inconsistency rule) which includes total mandatory consumption over the set of activities A:

Property 1 CuSP feasibility test If ∃ [t 1 , t 2 ] s.t. i∈A w(i, t 1 , t 2 ) > B.(t 2 -t 1 )
, then no feasible solution exists for the CuSP.

In [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF], the set of relevant intervals [t 1 , t 2 ] is characterized and an O(n 2 ) algorithm is provided to perform the feasibility tests over all these intervals.

From this satisfiability test, we can now propose local consistency rules to derive time-window adjustments for a specified task. Let SL(i, t 1 , t 2 ) = B.(t 2t 1 )-j∈A\{i} w(j, t 1 , t 2 ) be the maximum available energy (i.e. the slack) for processing i on [t 1 , t 2 ].

Property 2 CuSP time-bound adjustments

Release date adjustment. If an activity i verifies: ∃ [t 1 , t 2 ] s.t. w L (i, t 1 , t 2 ) > SL(i, t 1 , t 2 ), then a valid lower bound of the completion time of i can be deduced and then impacts its release date as follows:

r i ← max{r i , ⌈t 2 -SL(i, t 1 , t 2 )/b i ⌉}.
Deadline adjustment. Symetrically, if an activity i verifies: ∃ [t 1 , t 2 ] s.t. w R (i, t 1 , t 2 ) > SL(i, t 1 , t 2 ), then a valid upper bound of the start time of i can be deduced and then impacts its deadline as follows:

d i ← min{d i , ⌊t 1 + SL(i, t 1 , t 2 )/b i ⌋}.
In [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF], an O(n 3 ) algorithm is provided to perform all the time-bound adjustments over the relevant intervals.

Energy reasoning for the EnSP

A first basic feasibility rule is to check whether there is enough time in each activity time window to bring the energy it requires when the maximum power is allocated to the activity.

Namely, this basic feasibility test can be written as follows: In what follows we consider this condition is fulfilled for each activity. To extend the energy reasoning, the basic question to answer is, given an interval [t 1 , t 2 ], what is the mandatory consumption w(i, t 1 , t 2 ) of each activity i ? Obviously if r i ≥ t 2 or d i ≤ t 1 , w(i, t 1 , t 2 ) = 0. Let us consider now that r i < t 2 and d i > t 1 . As for the standard energy reasoning, the mandatory consumption of each activity i in when the activity starts at its release date or when it ends by its due date. When r i < t 2 , the relevant cases are displayed in Figure 3.

[t 1 , t 2 ] is attained either b b b min i b max i r i t 1 t 1 t 2 r i b max i b min i t b b min i b max i r i t 1 b min i t 1 t 2 r i b max i t 2 t b b min i b max i r i t 1 t 2 t t b b min i b max i r i t 1 b min i t 1 t 2 r i b max i t 2 t b b min i b max i r i t 1 t 2 t t t 1 t 2 r i b max i b min i d i d i d i d i
To compute w(i, t 1 , t 2 ) we need to compute the maximum energy w -(i, t 1 ) consumed by i before t 1 , as well as the maximum energy w + (i, t 2 ) consumed by i after t 2 . We have

w -(i, t 1 ) = min {W i , max (0, b max i .(t 1 -r i ))} w + (i, t 2 ) = min {W i , max (0, b max i .(d i -t 2 ))} It follows that the minimal energy consumption of i inside [t 1 , t 2 ] verifies w(i, t 1 , t 2 ) ≥ v where v = min{W i -w - i (i, t 1 ), W i -w + i (i, t 2 ), b min i .(t 2 -t 1 )} or equivalently: v = min{W i -min(W i , b max i . max(0, t 1 -r i , d i -t 2 )), b min i .(t 2 -t 1 )}
Because of the minimal resource requirement b min i , we cannot have w(i, t 1 , t 2 ) < b min i if w(i, t 1 , t 2 ) > 0. Futhermore the required work W i has to be performed inside the time window [r i , d i ]. So in the case where it is necessary to consume b min i .(t 2t 1 ) inside the interval, we have to check whether consuming the maximal energy outside the interval is sufficient to bring the required energy W i . The case where b min i .(t 2t 1 ) is not a sufficient energy amount because of time window tightness is displayed at the right bottom of Figure 3. Hence we set:

w(i, t 1 , t 2 ) = 0 if v = 0 and w(i, t 1 , t 2 ) = max(b min i , v, W i -w - i (i, t 1 ) -w + i (i, t 2 )) otherwise.
This yields the following feasibility test.

x = min{W i -min(W i , b max i . max(0, t 1 -r i )), b min i .(t 2 -t 1 )}
and, we have:

w L (i, t 1 , t 2 ) = 0 if x = 0 and w L (i, t 1 , t 2 ) = max(b min i , x, W i -w - i (i, t 1 ) -w + i (i, t 2 )) otherwise.
Symmetrically, consider w R (i, t 1 , t2) the minimal energy consumption of i in [t 1 , t 2 ] when i is right shifted (i.e. f t i = d i ). We have w L (i, t 1 , t 2 ) ≥ y where

y = min{W i -w + i (i, t 2 ), b min i .(t 2 -t 1 )}
or equivalently :

y = min{W i -min(W i , b max i . max(0, d i -t 2 )), b min i .(t 2 -t 1 )} and, we have w R (i, t 1 , t 2 ) = 0 if y = 0 and w R (i, t 1 , t 2 ) = max(b min i , y, W i -w - i (i, t 1 )-w + i (i, t 2 )) otherwise.
We obtain the following time-bound adjustments:

Property
d i ← min{d i , ⌊t 1 + SL(i, t 1 , t 2 )/b min i ⌋}.
As the EnSP admits the CuSP as special case, it is a priori difficult to enumerate the intervals to be considered. Indeed, from [START_REF] Baptiste | Satisfiability tests and time-bound adjustments for cumulative scheduling problems[END_REF] we know that a part of the relevant intervals for the CuSP is such that t 1 = r j + p j and/or t 2 = d jp j for some activity j. For the EnSP, except when b min We can illustrate the adjustments performed on the Figure 1 example. Consider interval [t 1 , t 2 ] with t 1 = 2 and t 2 = 5. We have w

(1, t 1 , t 2 ) = w L (1, t 1 , t 2 ) = 2, w(2, t 1 , t 2 ) = w R (3, t 1 , t 2 ) = 7 and w(3, t 1 , t 2 ) = w L (3, t 1 , t 2 ) = w R (3, t 1 , t 2 ) = 6.
Note the configuration displayed in Figure 1 actually corresponds to the minimal consumption of the three activities in [t 1 , t 2 ]. Consider the case where activity 1 is right shifted. We have w R (1, t 1 , t 2 ) = 7 (same configuration as the one displayed for activity 2). Since w(3, t 1 , t 2 ) + w(2, t 1 , t 2 ) = 13 the slack for activity 1 in [t 1 , t 2 ] is SL(1, t 1 , t 2 ) = 15 -13 = 2. Since w R (1, t 1 , t 2 ) > SL(1, t 1 , t 2 ), the deadline of activity 1 can be updated according to property 5 by setting d 1 ← t 1 +2/1 = 4.

Dominance rules for the EnSP

The following dominance rules can be established for the EnSP.

Property 6 Active schedules

Active schedules are dominant for the EnSP.

Consider a solution S to the EnSP such that there is an activity i starting at time st i and a time period t < st i such that there is a feasible solution S ′ setting st i = t without changing the schedule of other activities. The search space can be obviously reduced to the set of solutions for which no such property holds.

Property 7 Power change

Schedules for which, for any activity i, changes in the allocated power only occur on activity release dates or completion times, are dominant.

Consider a feasible solution S to an EnSP instance such that a power change occurs at a time t which does not verify the above property and such that t is maximal. Simple arguments can show that the power change can be postponed while keeping the solution feasible, which contradicts the maximality of t.

Branching scheme

A simple branching scheme based on time incrementation can be derived from the dominance rules presented in Section 6. Each node corresponds to a decision time point initially set to t = min i∈A r i . For each activity the required energy W i is progressively decreased and all activities are scheduled when W i = 0 for all activities. At each node, associated with a decision time t, activities are partionned into the following subsets. The started activities are such that the decision to start the activity has been taken at some ancestor node (at a time point t ′ < t) but no decision has been taken yet for the current decision point and W i > 0. The completed activities are such that f t i ≤ t and W i = 0. The available activities are such that r i ≤ t but no start decision has been taken yet for these activities. The processed activities are such that the decision to process the activity at time t with some resource amount b has already been taken and W i > 0. The unavailable activities verify r i > t and W i > 0. The postponed activities are those selected for being scheduled later (see branching scheme below).

At each node an activity either started or available is selected for being included in the processed set (or in the postponed set for the available activities). The activity i * with the smallest due date is selected first and, in case of tie, the activity with the most remaining work (W i * ) is selected. Let Q and E denote the set of started and processed activities, respectively. If activities, corresponds to postponing activity i * to a decision point t ′ > t such that t ′ is either equal to the minimum between the smallest possible completion time of an activity of E and the smallest release date of unavailable activities, strictly greater than t. This time point is unknown at this step since set E is under construction, so the activities are just marked as postponed without any other update.

If no activity can be selected for being scheduled at t, we have different reasons. If all activities are in the completed set, the search succeeds. If all activities are either processed, postponed, unavailable or available but without enough resource capacity, the search must continue from the next decision time point set to the smallest release date or completion time of processed activities greater than t. At this time we may check whether the new decision point is still compatible with the due date of the available activities and if the schedule is active. Actually we just check whether the schedule is still semi-active by verifying that no postponed activity could actually start at t. If one due date cannot be satisfied or if the schedule is no more semi-active, a failure occurs and the node is pruned. Otherwise decision time point is updated. The processed activities are transferred either to the completed set or to the started set. The postponed activities are moved to the available set. The unavailable activities such that r i ≤ t are moved to the available set. The activity selection process starts again and the process is iterated until an activity is selected for being processed or a failure occurs.

We illustrate the branching process on the Figure 1 problem instance. For the root node where t = 0, activity 1 is in the available set while activities 2 and 3 are in the unavailable set. We branch to the second node by selecting activity 1 for being scheduled at maximal power. Activity 1 is included in the processed set. At time t = 0 no other activity is available. Time t is set of the next decision point t = 2. Activities 2 and 3 are included in the available set and activity 1 is transferred to the started set. The third node selects activity 3 with power b = 2 as the activity with the smallest due date for being inserted in the processed set. Activities 1 and 2 can both be processed at time 2 and have the same due date but activity 2 has the most remaining work. So the fourth node selects activity 2 for being processed at time t = 2 with the maximal available power, taking account of processed and started activities, equal to b = 2. For the fifth node, activity 1 can now be processed at time t = 2 with its minimal power b = 1. No activity is available anymore at time t = 2, so we proceed to the next time point corresponding with the completion time of activity 1 at time t = 4 and activities 2 and 3 are now both in the started set while 1 is put into the completed set. For the seventh node, activity 3 is still selected with power b = 2 as it has the smallest due date. Then, the eighth node selects activity 2 with the maximal available power b = 3. Since all activities are in the processed set, the time point is increased to the completion time t = 5 of activity 3 and activity 2 is included in the started set. For the ninth node, activity 2 is selected with the maximal power b = 5 and completed at time t = 6. For this example no backtracking has been necessary.

Computational experiments

In this section we illustrate on a few randomly generated problem instances the interest of the proposed energy reasoning. In Table 1, we provide the results of two tree search methods, the first one with energy reasoning feasibility tests and time-bound adjustments applied at each node, and the second one without these tests and adjustments. Five instance EnSP1,. . . ,EnSP5 have been selected as illustrative ones. The first four instances have 25 activities while the last one comprises 30 activities. The solution found, the CPU time in seconds, and the number of nodes in the search tree are provided for each pair instance / method. The available power has been set to B = 10. The energy requirements and time windows have been randomly generated to obtain infeasible and feasible instances. For the 25 activity instances, the results show the superiority of the approach incorporating energy reasoning, both for number of nodes and CPU time. For infeasible instance EnSP1, the energy reasoning proves infeasibility at the root node, while the branching scheme cannot reach this result after 10 6 nodes ("NA" stands for 'Not Available'). However, for infeasible instance EnSP5, the branching scheme incorporating energy reasoning obtains a significantly lower number of nodes but the required CPU time is much more important. This indicates that despite the quality of the adjustments, the algorithm complexity (O(n 3 )) is too big. Hence, in this case we may use energy reasoning only for a subset of nodes. Indeed, if we use it only at the root node (results displayed in parenthesis in Table 1), we still obtain 69350 nodes with a CPU time of 2 seconds, so incorporating energy reasoning becomes profitable again.

Conclusion

We presented the energy scheduling problem, an extension of the cumulative scheduling problem to represent energy requirements of activities. We showed this model is well-adapted to a parallel machine scheduling industrial context with electric power limitations. We proposed an extension of the standard energy reasoning scheme that was not covered by previous works on this subject. Finally we draw the scheme of a tree search method based on dominance rules. Computational experiments illustate the quality of energy reasoning adjustments and the trade-off that has to be found for their efficient use inside tree search.

2 Fig. 1 .

 21 Fig. 1. Solution of an EnSP

i = b max i =Fig. 2 .

 i2 Fig. 2. Consumption of five activities

Property 3

 3 EnSP basic feasibility test If, for an activity i, b max i .(d ir i ) < W i , the EnSP is infeasible.

Fig. 3 .

 3 Fig. 3. Different cases for left-shifted consumption wL(i, t1, t2)

  CuSP case), we have not a fixed activity duration but a set of possible durations from ⌈W j /b max j ⌉ to ⌈W j /b min j ⌉. For the sake of simplicity we restrict the considered intervals to O 1 × O 2 where O 1 = {r j |j ∈ A} and O 2 = {d j |j ∈ A}.

  i * ∈ Q, b i * = B -j∈Q\{i * } b min j -j∈E b jt denotes the available power for i at time t. If i * ∈ Q, the available power for i * is b i * = B -j∈Q b min j -j∈E b jt . If b i * > b min i * , a part of i can be scheduled at time t. A child node is generated for b ∈ [b min i * , min(b i * , b max i * )] corresponding to an allocation of power b i * t = b to i * at time t. An additional child node, only for available

  Property 4 EnSP feasibility test If ∃ [t 1 , t 2 ] s.t. i∈A w(i, t 1 , t 2 ) > B.(t 2t 1 ), then no feasible solution exists for the EnSP.As for the CuSP, let SL(i, t 1 , t 2 ) = B.(t 2t 1 ) -j∈A\{i} w(j, t 1 , t 2 ) denote the maximum available energy (i.e. the slack) for processing i on [t 1 , t 2 ]. We obtain bound adjustments considering the two extreme cases for an activity i.Consider w L (i, t 1 , t2) the minimal energy consumption of i in [t 1 , t 2 ] when i is left shifted (i.e. st i = r i ). We have w

L (i, t 1 , t 2 ) ≥ x where x = min{W iw - i (i, t 1 ), b min i .(t 2t 1 )}

or equivalently :

5

  EnSP time-bound adjustments Release date adjustment. If an activity i verifies: ∃ [t 1 , t 2 ] s.t. w L (i, t 1 , t 2 ) > SL(i, t 1 , t 2 ), then the release date can be updated as follows: r i ← max{r i , ⌈t 2 -SL(i, t 1 , t 2 )/b min

i ⌉}.

Deadline adjustment. Symetrically, if an activity i verifies

: ∃ [t 1 , t 2 ] s.t. w R (i, t 1 , t 2 ) > SL(i, t 1 , t 2 )

, then the deadline can be updated as follows:

Table 1

 1

	Compared results on EnSP instances
				results with energy reasoning	results without energy reasoning
	Instance n	B	Solution	CPU (s) #Nodes	Solution	CPU (s) #Nodes
	EnSP1	25 10 Infeasible 0	1	NA	NA	> 10 6
	EnSP2	25 10 Feasible	6	101970	Feasible	17	464933
	EnSP3	25 10 Feasible	13	212382	Feasible	16	443491
	EnSP4	25 10 Feasible	22	368264	Feasible	31	811607
	EnSP5	30 10 Infeasible 27(2)	69350(69350) Infeasible 4