Christophe Rapine
email: christophe.rapine@univ-lorraine.fr

Guillaume Goisque
email: guillaume.goisque@univ-lorraine.fr

Ayse Akbalik
email: ayse.akbalik@univ-lorraine.fr

Energy-aware lot sizing problem : Complexity analysis and exact algorithms

Keywords: Lot sizing problem, energy, capacitated parallel machines, polynomial time algorithm, complexity

come

Introduction

Energy-efficiency in production planning becomes more and more appealing for researchers and practitioners. According to Biel and Glock [START_REF] Biel | Systematic literature review of decision support models for energy-efficient production planning[END_REF], "In 2010, the industrial sector was responsible for 39.4% of the overall energy consumption and this latter largely originates from manufacturing industries." The same authors mention that the aim of energy-efficient production planning models is not only to take into account the classical metrics such as the minimization of overall cost or completion time, but also to consider energy-aware factors such as energy related constraints, energy cost or energy consumption minimization, etc. There is also a change in the consumers' behavior, with a higher sensitivity to the environmental impacts of the industrial activities (pollution, energy consumption, etc.). For couple of years, numerous companies have thus begun to rethink and optimize their production processes in order to produce at lower cost, but also more ecologically and with a lower energy consumption.

We consider in this paper a lot-sizing problem taking into account the energy consumption as a hard constraint, in a capacitated machines environment. In addition to a classical production capacity, dependent on the number of machines running in a given period (which is a decision variable in our problem), we consider a limit on the amount of energy that can be consumed in each period by the production system. The different activities responsible for consuming energy that we consider in this paper, include the start-up of the machines, the production of goods, and keeping the machines ready, either they do produce or are idle. The aim is to decide when and how much to produce, when and how many machines to turn on or to turn off, in order to minimize the total cost incurred over a time horizon of T periods, while respecting the amount of energy available in each period and satisfying the demand. We consider the deterministic version of the problem, that is, we assume that all the parameters and the demand to satisfy are known for each period of the time horizon. The cost of a planning includes a start-up cost to switch on the machines, a reservation cost to keep the machines ready for production, a joint setup cost, a unit production cost, and a unit holding cost to carry units in stock. We believe that the problem studied is in accordance with the context of energy aware production and environmental sustainability. We call this energy aware lot sizing problem energy-LSP in the rest of the paper.

Contributions of the paper. Problem energy-LSP in a parallel production system was first introduced by Rapine et al. [START_REF] Rapine | Capacity acquisition for the single-item lot sizing problem under energy constraints[END_REF]. They propose a very efficient O(T log T ) algorithm for a restricted version assuming that start-up costs are stationary and that only one activity (start-up or production) consumes energy. In this article we extend the model in different directions to render it more realistic : First, we consider time-varying cost parameters, including start-up costs but also non null joint production setup costs, to be paid in each period where production occurs, and reservation costs, to be paid for each machine kept ready to produce. Second, we consider that all activities may have a non negligible energy consumption. It means that, in each period, one has to arbitrate how the available amount of energy is to be shared between the start-up of machines, which increases the production capacity of the system, and the effective production of units. In addition, we also consider a reservation energy consumption, that represents the energy consumed by a machine that is kept on, whenever producing or not. Under this quite general framework, we establish that the problem is NP-hard if some energy parameters are time-varying, even on a single resource with non-null setup or reservation costs. In contrast, we show that the problem is polynomially solvable if all the energy parameters, that is, periodic amount of available energy, start-up, reservation and unit consumptions, are stationary. Our approach is based on dynamic programming and provides an O(M 6 T 6 ) exact algorithm for the most general case studied in this paper. To the best of our knowledge, there is no other theoretical studies on this integrated lot sizing and energy issues, except [START_REF] Rapine | Capacity acquisition for the single-item lot sizing problem under energy constraints[END_REF].

Organization of the paper. The paper is organized as follows. In Section 2, we present relevant studies in both lot sizing and energy-efficient production planning problems. The problem description is given in Section 3 via a mixed integer programming formulation for the general case. In Section 4, we establish that problem energy-LSP is NP-hard, even with null production and null holding costs. Then, several other complexity results are given for different restricted cases. In Section 5, we first give a polynomial time algorithm for the restricted version of the problem, with null setup cost, null reservation cost and null reservation energy consumption. Under stationary energy parameters, this algorithm solves the problem exactly in time complexity of O(M 5 T 4 ). In the same section, this algorithm is extended to solve energy-LSP with non-null reservation cost, joint setup cost and reservation energy consumption parameters, which results in a time complexity of O(M 6 T 6 ). We finally conclude in Section 6 with several perspectives.

Literature review

The problem studied in this article can be positioned at the intersection of the single-item dynamic lot sizing problem (LSP) and energy-efficient manufacturing. In this section, relevant studies published in both domains are presented, together with the very few studies at their intersection.

The single-item LSP aims to determine how much and in which periods to produce in order to satisfy a deterministic and discrete demand over a given time horizon, while minimizing the total production and storage costs. The reader can refer to Wagner and Whitin [START_REF] Wagner | Dynamic version of the economic lot size model[END_REF] for a seminal paper, and to Florian et al. [START_REF] Florian | Deterministic production planning: Algorithms and complexity[END_REF] and to Bitran and Yanasse [START_REF] Bitran | Computational complexity of the capacitated lot size problem[END_REF] for the first complexity analysis on the capacitated LSP. For more details on the different extensions of this extensively studied production planning problem, we refer to Brahimi et al. [START_REF] Brahimi | Single item lot sizing problems[END_REF], Pochet and Wolsey [START_REF] Pochet | Production Planning by Mixed Integer Programming[END_REF] and to Brahimi et al. [START_REF] Brahimi | Single-Item Dynamic Lot-Sizing Problems: An Updated Survey[END_REF]. In the literature, most of the existing problems in production planning focus on the minimization of production and holding costs. However, in order to respect the new environmental standards and energy consumption issues, more and more theoretical and practical applications integrate them within the optimization of the production planning (see [START_REF] Gahm | Energy-efficient scheduling in manufacturing companies: A review and research framework[END_REF] and [START_REF] Biel | Systematic literature review of decision support models for energy-efficient production planning[END_REF]).

The aim of this paper is to integrate the energy constraints into the lot sizing problem. In the related literature, some studies integrate explicitly the energy cost in the optimization problem (see Özdamar and Birbil [18], Uzel [START_REF] Uzel | A mathematical modeling approach to energy cost saving in a manufacturing plant[END_REF], Tang et al. [START_REF] Tang | A stochastic production planning problem with nonlinear cost[END_REF] and Ding et al. [START_REF] Ding | Parallel machine scheduling under time-of-use electricity prices: New models and optimization approaches[END_REF]), but they assume that the available energy is unlimited. We propose in this paper an approach considering a given limit on the energy available in each period, which hence also limits the quantity that can be produced. Notice that a limit on the amount of available energy is also considered by Artigues et al. [START_REF] Artigues | The energy scheduling problem: industrial case-study and constraint propagation techniques[END_REF], Nattaf et al. [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF], [START_REF] Nattaf | Energetic reasoning and mixed-integer linear programming for scheduling with a continuous resource and linear efficiency functions[END_REF], Ngueveu et al. [START_REF] Ngueveu | Scheduling under a nonreversible energy source: An application of piecewise linear bounding of non-linear demand/cost functions[END_REF] and Modos et al. [START_REF] Modos | Algorithms for robust production scheduling with energy consumption limits[END_REF] for scheduling problems, by Schultz et al. [START_REF] Schultz | An approach for energy-oriented production control using energy flexibility[END_REF] for a short term production control problem and by Masmoudi et al. [START_REF] Masmoudi | Lot-sizing in a multi-stage flow line production system with energy consideration[END_REF] for a single-item capacitated LSP. In [START_REF] Masmoudi | Lot-sizing in a multi-stage flow line production system with energy consideration[END_REF], the authors consider a flow-shop system with a maximum allowable energy level, as well as an electricity price in their objective function. The flow-shop system considered in [START_REF] Masmoudi | Lot-sizing in a multi-stage flow line production system with energy consideration[END_REF] makes the problem quite different than ours with deadlines to respect. Moreover, the authors propose heuristics to solve their problem, while we theoretically study our models, analyzing their complexity and proposing polynomial time exact algorithms. A very recent study from Giglio et al. [START_REF] Giglio | Integrated lot sizing and energy-efficient job shop scheduling problem in manufacturing/remanufacturing systems[END_REF] integrates energy consumption issues into the lot sizing and scheduling decisions in a multi-item, multi-machine job-shop environment, with additional backlogging and remanufacturing assumptions. The capacitated machines consume a certain amount of energy when being idle and when producing units, where a normal production mode and an accelerate production mode are distinguished. All the latter energy issues are modeled via costs of energy consumption into the objective function. Giglio et al. [START_REF] Giglio | Integrated lot sizing and energy-efficient job shop scheduling problem in manufacturing/remanufacturing systems[END_REF] propose a relax-and-fix heuristic to cope with this integrated problem.

There are also several papers dealing with industrial case studies on energy issues in production planning problems (see [START_REF] Artigues | The energy scheduling problem: industrial case-study and constraint propagation techniques[END_REF], [START_REF] Santos | Integrated pulp and paper mill planning and scheduling[END_REF], [START_REF] Waldemarsson | Including energy in supply chain planning at a pulp company[END_REF] and [START_REF] Zhao | Production planning optimization of an ethylene plant considering process operation and energy utilization[END_REF]). Those case studies provide us with a real motivation to integrate energy issues into the production planning problems. For instance, in Ozdamar and Birbil [START_REF] Özdamar | A hierarchical planning system for energy intensive production environments[END_REF], the authors provide some examples of energy-intensive industries, such as steel, tile and glassware industries, where, the energy expenditure represents the major component of the unit production cost. Tang et al. [START_REF] Tang | A stochastic production planning problem with nonlinear cost[END_REF] study a production planning problem for a hot rolling production process, where they try to minimize the energy consumption. Waldermarsson et al. [START_REF] Waldemarsson | Including energy in supply chain planning at a pulp company[END_REF] consider a pulp company, and they study an integrated supply chain planning taking energy issues into consideration. Zhao et al. [START_REF] Zhao | Production planning optimization of an ethylene plant considering process operation and energy utilization[END_REF] study the scheduling of parallel furnaces and energy distribution for real world ethylene plant. All the above cited case studies show the importance of taking into account energy cost and limitation within operational planning in manufacturing. The reader can be referred to Gahm et al. [START_REF] Gahm | Energy-efficient scheduling in manufacturing companies: A review and research framework[END_REF] for a recent review on energy-efficient scheduling issues in manufacturing, to Biel and Glock [START_REF] Biel | Systematic literature review of decision support models for energy-efficient production planning[END_REF] for a literature survey on the energy-efficient production planning, to May et al. [START_REF] May | Energy management in manufacturing: From literature review to a conceptual framework[END_REF] for a detailed literature review on the energy management in manufacturing and finally, to Schulze et al. [START_REF] Schulze | Energy management in industry -a systematic review of previous findings and an integrative conceptual framework[END_REF] for energy management issues in industry.

The majority of the papers published in the domain of energy-efficient production planning consists in energyefficient machine scheduling problems (see Biel and Glock [START_REF] Biel | Systematic literature review of decision support models for energy-efficient production planning[END_REF]). To the best of our knowledge, there are only a few studies in the literature coupling energy issues with discrete lot sizing problem: Masmoudi et al. [START_REF] Masmoudi | Lot-sizing in a multi-stage flow line production system with energy consideration[END_REF], Giglio et al. [START_REF] Giglio | Integrated lot sizing and energy-efficient job shop scheduling problem in manufacturing/remanufacturing systems[END_REF], that we have already discussed, and Rapine et al. [START_REF] Rapine | Capacity acquisition for the single-item lot sizing problem under energy constraints[END_REF]. As mentioned earlier, the problem studied in this paper consists in an extension of the energy lot sizing problem presented in Rapine et al. [START_REF] Rapine | Capacity acquisition for the single-item lot sizing problem under energy constraints[END_REF]. The main differences between the two models are, first, the fact that in this paper, several activities, such as the production of units, the start-up of machines, and the reservation of machines consume a non negligible amount of energy. Second, we consider a more general cost structure, including reservation cost, joint setup cost, and start-up costs, all allowed to be time-dependent in our model. Our resolution approach, based on dynamic programming, is also totally different from the algorithm presented in Rapine et al. [START_REF] Rapine | Capacity acquisition for the single-item lot sizing problem under energy constraints[END_REF].

Problem formulation

The system we study is constituted of M parallel, identical and capacitated machines that can be started at any period, respecting the energy restriction. Each machine has a constant capacity of U. We say that a machine is running if it is not turned off. That is, a running machine may either be actually producing units, or simply idle, ready to produce. We assume through the paper that the amount of energy available in each period is stationary, and we denoted it by E. This available energy amount is shared between various activities, such as, starting the machines, keeping the machines ready for production, and producing units.

Note that, in our problem, the capacity limit related to the available energy amount is a hard constraint, whereas the capacity limit related to the capacitated machines is similar to a soft capacity constraint, since the actual production capacity depends on the number of running machines. In particular, we can take the decision to switch on more machines, if less than M machines are currently running, in order to increase the available production capacity. We denote by m t the number of machines that are running, and thus available for production, during period t. Initially we assume that all the machines are turned off, that is, m 0 = 0. In each period t, we have to decide :

• How many machines m t to have ready for production (that is, how many machines to turn on/off at the beginning of the period)

• Which quantity x t to produce to satisfy the demand or/and to store in inventory.

The aim is to minimize the total cost over a finite horizon of length T to satisfy a deterministic demand d t in each period t, without backlogging, while respecting the production capacity and the limit on the amount of energy available. The cost of a production planning includes the cost to start the machines, the cost to reserve the machines to be ready to produce, the cost to produce units with a fixed (joint setup cost) and a variable component (unit production cost), and the cost to carry units in stock. The cost to keep a machine ready is called a reservation cost, in reference to the article [START_REF] Karmarkar | The Dynamic Lot-Sizing Problem with Startup and Reservation Costs[END_REF] of Karmarkar et al where it was first introduced. By analogy, the energy required to keep a machine ready for production is called the reservation energy consumption. The parameters used are listed below :

d t :
demand in period t K t : joint setup cost for producing in period t, whatever the number of machines used c t : unit production cost in period t h t :

unit holding cost to carry a unit from period t to t + 1 f t (k) : cost to turn on k machines on period t. We call f the start-up cost function r t : reservation cost, incurred by each running machine during period t, whether it actually produces or not U : capacity of a machine M : number of machines in the system E : amount of energy available in each period p t : unit energy consumption to produce one unit in period t w t : energy consumption to start a machine in period t g t : reservation energy consumption (energy consumed by a machine running during period t)

Decision variables are as follows:

x t : quantity produced in period t y t : binary joint setup variable in period t, equal to 1 if a production occurs s t :

quantity in stock at the end of t m t : the number of machines running in period t m + t : the number of machines turned on at the beginning of period t We require the start-up cost function f t (k) to be non-decreasing with respect to the number k of machines turned on, with f t (0) = 0, for each period t. This assumption seems quite realistic and easily verified in practice. Notice that functions f t may differ from one period to another. The most common example of start-up cost is a strictly linear function, where a unit cost f t (1) is incurred for each machine turned on in period t. However, our model can capture more general situations, for instance if we have an economy of scale in starting several machines in the same period, or, on the contrary, if each additional machine is more and more expensive to start, as it may require working overtime. We assume through the paper that production costs follow non-speculative motives, also called Wagner-Whitin (WW) cost structure. Non-speculative motives imply that for any period t, we have c t + h t ≥ c t+1 . In other words, producing and storing one unit in a period t has a higher cost than producing it later in period t + 1. Under WW costs, it is dominant to produce as late as possible. Notice that, wlog, we can consider that the holding costs are null, by substituting unit production costs c t with ct = c t + T u=t h u . This transformation is possible due to the linearity of the holding costs. For the details, see [START_REF] Pochet | Production Planning by Mixed Integer Programming[END_REF]. WW cost assumption implies that ct ≥ ct+1 holds for all periods, in other words, modified unit production costs ct are non-increasing over time. The formulation of the problem can be written as follows :

min T t=1 ( f t (m + t ) + c t x t + h t s t + r t m t + K t y t ) s.t. s t-1 + x t = s t + d t ∀t ∈ {1..T } (1)
x t ≤ Um t ∀t ∈ {1..T } (2)

px t + wm + t + gm t ≤ E ∀t ∈ {1..T } (3) m + t ≥ m t -m t-1 ∀t ∈ {1..T } (4) m t ≤ M ∀t ∈ {1..T } (5)
x t ≤ U My t ∀t ∈ {1..T } (6)

s t ≥ 0, x t ≥ 0, y t ∈ {0, 1}, m + t ∈ Z + , m ∈ Z + ∀t ∈ {1..T } (7)
Constraints (1) describe the classical material balance between the produced, stored and satisfied units. In each period t the production is limited by 2 constraints: production capacity constraints (2) and energy restriction constraints (3). Constraints (4) ensure that the number m + t of machines switched on at the beginning of each period t is sufficient to have m t machine running during the period. Notice that, since the start-up function is non-decreasing, in an optimal solution we have m + t = max{m tm t-1 , 0}. Constraints [START_REF] Brahimi | Single-Item Dynamic Lot-Sizing Problems: An Updated Survey[END_REF] stipulate that the number of machines running can not exceed the total number of machines of the system. Finally, Constraints (6) force variable y t to be equal to 1 if the quantity x t produced in period t is positive. Notice that U M is an upper bound of the quantity that can be produced in any period. The feasibility domains are given by Constraints [START_REF] Klein | Deterministic production planning with concave costs and capacity constraints[END_REF].

Complexity results

In this section we establish that energy-LSP is NP-hard, even under stringent conditions. Namely, in 4.1, we show that if the energy consumption w to start a machine, the unit energy consumption p to produce and the start-up cost function f are the only non-null parameters, the problem is already NP-hard if the number M of machines in the system is part of the inputs. Of course, allowing the other parameters to be non-null cannot render the problem easier. In fact, we show in the following that if either the joint setup cost, or the reservation cost, or the reservation energy consumption is non-null, then the problem is NP-hard even if we have a single machine in the system.

Null joint setup cost, null reservation cost, null reservation energy consumption case

We consider the case with null joint setup cost, null reservation cost, and null reservation energy consumption, that is, K = r = g = 0. Notice that in this case there is no incentive to switch off a machine : in an optimal solution, once a machine is turned on, it stays running till the end of the planning horizon. Hence, m t , the number of machines running in period t, is non-decreasing with time. We call this particular case of energy-LSP problem energy-LSP-no-switch-off. The mixed-integer formulation given in the previous section can be simplified for problem energy-LSP-no-switch-off, to obtain the following formulation :

min T t=1 ( f t (m + t ) + c t x t + h t s t ) s.t. s t-1 + x t = s t + d t ∀t ∈ {1..T } (1)
x t ≤ Um t ∀t ∈ {1..T } (2)

p t x t + w t m + t ≤ E ∀t ∈ {1..T } (3) m + t = m t -m t-1 ∀t ∈ {1..T } (4) m t ≤ M ∀t ∈ {1..T } (5) s t ≥ 0, x t ≥ 0, m t ∈ Z + , m + t ∈ Z + ∀t ∈ {1..T } (6)
In this section, we establish that energy-LSP-no-switch-off is computationally difficult if the unit energy consumption parameter p t is time-dependent, even if the other energy parameters are stationary and most of the cost parameters are null.

Theorem 1. If the number M of machines is part of the instance, problem energy-LSP-no-switch-off is NP-hard even with null production cost (c = 0) and null holding cost (h = 0), and with stationary energy parameter w.

Proof. The reduction is made from the Partition problem. Recall that an instance of Partition is constituted of a list of n integers a i . Denoting by A the quantity i a i /2, it is asked whether there exists a subset S ⊆ {1, . . . , n} such that i∈S a i = A. For short we denote by a(S ) the sum of the a i 's for i ∈ S . Notice that we can restrict to instances such that all the a i are lower than A, otherwise the answer is trivial. We transform an instance I of Partition into an instance τ(I) of energy-LSP-no-switch-off as follows :

• We have n + 2 periods, indexed from 0 to T = n + 1. The only positive demand appears in the last period, with d T = nA

• The capacity of a machine is U = A. The number of machines is equal to M = n. Unit production and holding costs are null.

• The amount of energy available in each period is E = Π i=1,n (Aa i ).

• The amount of energy required to start a machine is w = E. Notice that at most one machine can be switched on in each period.

• The amount of energy required to produce one unit at period t is equal respectively to : p 0 = 1, p t = E/(Aa t ) for t = 1, . . . , n, and p T = 0. Notice that for t = 1, . . . , n, due to the limited amount E of energy, at most (Aa t ) units can be produced.

• The start-up cost function is linear, with f 0 (1) = 0, f t (1) = a t for t = 1, . . . , n, and f T (1) = A + 1

• It is asked whether a solution of cost at most A exists.

The following table gives an overview of the time-dependent parameters p t and f t for the instance τ(I) :

Period t 0 1, . . . , n T p t 1 E/(A -a t ) 0 f t (1) 0 a t A + 1
We show that τ(I) is positive if and only if instance I is positive. Consider any planning x, and define S as the subset of periods of {1, . . . , n} where a machine is started. Since the energy needed to start a machine is w = E, at most one machine can be started in each period, and in this case nothing can be produced, except for the last period T . Notice that starting a machine at period 0 is clearly dominant, and starting a machine at period T is prohibited for a planning of cost at most A. Hence, the number of machines available to produce at the last period is equal to 1 + |S |. Let us denote by X the cumulative production of periods 0, . . . , n, and let S = {1, . . . , n}\S . Notice that a production before the last period can only occur in periods of S . In these periods, at least one machine is on (the one started in period 0). Hence, production is limited by the amount E of energy available. For the planning to be feasible, we must have X + x T ≥ d T = nA. We have :

• X = i∈ S x i ≤ i∈ S (A -a i ) = | S |A -a( S ). Hence, we have X ≤ (n -|S |)A + (a(S ) -2A) • x T ≤ (1 + |S |)A since exactly 1 + |S |
machines are running during the last period As a result, on one hand, for a planning to be feasible, the inequality (n -1)A + a(S ) ≥ nA must hold, which implies that a(S ) ≥ A. On the other hand, for a planning to cost at most A, we must have a(S ) ≤ A, since starting a machine in a period i ∈ S incurs a cost f i (1) = a i . We can conclude that instance I is positive, as S defines a partition of value A. Conversely, if S is a partition of value A, it is easy to check that a planning starting a machine at period 0 and at each period of S , is feasible and costs at most A.

In the following, we show that problem energy-LSP is NP-hard even on a single machine, as soon as one of the parameters r t , K t or g t is not null.

Non-null reservation cost case

We consider now that we have a non-null reservation cost. For each machine running during period t, a cost r t is to be paid, whether it produces or not. The costs incurred at a given period t where a quantity x t is produced in the system with m t machines running and m + t machines turned on at the beginning of the period, are now equal to f t (m + t ) + c t x t + h t s t + r t m t , where s t is the stock level at the end of the period. Karmarkar et al. [START_REF] Karmarkar | The Dynamic Lot-Sizing Problem with Startup and Reservation Costs[END_REF] proposed an O(T 2 ) time algorithm for a special case of our problem, considering a single uncapacitated machine and without energy consideration. Next theorem establishes that problem energy-LSP with reservation costs is NP-hard even for a single machine. This result strengthens Theorem 1 where the number M of machines is part of the inputs.

Theorem 2. Problem energy-LSP with reservation costs is NP-hard, even for a single machine and null start-up energy consumption (w = 0), null joint setup cost (K = 0) and null reservation energy consumption (g = 0).

Proof. The reduction is made from the capacitated lot-sizing problem (CLSP), which has been shown to be NP-hard by Florian et al. [START_REF] Florian | Deterministic production planning: Algorithms and complexity[END_REF]. In a CLSP instance, the amount that can be produced in each period is limited by a capacity C t . The authors consider a setup cost K t to be paid if a positive quantity is produced in period t. Let c t , h t and d t be the unit production cost, unit holding cost and the demand of CLSP instance I , respectively, on a time horizon of T periods. It is asked whether a feasible schedule of total cost at most Z exists. The complexity proof of Florian et al. [START_REF] Florian | Deterministic production planning: Algorithms and complexity[END_REF] allows us to assume that h t = 0 and that the c t are non-increasing, that is, they obey a non-speculative cost structure. We can also restrict ourselves to the instance with non null capacities. We transform instance I of CLSP into an instance I of energy-LSP as follows :

• We have T = 2T periods, indexed from 1 to T .

• We have a single machine of stationary capacity U = max t C t .

• The amount of energy available in each period is E = Π t=1,...,T C t

• The amount of energy required to start a machine is null, w = 0

• The amount of energy required to keep a machine ready is null, g = 0

• The joint setup cost is null, K = 0 • It is asked if a feasible planning of cost at most Z exists
In the instance I of energy-LSP, we distinguish between odd and even periods. We set the value of the different parameters as follows :

t d t f t c t h t p t r t 2t -1 d t K t c t 0 E/C t 0 2t 0 0 0 0 0 Z + 1
Notice that in each odd period 2t -1, the production is limited by E/p t = C t ≤ U due to the limited amount of energy available. Basically, an odd period t = 2t -1 in instance I plays the role of period t in instance I , whereas even periods force to shut-down the machine, since the reservation cost r t in these periods exceeds Z. It is immediate to check that I is positive if and only if instance I is positive.

Non-null reservation energy consumption case

We consider that a machine that is not turned off consumes some energy even if it does not produce. This reservation energy consumption parameter reflects practical situation where a non-negligible amount of energy is required to keep a machine ready or on standby, for instance to maintain the temperature of a furnace. It involves that in each period, one has now to arbitrate how to share the available amount E of energy between 3 activities, namely the start of machines, the effective production and keeping the machines ready, see the energy constraint (3) in the formulation given in Section 3. Again, the problem becomes NP-hard on a single machine when considering reservation energy consumption : Theorem 3. Problem energy-LSP with reservation energy consumption is NP-hard, even for a single machine and null start-up energy consumption (w = 0), null reservation cost (r = 0) and null joint setup cost (K = 0). We can use the same reduction as in the proof of Theorem 2. In order to force the shut-down of the machine during the even periods we simply set the reservation energy consumption parameter g t equal to E + 1, that is, exceeding the amount of available energy.

Non-null joint setup costs

In lot-sizing literature, it is common to consider that a positive production at a period incurs a setup cost, representing typically the efforts and materials required to prepare the machines. We assume here a joint setup cost for the system : a positive production at a period t incurs a fixed setup cost K t , whatever the amount produced and the number of running machines. Hence, if x t > 0, the costs to be paid in period t are equal to f t (m + t ) + c t x t + h t s t + K t . Otherwise, if no production takes place, the costs reduce to h t s t . We have the following result : Theorem 4. Problem energy-LSP with a joint setup cost is NP-hard, even on a single machine with null start-up energy consumption (w = 0), null start-up cost ( f = 0), null reservation cost (r = 0) and null reservation energy consumption (g = 0).

Proof. Once again, the reduction is made from the capacitated lot-sizing problem. Using the same notations as in the proof of Theorem 2, instance I of CLSP is transformed into an instance I of energy-LSP as follows :

• We have T = T periods, indexed from 1 to T .

• We have a single machine of stationary capacity U = max t C t .

• The amount of energy available in each period is E = Π t=1,...,T C t • The amount of energy required to start the machine is null, w = 0

• The cost to start the machine is null, f = 0 • The reservation cost is null, r = 0 • the reservation energy consumption is null, g = 0 • The unit energy consumption is p t = E/C t
• The setup costs are identical to the setup costs of instance I , K t = K t Notice that, in instance I of energy-LSP, the quantity x t that can be produced in period t is limited by min{U, E/p t } = C t . It results that instance I is positive if and only if instance I of CLSP is positive. [START_REF] Bitran | Computational complexity of the capacitated lot size problem[END_REF] establish other NP-hardness results for different variants of CLSP. In particular the authors show that even with null holding and null unit production costs (and hence obeying non-speculative motives), problem CLSP remains NP-hard when the setup costs and the production capacities are both non-increasing or both nondecreasing over time. With the previous transformation, this result immediately translates to energy-LSP : Problem energy-LSP is NP-hard even in the special case of null holding and null unit production costs, if joint setup costs are non-increasing and unit energy consumption are non-decreasing, or vice-versa.

Bitran and Yanasse

Polynomial time algorithms

In this section, we show that problem energy-LSP is polynomially solvable when all the energy parameters are stationary over time. We think that this particular case is particularly relevant in practice. Notice that the cost parameters of the problem are allowed to be time-varying, under the restriction that the unit production and holding costs follow a non-speculative motive. In particular, the start-up cost function f t may differ from one period to another. Our approach is based on dynamic programming. We first present our approach for problem energy-LSP-no-switch-off, since the absence of reservation costs/energy consumption and null joint setup cost render the presentation of the algorithm easier, and allow to obtain a lower time complexity. We then extend our algorithm to problem energy-LSP in Section 5.2

A polynomial time algorithm for energy-LSP-no-switch-off

In this section we propose an exact O(M 5 T 4 ) time dynamic programming algorithm for energy-LSP-no-switch-off, see Section 4.1, when all the energy parameters are stationary over time. More precisely, we assume that, in each period, an amount E of energy is available, the unit energy consumption is equal to p and the energy consumption to start a machine is equal to w. Recall that in problem energy-LSP-no-switch-off, we have null reservation costs, null reservation energy consumptions and null joint setup costs. Considering the formulation of energy-LSP-no-switch-off given in Section 4.1, we call a period C-saturated if it saturates the production capacity constraint [START_REF] Biel | Systematic literature review of decision support models for energy-efficient production planning[END_REF], and E-saturated if it saturates the energy constraint (3). If a period t is C-saturated, by definition we have x t = m t U, whereas if t is E-saturated, we have x t = (Ewm + t )/p. Notice that both m t and m + t are decision variables of the problem. Following the classical terminology of lot-sizing problems, we also called a period a regeneration point if its entering inventory is null. Figure 1 illustrates the different definitions introduced in this paragraph, also used in Property 1 below : Property 1. In a dominant solution, each period t is either :

• a regeneration point, that is, s t-1 = 0

• or C-saturated, that is, x t = m t U

• or E-saturated, that is, px t + wm + t = E A period may eventually be at the same time a regeneration point, a C-saturated period and/or a E-saturated period.

Proof. Let us consider an optimal solution π and let t be the last period which complies with none of these possibilities. Consider one unit entering in stock in period t, and let t < t be the production period of this unit. Since both capacities are not reached (t being neither C-saturated nor E-saturated), and due to non-speculative motives (delaying a production is not more expensive), it is possible to postpone the production of this unit from period t to period t without increasing the cost of the solution or rendering it infeasible. This operation can be iterated until the stock vanishes at the beginning of period t or t becomes C-saturated or E-saturated. As a result, Property 1 becomes valid at period t and remains valid at the subsequent periods. The process can be repeated until Property 1 is valid at each period. The result follows.

In lot sizing domain, a very common problem-solving approach consists in decomposing the entire horizon into independent subplans (u, v), solving each subplan separately and then constructing the optimal solution via a shortest path algorithm. Recall that a subplan is defined as the set of periods between two consecutive regeneration points. By definition of a subplan (u, v), the entering stock level in periods u and v is null, and in any period t inside the subplan the stock level is positive. Very classically, since the pioneer study of Florian and Klein [START_REF] Klein | Deterministic production planning with concave costs and capacity constraints[END_REF], we compute the optimal cost of each possible subplan (u, v) using dynamic programming. However, this cost clearly depends on the number m u-1 of machines running at the beginning of period u, which depends on prior decisions, and on the number m v-1 u,0 v,0 (T+1,0) of machines running at the beginning of period v, which impact decisions on subsequent periods. For this reason, to render the cost of a subplan independent of the rest of the horizon, we fix the number of machines running at the beginning of the regeneration periods. More precisely, we compute the optimal cost of a policy for all pairs of periods (u, v), 1 ≤ u < v ≤ T + 1 and all pairs of integers (k, l), 0 ≤ k, l ≤ M, assuming that k machines, respectively l, are running at the beginning of period u, respectively v. Let us denote by S (u, k, v, l) the optimal cost of such a subplan. To compute the optimal cost of a policy, we consider the graph whose nodes are labeled by pairs (u, k), for 1 ≤ u ≤ T + 1 and 0 ≤ k ≤ M, and where an arc between a node (u, k) and a node (v, l) exists if u < v. The length of the arc ((u, k), (v, l)) is precisely S (u, k, v, l). We also add a leaf node S , which is a successor of each node (T + 1, k), for 0 ≤ k ≤ M. The length of any arc ((T + 1, k), S ) is null. The structure of the graph is depicted in Figure 2. Notice that this graph has O(T M) nodes. Since this graph is acyclic, the shortest path between root node (1, 0) and leaf node S can be computed in a time linear in the number of arcs, and thus quadratic in the number of nodes. The length of this shortest path corresponds to the cost of an optimal policy over the time horizon 1, . . . , T . As a consequence, assuming that all the costs S (u, k, v, l) are known, the optimal cost of a policy can be computed in time O(M 2 T 2 ). We detail now how the cost S (u, k, v, l) of a subplan can be determined using dynamic programming.

2,0 u,1 v,1 (T+1,1) u,2 v,2 (T+1,2) 2,2 S 1,0 2,1 S (u,0,v,0) S (u,2,v,2) S (u,0,v,2) 0 0 0 S (u,0,v,1)

Optimal cost of a subplan

Let us consider a subplan (u, v), such that k machines, respectively l, are running at the beginning of period u, respectively v, in an optimal solution. Let us denote by B = {u + 1, . . . , v -1} the periods inside the subplan. Due to Property 1, each of these periods is either C-saturated or E-saturated, or both. We denote by

B C = {t ∈ B | t is C-saturated} and by B E = {t ∈ B | t is E-saturated and not C-saturated}. It clearly defines a partition of set B. Let t ∈ {u + 1, v -1}
be a period inside the subplan. Assume that we know the value of the following quantities in an optimal planning:

• m: number of machines running at the beginning of period t, before one decides how many machines m + t to start in this period, that is, m = m t-1 .

• N C : the sum of the number of the machines running during each period of B C over the time horizon {t, . . . , v-1}: N C = i∈B C :i≥t m i

• N + E : the sum of the number of machines started over the periods of B E over the time horizon {t, . . . , v -1}:

N + E = i∈B E :i≥t m + i
• n E : the number of periods of B E over the time horizon {t, . . . , v -1}, that is,

n E = |B E ∩ {t, . . . , v -1}|
We claim that the entering stock level s t-1 of period t in an optimal planning is fixed for a given vector (t, m, N C , N + E , n E ). To see why, let us write the flow conservation on time horizon {t, . . . , v-1}. Let us define D i, j as the cumulative demand between periods i and j. We have:

D t,v-1 + s v-1 = s t-1 + v-1 i=t x i = s t-1 + i∈B C :i≥t x i + i∈B E :i≥t x i = s t-1 + i∈B C :i≥t m i U + i∈B E :i≥t (E -m + i w)/p = s t-1 + N C U + (n E E -N + E w)/p Since s v-1 =
0 as v is a regeneration period, we obtain that :

s t-1 = D t,v-1 -N C U -(n E E -N + E w)/p (8)
We denote by σ t-1 (v, m, N C , N + E , n E ) this quantity. Notice that σ t-1 can be computed in constant time if the cumulative demand D t,v-1 has been pre-computed. Vector (t, m, N C , N + E , n E ) represents the state vector of our dynamic programming algorithm. For fixed values v and l, we compute C (t, m, N C , N + E , n E ) the minimal cost of a policy on the time horizon {t, . . . , v-1}, such that the inventory level at the end of period v-1 is null and the number of running machines is equal to l. To express this cost, we distinguish between 2 cases, depending whether t belongs to

B C or B E . case 1, t ∈ B C : t is a C-saturated period
If m is the number of machines running during period t, by definition of a C-saturated period, the quantity produced in period t is equal to m U. In this case, (mm) + machines are started at the beginning of period t, incurring a cost of f ((mm) + ) and consuming an amount w(mm) + of energy. For the planning to be feasible, the energy constraint must be satisfied, which implies that pm U + w(mm) + ≤ E must hold. We must also have m U + s t-1 ≥ d t in order to satisfy the demand at period t. Let us denote by γ C (m, m ) the cost incurred at period t by having m machines running during period t, given that m machines were running at the beginning of this period, and that t is C-saturated. Cost γ C (m, m ) consists in the start-up cost of the machines and the variable production cost. We set by convention γ C (m, m ) = +∞ if the energy constraint is violated or the demand can not be satisfied. We obtain the formula :

γ C (m, m ) =          +∞ if m U + σ t-1 (v, m, N C , N + E , n E ) < d t +∞ if pm U + w(m -m) + > E f t ((m -m) + ) + ct m U otherwise
The minimal possible cost of a policy on the remaining time horizon {t + 1, . . . , v -1} is by definition

C (t + 1, m , N C - m , N + E , n E )
. By suboptimality principle, we have :

C (t, m, N C , N + E , n E ) = min m =0,...,M {γ C (m, m ) + C (t + 1, m , N C -m , N + E , n E )} (9)
case 2, t ∈ B E : t is not a C-saturated period but an E-saturated period Again, knowing the number m of machines running during period t, the production x t is fixed, since we have px t + wm + t = E by definition of an E-saturated period, with m + = (mm) + the number of machines started in period t. Hence, for a given value of m , the amount x t produced is equal to (Ew(mm) + )/p.

For the planning to be feasible, we must satisfy demand d t and ensures that the quantity x t produced is nonnegative. It results that we must have d t ≤ s t-1 + x t and x t ≥ 0. Similarly to the previous case, we introduce the cost γ E (m, m ) incurred in period t if t saturates the energy constraint, with the convention that γ E (m, m ) = +∞ if the demand can not be satisfied or the quantity produced is negative. We have:

γ E (m, m ) =          +∞ if (E -w(m -m) + )/p + σ t-1 (v, m, N C , N + E , n E ) < d t +∞ if E -w(m -m) + < 0 f t ((m -m) + ) + ct (E -w(m -m) + )/p otherwise
The optimal cost on the remaining time horizon till period v is then equal to

C (t + 1, m , N C , N + E -(m -m) + , n E -1). It results that : C (t, m, N C , N + E , n E ) = min m =0,...,M {γ E (m, m ) + C (t + 1, m , N C , N + E -(m -m) + , n E -1)} (10)

Dynamic programming algorithm

For a given regeneration point v and a given number l of machines running at the beginning of period v, we compute cost C (t, m, N C , N + E , n E ) for all possible state vectors such that t ≤ v using Equations ( 9) and [START_REF] Giglio | Integrated lot sizing and energy-efficient job shop scheduling problem in manufacturing/remanufacturing systems[END_REF], by taking the minimal of both expressions. The basis of the induction is given in period v by setting :

C (v, m, N C , N + E , n E ) = 0 for vector (v, l, 0, 0, 0) +∞ otherwise (11)
The computation of each cost C (t, m, N C , N + E , n E ) according to Equations ( 9) and ( 10) requests to compare O(M) different values of m , where each computation for a given m can be performed in constant time. The number of state vectors to consider is bounded by (M + 1) 3 T 3 : t and n E can take at most T different values, m is clearly bounded by (M + 1) and N C by (M + 1)T . Parameter N + E can also take at most (M + 1) different values, since at most M machines can be started in a period. Recall that in our setting there is no incentive to shut down a machine. It results that the number of starts over the time horizon is bounded by M, since a machine is started at most once. Hence, the computation of all the costs C (t, m, N C , N + E , n E ) for a given pair (v, l) requires O(M 4 T 3 ) operations. Recall that we want to compute the cost S (u, k, v, l) of all possible subplan (u, v), with k and l being the number of machines running at the beginning of period u and respectively v. Assume that all the costs C (t, m, N C , N + E , n E ) have been computed for pair (v, l). Again, if we know the state vector (u + 1, m, N C , N + E , n E ) reached at period u + 1, we can deduce the quantity x u produced in period u and the number m + u of machines started in period u. Indeed, we have

x u = d u + σ u (v, m, N C , N + E , n E ) and, clearly, m + u = (m -k) + .
In order to be feasible, the production must respect the capacity available and the energy limitation. With our convention that the cost γ R (k, m) is infinite if the constraints are violated in period u, we have :

γ R (k, m) =          +∞ if d u + σ u (v, m, N C , N + E , n E ) > mU +∞ if p(d u + σ u (v, m, N C , N + E , n E )) + w(m -k) + > E f u ((m -k) + ) + cu (d u + σ u (v, m, N C , N + E , n E )) otherwise
This cost γ R (k, m) can be computed in constant time if the value σ u of the stock level is known. The cost S (u, k, v, l) of the subplan starting at period u with k machines running can be obtained as :

S (u, k, v, l) = min{γ R (k, m) + C (u + 1, m, N C , N + E , n E ) | 0 ≤ m ≤ M, 0 ≤ N C ≤ MT, 0 ≤ N + E ≤ M, 0 ≤ n E ≤ T } (12)
Hence, computing S (u, k, v, l) for a given subplan can be performed in time O(M 3 T 2 ). Computing this cost for all the subplans (u, k, v, l) represents a computation effort in O(M 5 T 4 ), since we have in total O(M 2 T 2 ) subplans to consider. Notice that this complexity dominates the computation complexity of O(M 4 T 3 ) of determining the costs C (t, m, N C , N + E , n E ). The final complexity of the algorithm is thus in O(M 5 T 4 ) time. We have the following result :

Theorem 5. Problem energy-LSP-no-switch-off can be solved in polynomial time in O(M 5 T 4 ) if energy parameters p, w and E are stationary.

A polynomial time algorithm for energy-LSP

In this section, we extend the previous dynamic programming algorithm to deal with non-null parameters r, g and K, that is, considering a reservation cost and a reservation energy consumption to keep a machine ready, and a joint setup cost incurred in each production period. We show that, when all the energy parameters p, w, g and E are stationary, the problem is still polynomially solvable. Recall that in Section 4, we have established that if any of these three parameters is not null and time-varying, then problem energy-LSP is NP-hard, even on a single machine. Thus, we have quite precisely identified the frontier between easy and hard variants of energy-LSP.

Compared with problem energy-LSP-no-switch-off, each running machine incurs now a cost and consumes energy, even if it is not producing units. As a consequence, an optimal policy may switch off some machines in a period and possibly starts them again later, in order to save their reservation costs and to limit their energy consumption. Another difference is that, due to economies of scale induced by the joint setup costs, there may be periods with null production even if the number of running machines is positive and with a demand to satisfy. In this case, the demand is satisfied using the units in stock. As a result, Property 1 must be slightly modified into Property 2 given below. Figure 3 illustrates the different production possibilities of the Property. Property 2. In a dominant solution, each period t is either :

• a regeneration point, that is, s t-1 = 0

• or C-saturated, that is, x t = m t U

• or E-saturated, that is, px t + wm + t + gm t = E

• or a null production period, that is, x t = 0 It implies that a period t with both a positive entering stock (s t-1 > 0) and a positive production (x t > 0) is either C-saturated or E-saturated. The proof is similar to the proof of Property 1, by considering a period t with a positive production (hence the joint setup cost is already paid for) : Due to the non-speculative cost structure, postponing the production of one unit carried in the entering stock to period t can not increase the cost of the solution. As a consequence of Property 2, only the first period of a subplan can have a production that does not saturate constraints [START_REF] Masmoudi | Lot-sizing in a multi-stage flow line production system with energy consideration[END_REF] and [START_REF] May | Energy management in manufacturing: From literature review to a conceptual framework[END_REF]. Note that a null production period may also occur if all the machines are switched off. This is a special case of a C-saturated period, with m t = 0 and x t = m t U = 0.

We explain in the remainder of this section how the dynamic programming algorithm proposed in Section 5.1 can adapted to solve the more general problem energy-LSP. We obtain the following result : Theorem 6. Problem energy-LSP can be solved in polynomial time in O(M 6 T 6 ) if energy parameters p, w, g and E are stationary.

We point out the modifications by following the structure of Section 5.1 where the initial version of our dynamic programming algorithm is presented. Recall that we compute the optimal cost S (u, k, v, l) of each possible subplan, using a state vector (t, m, N C , N + E , n E ) to determine the optimal costs C (t, m, N C , N E , N + E , n E ) over the time horizon {t, . . . , v -1} inside a given subplan.

Optimal cost of a subplan (u, v)

The main modification of the algorithm is the enlargement of the state vector by the addition of a new component N E , which represents the sum of the number of machines running during each period of B E over the time horizon {t, . . . , v -1}, that is, N E = i∈B E :i≥t m i . Notice that N E is the counterpart of N C for the periods of B E . This new component is necessary to be able to evaluate the entering stock level of a period in our dynamic programming algorithm, as explained below. Consider the state vector (t, m, N C , N E , N + E , n E ) associated with a period t inside the subplan (u, v). Using the conservation of the flow over the time interval {t, . . . , v -1}, we have :

D t,v-1 + s v-1 = s t-1 + v-1 i=t x i = s t-1 + i∈B C :i≥t x i + i∈B E :i≥t x i = s t-1 + i∈B C :i≥t m i U + i∈B E :i≥t (E -m + i w -m i g)/p = s t-1 + N C U + (n E E -wN + E -gN E )/p Since s v-1 = 0,
as v is a regeneration point, we obtain that the entering stock level at period t is equal to :

s t-1 = D t,v-1 -N C U -(n E E -wN + E -gN E )/p
Slightly abusing the notation, we denote by σ t-1 (v, m, N C , N E , N + E , n E ) this quantity.

Another modification of the algorithm is that, due to Property 2, a period inside a subplan (u, v) may never be C-saturated nor E-saturated, but a null-production period. Hence, when computing cost C (t, m, N C , N E , N + E , n E ), we now need to distinguish between 3 cases, depending whether t belongs to B C , B E or is a null production period.

case 1, t ∈ B C : t is a C-saturated period
Recall that the quantity produced in period t saturates the available machine capacity, that is, x t = m U, with m the number of machines running in period t. Since the modified energy constraint pm U + w(mm) + + gm ≤ E must hold, the new formula to evaluate γ C (m, m ) taking into account the setup and reservation costs is :

γ C (m, m ) =          +∞ if m U + σ t-1 (v, m, N C , N E , N + E , n E ) < d t +∞ if pm U + w(m -m) + + gm > E f t ((m -m) + ) + ct m U + K t 1 {m } + rm otherwise
Where 1 {z} is the indicator function, equals to 1 if z > 0 and to 0 otherwise. It results that :

C (t, m, N C , N E , N + E , n E ) = min m =0,...,M {γ C (m, m ) + C (t + 1, m , N C -m , N E , N + E , n E )}
case 2, t ∈ B E : t is a E-saturated period and not a C-saturated period Due to the modification of the energy constraint (13), the amount x t produced in a E-saturated period is now equal to (Ewm + tgm )/p. Hence γ E (m, m ) is given by the formula :

γ E (m, m ) =          +∞ if (E -w(m -m) + -gm )/p + σ t-1 (v, m, N C , N E , N + E , n E ) < d t +∞ if E -w(m -m) + -gm < 0 f t ((m -m) + ) + ct (E -w(m -m) + -gm )/p + K t 1 {E-w(m -m) + -gm } + rm otherwise It results that : C (t, m, N C , N E , N + E , n E ) = min m =0,...,M {γ E (m, m ) + C (t + 1, m , N C , N E -m , N + E -(m -m) + , n E -1)} case 3, t B C ∪ B E : t is a null production period
The value of x t is by definition equal to 0. We must ensure that the entering stock level is greater than or equal to the demand in t for the planning to be feasible. Notice that it is possible to start some machines during period t and to keep some other running, even if no unit is produced. Hence we must also ensure that the energy constraint is not violated. The cost γ N (m, m ) incurred during a null production period t is given by:

γ N (m, m ) =          +∞ if σ t-1 (v, m, N C , N E , N + E , n E ) < d t +∞ if w(m -m) + + gm ≥ E f t ((m -m) + ) + rm otherwise
The optimal cost on the remaining time horizon till period v is equal simply to C (t ). Indeed, the new component N E can take at most (M + 1)T values, in the same way as N C . Moreover, the feasible set of N + E is also enlarged. Recall that N + E is the sum of the number of machines started in each period of B E over {t, . . . , v -1}. Without reservation costs nor reservation energy consumption, we only have M possibilities, since a machine is started at most once in a dominant planning. This is not true any more for energy-LSP : In a period one can switch off all the machines and later the same machines can be switched on again. Hence, the number of possible values for N + E increases to (M + 1)T . As a consequence, the computation of all the costs C (t, m, N C , N E , N + E , n E ) for a given pair (v, l) requires O(M 5 T 5 ) operations. Considering all pairs (v, l), the final complexity becomes O(M 6 T 6 ). Recall that the optimal cost S (u, k, v, l) of a subplan starting at period u with k machines running, is computed using the expression : 4-uplet (u, k, v, l) to consider, we obtain the overall complexity claimed in Theorem 6. We can remark that with null reservation energy consumption (g = 0), we do not need to incorporate N E in the state vector. In this case the complexity of the algorithm reduces to O(M 5 T 5 ).

+
S (u, k, v, l) = min{γ R (k, m) + C (u + 1, m, N C , N E , N + E , n E ) | 0 ≤ m ≤ M, 0 ≤ N C , N E , N + E ≤ MT, 0 ≤ n E ≤ T } Where γ R (k,

Conclusion and perspectives

In this paper, we have investigated a new energy-aware lot-sizing problem, where the amount of energy available in each period is limited. In the system under study, different activities consume energy, from turning on a machine, keeping it ready for production, to the effective production of goods. Hence, in each period, one has to arbitrate the use of energy between the increase of system capacity by starting up machines and keeping them running, and the effective production of units. We have established that problem energy-LSP is NP-hard, even in very restricted cases with null production cost and null holding costs. We have also shown that the problem is polynomially solvable if all energy consumption parameters are stationary. We have proposed an O(M 6 T 6 ) algorithm based on dynamic programming for the most general case studied in this article, including reservation costs, joint setup costs and reservation energy consumptions.

In the literature, very few studies integrate energy issues into the lot sizing problem from a theoretical point of view. This work is among the first attempts to study such production problem. Among the different perspectives of this work, one can investigate if efficient approximation algorithms can be developed for energy-LSP with timedependent energy parameters. Notice that we let open the question to know if the problem is NP-hard in the strong sense or in the weak sense. In the latter case, the design of a fully polynomial scheme, FPTAS, may be possible for the problem. Exact approaches for the problem, through polyhedral studies and the design of new cuts, would also be of interest. One extension of our model is to distinguish among more than two possible states for a machine (either turned off or running). In many situations, an idle machine can be put on a standby or sleep state, where it consumes less energy than in a running state, but may require an additional warm-up cost/energy consumption to resume. There can also exist different production modes on a machine, each one with a given processing speed and a given energy consumption. That is, the production capacity of a machine can be modulated with its energy consumption. It would be interesting to see if our model can be extended to capture such different energy consumption levels/states of the machines.

Figure 1 :

 1 Figure 1: Illustration of C-saturated, E-saturated and regeneration periods.

Figure 2 :

 2 Figure 2: A representation of the acyclic graph where the shortest path between (1, 0) and S is computed, for M = 2 machines.

Figure 3 :

 3 Figure 3: Illustration of different production periods in Property 2.

  m) is defined by : γ R (k, m)+∞ if d u + σ u (v, m, N C , N E , N + E , n E ) > mU +∞ if p(d u + σ u (v, m, N C , N + E , n E )) + w(mk) + + gm > E f u ((mk) + ) + cu (d u + σ u (v, m, N C , N + E , n E )) + K u 1 {d u +σ u (v,m,N C ,N + E ,n E )} + r u m otherwiseHence, for a given subplan, cost S (u, k, v, l) can be computed in time complexity O(M 4 T 4 ). Since we have O(M 2 T 2 )

  1, m , N C , N E , N + E , n E ). It results that : C (t, m, N C , N E , N + E , n E ) = min m =0,...,M {γ N (m, m ) + C (t + 1, m , N C , N E , N + E , n E )}5.2.2. Complexity of the algorithm. The number of state vectors (t, m, N C , N E , N + E , n E ) to consider in a given subplan is bounded by ((M + 1) 4 T 5

Acknowledgments

We are grateful to the anonymous referees for their very careful reading and suggestions which helped to improve the presentation of this paper.