Mohammadmohsen Aghelinejad
email: mohsen.aghelinejad@utt.fr

Yassine Ouazene
email: yassine.ouazene@utt.fr

Alice Yalaoui
email: alice.yalaoui@utt.fr

Complexity analysis of energy-efficient single machine scheduling problems

Keywords: Finite states single-machine scheduling, Energy efficiency, Time of use electricity tariffs, Complexity analysis

This paper deals with the complexity analysis of several energy-oriented single-machine scheduling problems addressed in the literature. The considered machine may be in different states: OFF, ON, Idle, or in transitions between them. The energy consumption of the machine at each time-slot is state-dependent. The objective is the minimization of the total energy consumption costs over the planning horizon.

For this purpose, two particular cases with constant energy price and increasing energy prices during all the time-slots are studied. These two problems are proved to be polynomial. Moreover, the general version of this problem with Time-Of-Use (TOU) energy prices and different processing times of the jobs is investigated in two versions: with and without the fixed sequence for the jobs. As the results, the version with the fixed sequence is proved to be polynomial, and the version without the fixed sequence (general version) is proved to be NP-hard. This paper also introduces different lower bounds to deal this general version of the problem. The performances of these lower bounds are discussed based on different numerical instances.

Introduction

Nowadays, a significant part of the energy in each country is consumed in the industry. For example, about 30% of all the end-use energy consumption in the United States is associated with industrial activities ( [START_REF] Fang | Scheduling on a single machine under time-of-use electricity tariffs[END_REF]). It is well-known that most countries use electricity as the main energy source for manufacturing. Rising electricity prices in addition to the ecological considerations have encouraged researchers to study the efficiency improvement of a production system in terms of energy consumption and costs involved, to reduce energetic production costs and environmental impact.

The energy consumption of a manufacturing system can be minimized at different levels such as machine-level, product-level, and system-level. Contrary to the machinelevel and product-level, which need great financial investments to redesign the machine(s) or product(s), at the system-level, manufacturers may reduce their energy consumptions using the existing decision tools based on optimization techniques. In this paper, some energy-efficient scheduling problems are studied to optimize the energy consumption of a single machine manufacturing system.

Based on the literature review analysis, the total energy consumptions and total energy costs minimization are the two objectives mostly used for dealing with the energy efficient scheduling problems. In the case of a single machine, the total energy consumptions consist of the amount of energy consumed during non-processing states (NPE) (e.g. the start-up, the transition between different states, shut down states, and idle states), and during processing state (PE). Therefore, decision makers may focus on the NPE or PE parts of any system to reduce its energy consumption. For this purpose, one of the most usual approaches is investigating the NPE consumption and using a scheduling method to change the job's processing order and the machine's state within a production shift.

In the following, a summary of the few papers addressing energy efficient scheduling problems on the single machine systems is given.

[2] presented a literature review of decision support models for energy efficient production planning. For each machine, the amount of its energy consumption depends on one or several factors, e.g. type of the machine, the machine's state, processing speed, and type of the jobs. Among the papers which consider the state factor, [START_REF] Mouzon | Operational methods for minimization of energy consumption of manufacturing equipment[END_REF] developed operational methods by using some dispatching rules. They also proposed a multi-objective model to minimize the energy consumption and total completion time of the system. [START_REF] Mouzon | A framework to minimise total energy consump-tion and total tardiness on a single machine[END_REF] presented a framework for a system with idle and setup states to minimize total energy consumption and total tardiness simultaneously. Energy consumption and total completion time minimization of a single machine are studied in [START_REF] Yildirim | Single-machine sustainable production planning to minimize total energy consumption and total completion time using a multiple objective genetic algorithm[END_REF], using a multi-objective genetic algorithm and dominance rules. [START_REF] Tarakc ¸ı | Design of a genetic algorithmic approach for reducing energy consumption in single machine production systems[END_REF] developed a model and algorithm that minimize energy consumption in a single machine production system with decision whether the machine should be idle or switched on or off between consecutive jobs. [START_REF] Che | Energy-efficient bi-objective single-machine scheduling with power-down mechanism[END_REF] considered a single-machine scheduling problem with power-down mechanism. The aim is to find an optimal processing sequence of jobs and determine if the machine execute a power-down operation between two consecutive jobs that minimize both total energy consumption and maximum tardiness.

[8] addressed a single-machine scheduling problem with cumulative deteriorating effect and multiple maintenance activities to determine the sequence of jobs and the number of maintenance activities as well as their positions, in order to minimise energy consumption. To solve this problem, a mixed integer linear programming model in addition to a genetic algorithm (GA), a particle swarm optimisation (PSO) algorithm and a hybrid PSO (HPSO) approach are proposed. [START_REF] Liao | Multi-objective optimization of single machine scheduling with energy consumption constraints[END_REF] studied a bi-objective single machine scheduling problem with energy consumption constraints, in which the objective functions were the total weighted completion time and the total weighted tardiness. They adopted a multi-objective particle swarm optimization algorithm to solve this problem.

Among the papers which consider the speed factor, [START_REF] Tasgetiren | Energy-efficient single machine total weighted tardiness problem with sequence-dependent setup times[END_REF] examined the trade-off between total energy consumption and total weighted tardiness in a single machine environment with sequence-dependent setup times, where different jobs can be operated at varying speed levels. [START_REF] Antoniadis | Non-preemptive speed scaling[END_REF] and [START_REF] Antoniadis | A fully polynomial-time approximation scheme for speed scaling with sleep state[END_REF] studied the complexity of the deadline-based preemptive and non-preemptive scheduling problems with a variable processing speed.

The scheduling problems with continuous resource and energy constraint are addressed in [START_REF] Artigues | The energy scheduling problem: Industrial casestudy and constraint propagation techniques[END_REF], [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF] and [START_REF] Nattaf | Energetic reasoning and mixedinteger linear programming for scheduling with a continuous resource and linear efficiency functions[END_REF], to minimize the amount of energy consumption.

In addition to the mentioned factors which change the amount of energy consumption of a machine, different policies are also considered by researchers to investigate the possible modifications on the total energy costs of a system, such as time-of-use pricing (TOU), real-time pricing (RTP), and critical peak pricing (CPP). For example, [START_REF] Che | An efficient greedy insertion heuristic for energyconscious single machine scheduling problem under time-of-use electricity tariffs[END_REF] addressed an energy-conscious scheduling problem of a single machine, in which each processing job has its power consumption, and electricity prices may vary from hour to hour throughout a day. [START_REF] Gong | Integrating labor awareness to energy-efficient production scheduling under real-time electricity pricing: An empirical study[END_REF] proposed a method for energy efficient and labor-aware production scheduling at the unit process level under real-time electricity pricing. [START_REF] Lee | A dynamic control approach for energy-efficient production scheduling on a single machine under time-varying electricity pricing[END_REF] studied a single machine scheduling problem which deals with the assignment of a set of jobs to available time periods under time-varying electricity pricing, while considering requested due dates of jobs so as to minimize total penalty costs for earliness and tardiness of jobs and total energy consumption costs, simultaneously. [START_REF] Rubaiee | An energy-aware multiobjective optimization framework to minimize total tardiness and energy cost on a single-machine nonpreemptive scheduling[END_REF] worked on a non-preemptive single-machine scheduling problem under TOU electricity tariffs in order to minimize the total tardiness and total energy cost.

They proposed a mixed-integer multi-objective mathematical programming model and several new holistic genetic algorithms for this problem. [START_REF] Zhang | A new greedy insertion heuristic algorithm with a multi-stage filtering mechanism for energy-efficient single machine scheduling problems[END_REF] developed a new greedy insertion heuristic algorithm with a multi-stage filtering mechanism for single machine scheduling problems under TOU electricity tariffs. [START_REF] Albers | Energy-efficient algorithms for flow time minimization[END_REF] proposed an energy-efficient algorithm to minimize the total flow time and the total cost of a single machine scheduling problem, when the processor has variable speeds and different energy consumptions. Generic mixed-integer programming models for a single machine scheduling that minimize total energy cost at volatile energy prices are presented in [START_REF] Gong | An energy-cost-aware scheduling methodology for sustainable manufacturing[END_REF] and [START_REF] Gong | A generic method for energyefficient and energy-cost-effective production at the unit process level[END_REF]. Some scheduling problems with arbitrary power demands for the jobs, and uniform or variable processing speeds in preemptive and nonpreemptive cases are studied in [START_REF] Fang | Scheduling on a single machine under time-of-use electricity tariffs[END_REF] to minimize total electricity cost under a time of use electricity tariffs. A preemptive scheduling problem with energy constraint in each time-slot, different energy consumption for each job, and the electricity time-varying prices are investigated in [START_REF] Mikhaylidi | Operations scheduling under electricity time-varying prices[END_REF] to minimize the total electricity consumption costs and the operations postponement penalty costs. [START_REF] Shrouf | Optimizing the production scheduling of a single machine to minimize total energy consumption costs[END_REF] deals with a single machine scheduling problem which has different possible states. They proposed a mathematical model to minimize total energy consumption costs with variable energy prices. The same problem as [START_REF] Shrouf | Optimizing the production scheduling of a single machine to minimize total energy consumption costs[END_REF], is considered in [START_REF] Aghelinejad | Machine and production scheduling under electricity time varying prices[END_REF] to improve the previous mathematical model. They also presented a new mathematical model to obtain the optimal schedule for the machine's state and the job's sequence, simultaneously. Then, a new heuristic algorithm and a genetic algorithm are proposed in [START_REF] Aghelinejad | Production scheduling optimisation with machine state and time-dependent energy costs[END_REF] to solve the problem without the fixed sequence for the jobs. The complexity of a preemptive multi-states single machine scheduling problem is analyzed in [START_REF] Aghelinejad | Preemptive Scheduling of a Single Machine with Finite States to Minimize Energy Costs[END_REF], using a dynamic programming approach. [START_REF] Gong | A power data driven energycost-aware production scheduling method for sustainable manufacturing at the unit process level[END_REF] addressed a new production scheduling method to minimize the total energy costs, when a finite set of states (multiple idle modes) is considered for the machine.

A comprehensive literature analysis demonstrates that there are several energyefficient single machine scheduling problems, but to the best of our knowledge, there are a few studies which deal with the complexity of this kind of problem, when the machine has finite states. This paper aims to fill this gap in the literature. The remainder of the paper is organized as follows. In section 2, the problem statement and its assumptions are introduced. In section 3, the complexity of the fixed sequence case of the problem under Time-Of-Use energy costs is investigated. Then, in sections 4, the complexity of two variants of the scheduling problems are analyzed. Section 5 studies the complexity of the general problem with Time-Of-Use energy costs, and presents some lower bounds for this problem. Finally, section 6 summarizes the contributions of this study and draws some future directions for next studies.

Problem statement

The addressed problem can be described as follows. Let consider n jobs which must be scheduled on a single machine within a given planning horizon (T time-slots).

The jobs must be processed non-preemptively. All the jobs are available at time-slot 0 to T (r j = 0 ; ∀ j = 1, ..., n).

The machine has 3 main states (ON, OFF, Idle) and 2 transition states for turning on and turning off (Ton, Toff). When the machine is in state k ∈ {OFF, Ton, ON, To f f , Idle}, it must remain in the same state during a fixed number of time-slots (d k ). For example, a transition from ON to OFF implies that, the machine must stay in Toff state during d To f f = β 2 time-slots. In other words, switching ON and OFF the processor causes delays. Each state k is also characterized by an energy consumption (e k ). This means the energy consumption of the machine in state ON is constant and independent from the processed job (Fig. 1). The machine must be in OFF state during the initial (t = 0) and the final (t = T ) time-slots. Note that, in this study, time-slot 0 is just for identifying the initial state of the machine which is OFF. The scheduling horizon is from time-slot 1 to T . Without loss of generality, the following relations are also considered for the machine states energy consumption: e ON > e Idle > e OFF = 0 (1) e Ton > e OFF = 0 (2)

e To f f > e OFF = 0 (3)
The minimum energy consumption of the machine is during state OFF, which is considered negligible (e OFF = 0). These assumptions and the possible transitions between different states are illustrated in Fig.

F = (e OFF × ∑ t∈ϕ OFF c t ) + (e Ton × ∑ t∈ϕ Ton c t )+ (e ON × ∑ t∈ϕ ON c t ) + (e To f f × ∑ t∈ϕ To f f c t ) + (e Idle × ∑ t∈ϕ Idle c t ) (4)
Since the initial and final states of the machine are assumed as OFF states, the machine is in Ton/Toff state at least for once. Let consider λ ∈ N the number of turning on or turning off over the T time-slots, then:

|ϕ Ton | = λ × β 1 (5) |ϕ To f f | = λ × β 2 (6)
Moreover, for each additional Toff/Ton transitions, the machine must stay in OFF state

during at least one time-slot (|ϕ OFF | ≥ λ ).
The required number of time-slots to have a feasible solution for this problem is equal to sum of the processing times (P = ∑ n j=1 p j ), plus the required number of time-slots for initial Ton and final Toff states (β 1 + β 2 ), plus one (because the machine must be in OFF state at the end of the horizon). In this problem, one of the essential conditions to have at least one feasible solution is that the T value must be always larger than the number of required time-slots. The difference between the T value and the required time-slots' value, can be defined as the number of extra time-slots. Let x indicates the number of these extra time-slots, then:

x = T -P -(β 1 + β 2 + 1) (7)
For example, in a problem with 3 jobs, 15 time-slots and the parameters' values as:

β 1 = 2, β 2 = 1, p 1 = 2, p 2 = 1, p 3 = 2, x is equal to [15 -5 -(2 + 1 + 1)] = 6. Based
on the problem's objective, the machine must be put into the non-processing states during these x time-slots (one or several cases among initial or final OFF states, idle states between the ON states, and middle-OFF states may be used). Note that each middle-OFF state consists of a sequence of Toff, OFF during at least one time-slot, and Ton states.

Therefore, the cardinal of sets ϕ k ∀k ∈ {Ton, ON, To f f , Idle, OFF} in any feasible

                                                   |ϕ Ton | = λ × β 1 |ϕ ON | = P |ϕ To f f | = λ × β 2 |ϕ Idle | ≥ 0 |ϕ OFF | ≥ λ (8)
where:

165 |ϕ Ton | + |ϕ ON | + |ϕ To f f | + |ϕ Idle | + |ϕ OFF | = T (9)
Since for each feasible solution, we have |ϕ ON | = P, so:

|ϕ Ton | + |ϕ To f f | + |ϕ Idle | + |ϕ OFF | = T -P (10)
For example, the gantt chart for an instance of 5 jobs and 32 time-slots with the parameters' values as: In the next sections, first of all the complexity analysis of a specific version of the problem with a pre-determined order for the jobs which is investigated in [START_REF] Shrouf | Optimizing the production scheduling of a single machine to minimize total energy consumption costs[END_REF] is addressed. By using Graham's three fields notation, this problem can be defined are studied.

β 1 = 2, β 2 = 1, p 1 = 3, p 2 = 2, p 3 = 4, p 4 =

The problem with time-of-use (TOU) energy prices and fixed sequence

Problem 1, T OU|sequence, states|T EC is already addressed by [START_REF] Shrouf | Optimizing the production scheduling of a single machine to minimize total energy consumption costs[END_REF] in the literature, where they proposed an LP mathematical model to find the optimal schedule for the system with a fixed sequence of the jobs by making decisions at the machine level.

Their experimental results proved the disability of the proposed analytical solution to solve the instances of this problem with more than 60 jobs during 3 hours. Moreover, their research was based on the fact that "since the shop floor scheduling problem is considered to be an NP-hard-complete problem, so, this problem cannot be solved in real life.", and they proposed a genetic algorithm to find a solution for any instance of this problem.

In this paper, before considering the more general problems, we want to give a prove for the complexity of this problem which is not addressed in the literature. For this purpose, in the following a dynamic programming approach is presented to model this problem (1, T OU|sequence, states|T EC). This approach is based on a finite graph whose dimension (number of vertices and edges) is dependent on the total number of processing times (P) and the total number of time-slots (T ).

In what follows, this approach it has been described in more details.

Graph construction steps

The using graph consists of several decision-making levels (l) and nodes, where each level represents one time-slot of the problem's horizon. As a consequence, the graph consists of T + 1 decision levels (0 ≤ l ≤ T ), and each level has some nodes.

Let us consider H l to present the possible nodes for level l, which corresponds to the possible states of the machine in each time-slot. Each node of is also characterized by the cumulative number of production units (k) from time-slot 0 to l. Because of the problem's assumption that machine is in OFF state within the initial and final timeslots, H 0 = {I} and H T = {F}. In this graph, I represents that the machine is in initial state and it did not performed any job, and F indicates the final status of the machine after processing all the jobs (P).

Let us explain our approach by using an example with 3 jobs, 15 time-slots, 5 production units and the parameters' values as Table 1, which is presented in Figure 3. For this instances, the possible number of production units at time-slot (level) 7 can be 1 to 5 units (H 7 = {1, 2, 3, 4, 5}). Because, if it were less than 1 unit, there will not be enough time to complete all the jobs during the rest of horizon. Moreover, according to the set up times, 7 units of time are not enough to process all the 5 production units and turn off the machine. For these reasons, a time interval is defined for each node which represents the earliest and the latest possible levels that contains node k in the graph, and is shown by

τ k = {l min(k) , • • • , l max(k) }.
The time interval time for node k simplifies as:

τ k ∈ {β 1 + k, • • • , x + β 1 + k} ; ∀k ∈ {1, • • • , P} (11)
Therefore, the first step among the graph construction steps is to place all the nodes (k ∈ {I, 1, • • • , P, F}) in the graph using their related time interval (τ k ).

Once all the possible nodes of the graph are placed, the second step is to draw the edges and compute their value which represent the total energy cost for doing the related transitions between node (k, l) and node

(k , l ) (Ev (k,l)-(k ,l ) ; ∀ k ∈ H l , k ∈ H l , l ≥ l + 1).
In order to distinguish the different types of the edges, they are divided into three main sets (E 1 , E 2 , E 3 ). The first set (E 1 ) connects the nodes with the same k number between level l and l + 1, which indicates the Idle state with the edge value of:

Ev (k,l)-(k,l+1) = c l+1 × e Idle ; ∀k ∈ {p 1 , p 1 + p 2 , • • • , n-1 ∑ j=1 p j } (12)
where c l is the unite of energy price in time-slot l, e Idle is the machine's energy consumption in Idle state, and p j is the process time of job j. The total number of edges for this set is:

|E 1 | = (n -1) × x.
The second set (E 2 ) connects nodes (k, l) to node (k + 1, l ) that consists of three cases.

The first case is for the initial turning on phase of the system, with the edge value as:

Ev (I,0)-(1,l) = l-1 ∑ i=l-β 1 (c i × e Ton ) + c l × e ON (13)
the second case is for processing the next production unit with the edge value as:

Ev (k,l)-(k+1,l ) = c l × e ON ; l = l + 1 ( 14
)
and the third case is for the final turning off phase of the system, with the edge value as:

Ev (P,l)-(F,T ) = l+β 2 ∑ i=l+1 (c i × e To f f ) + T ∑ i=l+β 2 +1 (c i × e OFF ) (15)
The cardinal of this set of edges is equal to: The third set (the last one E 3 ), shows the middle shutdown between two processing states. It connects node (k, l ) with node

|E 2 | = (P + 1) × (x + 1) (16)
(k + 1, l), where, l ∈ {l min(k) , • • • , x + k -β 2 -
1}, and the edge value is:

Ev (k,l )-(k+1,l) = ∑ l +β 2 i=l +1 (c i × e To f f ) + ∑ l-1 i=l-β 1 (c i × e Ton ) + c l × e ON ; ∀k ∈ {p 1 , p 1 + p 2 , • • • , ∑ n-1 j=1 p j } (17)
The cardinal of this set is:

245 |E 3 | = x-(β 1 +β 2 ) ∑ i=1 i × (n -1) (18)
As a result, the related graph of a problem with T time-slots, P production units and x value has the total number of nodes and edges as follow:

|V | = P × (x + 1) + 2 ∼ = T P (19)
|E| = |E 1 | + |E 2 | + |E 3 | ∼ = T 2 P ( 20
)
For example, the corresponding graph of our instance with P = 5, T = 15,

β 1 = 2, β 2 =
1, x = 6, and different energy prices (c t ), consists of 37 nodes and 66 edges (see Fig. 3).

250

C (I,0) = 0 C (k,l) = min (k ,l )∈A k,l {C (k ,l ) + Ev (k ,l )-(k,l) } (21)
For the presented instances in Figure 3 As a consequence, by this approach, C (F,T ) represents the objective value of the optimal solution for the problem.

Since with the presented approach any instance of the considered problem can be modeled by using a finite graph, if the shortest path of this graph (the optimal solution) can be also obtained in a polynomial time, then we can conclude that the problem is polynomial. On this account, Dijkstra's algorithm, which is one of the most efficient algorithms to find the shortest path between the source node and every other node of is based on a min-priority queue ( [START_REF] Fredman | Fibonacci heaps and their uses in improved network optimization algorithms[END_REF]). As a consequence, the complexity of this algorithm for the presented problem is equal to:

a
O(T 2 P + T P log T P) ∼ = O(T 2 P) (22)
Since the largest possible value of P is T (worst case analysis), it means that Dijkstra's algorithm obtain the optimal solution of this problem with T time-slots in O(T 3 ) which is a polynomial time.

As a result, it can be concluded that unlike what the authors considered in [START_REF] Shrouf | Optimizing the production scheduling of a single machine to minimize total energy consumption costs[END_REF], problem 1, T OU|sequence, states|T EC is polynomial.

The application of Dijkstra's algorithm on the considered instance, is presented in Figure 3. To be more clear, the best solution for this instance is to turn the machine on from time-slot 0 and process all the jobs based on their order during time-slots 3 to 7, and finally, turning the machine off in time-slot 9 which has the cost of 155.

After that we succeeded to prove that problem 1, T OU|sequence, states|T EC is polynomial, for the next step, we are interested to analyse the complexities of several problems when the jobs' sequence is not fixed (1|states|T EC). For this purpose, the problems with and without a regular trend for the energy prices are studied in the next sections.

The problems with a regular trend of the energy prices

In this section, the complexities of the problems with a constant, increasing, and decreasing energy prices for the case without the fixed sequence are investigated. Proof. In this problem (pb 2 ), the price of energy during all the time-slots is constant

(c t = c ; ∀t = 1, • • • , T ),
Let consider the solution S 2 such that:

|ϕ 2 OFF | = T -(β 1 +P+β 2 ), |ϕ 2 Ton | = β 1 , |ϕ 2 ON | = P, |ϕ 2 To f f | = β 2 , |ϕ 2
Idle | = 0, with the objective function value of F 2 . For any other feasible solution of pb 2 , as S i 2 with objective function F i 2 , the relation between F i 2 and F 2 is as follow:

F i 2 -F 2 = [(|ϕ i OFF | -|ϕ 2 OFF |) × e OFF + (|ϕ i Ton | -|ϕ 2 Ton |) × e Ton + (|ϕ i To f f | -|ϕ 2 To f f |) × e To f f + (|ϕ i Idle | -|ϕ 2 Idle |) × e Idle ] × c (24)
Regarding equations ( 1

F i 2 -F 2 = [(|ϕ i OFF | + |ϕ i Ton | + |ϕ i To f f | + |ϕ i Idle | -T + P) × e OFF +(|ϕ i Ton | -β 1 ) × δ 1 + (|ϕ i To f f | -β 2 ) × δ 2 + (|ϕ i Idle | -0) × δ 3 ] × c = [(|ϕ i Ton | -β 1 ) × δ 1 + (|ϕ i To f f | -β 2 ) × δ 2 + |ϕ i Idle | × δ 3 ] × c (25)
Based on equation ( 8) and the fact that λ ≥ 1, we have

|ϕ i Ton | -β 1 ≥ 0, |ϕ i To f f | - β 2 ≥ 0, |ϕ i Idle | ≥ 0.
Consequently, it can be concluded that F i 2 -F 2 ≥ 0 which means F 2 is a lower bound of this problem (pb 2 ). Since S 2 is also a feasible solution for pb 2 , for this reason, S 2 is the optimal solution. Note that, in this problem, S 2 is not a unique optimal solution. All feasible solutions which have the same value as |ϕ 2 k | for state k ∈ {OFF, Ton, ON, To f f , Idle}, have the same objective function value. Moreover, there is not any priority between the jobs of this problem.

As a consequence, the optimal solution of problem pb 2 is when the machine has just one turning on and one turning off states, and processes all the jobs (in any order) continuously without any idle state. Also, it remains in OFF state during the rest of the horizon. For example, for the presented problem in Fig. 4, there exist 8 different solutions with the same objective value. Any of these solutions can be considered as the optimal solution. Since this set of optimal solutions can be obtained directly, pb 2 is polynomial. Proof. Total energy consumption costs minimization of a production system can be reached by two ways: energy consumptions minimization and/or total energy costs minimization. In this problem (pb 3 ), unlike the previous one, the energy costs are different in each time-slot, for this reason, both of these ways may be used. The total energy consumptions of the machine should be minimized by minimizing the number of time-slots for each state (as it is demonstrated for pb 2 ). Moreover, the total energy costs may be minimized by placing the high-consumption states at the low-cost timeslots.

Let consider the solution S 3 as:

                                                   ϕ 3 Ton = {1, • • • , β 1 } ϕ 3 ON = {β 1 + 1, • • • , β 1 + P} ϕ 3 To f f = {β 1 + P + 1, • • • , β 1 + P + β 2 } ϕ 3 OFF = {β 1 + P + β 2 + 1, • • • , T } |ϕ 3 Idle | = 0 ( 26
)
with the objective function value of F 3 which may be computed from equation [START_REF] Mouzon | A framework to minimise total energy consump-tion and total tardiness on a single machine[END_REF].

For any other feasible solution S i 3 of pb 3 with F i 3 as the objective value, the relation between F i 3 and F 3 is as follow:

F i 3 -F 3 = e OFF × (∑ t∈ϕ i OFF c t -∑ t∈ϕ 3 OFF c t ) + e Ton × (∑ t∈ϕ i Ton c t -∑ t∈ϕ 3 Ton c t )+ e ON × (∑ t∈ϕ i ON c t -∑ t∈ϕ 3 ON c t ) + e Idle × ∑ t∈ϕ i Idle c t + e To f f × (∑ t∈ϕ i To f f c t -∑ t∈ϕ 3 To f f c t ) (27)
The other possible solutions for this problem can be divided into two main sets. The first set case is composed of the solutions obtained by adding some non-processing states (Idle or middle-off) between two processing states, and the second one is obtained by changing the starting time of processing, adding some initial-off states. All the other solutions are mixed of these two cases.

For the first case, regarding equations ( 1), ( 2), and (3), obviously adding some nonprocessing states which consume more than OFF state (e OFF = 0), causes an increase of the total energy consumptions and consequently the total energy consumption costs. Let consider a general example (Fig. 5) such that:

1 < t 1 < t 2 < t 3 < t 4 < T . If between
two ON states, the machine goes to the Idle state during time-slot t 2 + 1, based on the equation ( 27), we have:

F i 3 -F 3 = e Idle × c t 2 +1 + e ON × (∑ t 3 +1 t=t 2 +2 c t -∑ t 3 t=t 2 +1 c t )+ +e To f f × (∑ t 4 +1 t=t 3 +2 c t -∑ t 4 t=t 3 +1 c t ) + e OFF × (∑ T t=t 4 +2 c t -∑ T t=t 4 +1 c t ) (28)
Therefore,

F i 3 -F 3 = e Idle × c t 2 +1 + e ON × (c t 3 +1 -c t 2 +1 )+ +e To f f × (c t 4 +1 -c t 3 +1 ) -e OFF × c t 4 +2 (29)
Since in pb 3 , e OFF = 0, e Idle > 0, and ∀t > t; c t > c t , we have:

F i 3 -F 3 ≥ 0 ( 30
)
By the same procedure, it can be proved that multiple shut down operations (middle-off states) which includes a sequence of Toff, OFF and Ton states with at least [(e To f f × For the second case, let consider a general example (Fig. 6) such that: 1 < t 1 < t 2 < 350 t 3 < T and t z < t z ∀z = 1, 2, 3. Based on the equation ( 27), we have:

F i 3 -F 3 = e OFF × (∑ t 0 t=1 c t + ∑ T t=t 3 +1 c t -∑ T t=t 3 c t ) + e Ton × (∑ t 1 t=t 0 +1 c t -∑ t 1 t=1 c t )+ e ON × (∑ t 2 t=t 1 +1 c t -∑ t 2 t=t 1 +1 c t ) + e To f f × (∑ t 3 t=t 2 +1 c t -∑ t 3 t=t 2 +1 c t ) (31)
Accordingly,

F i 3 -F 3 = e OFF × (∑ t 0 t=1 c t -∑ t 3 t=t 3 +1 c t ) + e Ton × (∑ t 1 t=t 0 +1 c t -∑ t 1 t=1 c t )+ e ON × (∑ t 2 t=t 1 +1 c t -∑ t 2 t=t 1 +1 c t ) + e To f f × (∑ t 3 t=t 2 +1 c t -∑ t 3 t=t 2 +1 c t ) (32)
Regarding to equations ( 1), (2), and (3), since in pb 3 , e OFF = 0 and ∀t > t; c t > c t , we have:

F i 3 -F 3 ≥ 0 (33)
Thus, for any feasible solution as S i 3 , we have Then, the jobs must be processed from time-slot β 1 + 1 to β 1 + 1 + P in any order, and finally, the machine must be in turning off and OFF states consecutively (Fig. 7).

F i 3 -F 3 ≥ 0. It means that F 3 , is a
Therefore, pb 3 is a polynomial problem with the optimal objective value of F 3 .

Note that, with the same approach, but in a backward way, it can be proved that:

If the energy prices between two consecutive time-slots were decreasing (c t > c t+1 ; ∀t =

1, • • • , T -1)
, the problem is also polynomial (Fig. 8).

The problem with time-of-use (TOU) energy prices without fixed sequence

For the third part of this paper, the problem with TOU energy prices without fixed sequence is addressed (Fig. 2). In the following the complexity of this problem, when the jobs have different processing times, is investigated. Proof. The proof is based on the fact that the decision problem related to this optimization problem, may be reduced to a 3-PARTITION problem, which is strongly NP-hard ( [START_REF] Garey | A guide to the theory of np-completeness[END_REF]). In the following, the same approach which is utilised by [START_REF] Fang | Scheduling on a single machine under time-of-use electricity tariffs[END_REF] to prove that the problem with just two states for the machine (ON-OFF) and arbitrary power demands For this purpose, the 3t jobs must be partitioned to t sets such that each set consists of 3 jobs, and the sum of their processing times must be equal to b. Then, each set must be partition into one interval with the length of b time-slots, which can be achieved if and only if, 3-PARTITION has a solution (see Fig. 9). Therefore, since the 3-PARTITION is known as an NP-complete problem ( [START_REF] Garey | A guide to the theory of np-completeness[END_REF]), as a consequence, pb 4 is NP-hard.

Since it is not possible to find the optimal solution of an NP-hard problem by using the usual exact methods, approximation methods are developed to find a near optimal feasible solution for this kind of problems ( [START_REF] Aghelinejad | Production scheduling optimisation with machine state and time-dependent energy costs[END_REF]). A usual tool to evaluate the performances of such methods is to propose lower bounds. For this reason, in the following we attempted to propose some lower bounds for problem pb 4 .

Lower bounds for pb 4

From the given set of the time-slots' energy cost

C = {c t ; ∀t = 1, • • • , T }, let con- sider the set C = { c1 , c2 , • • • , cT }, which contains the time-slots' energy cost in the increasing order, such that c1 ≤ c2 ≤ • • • ≤ cT .
Then, the following relation can also be written:

θ ∑ t=1 ct ≤ θ ∑ t=1 c t ∀θ = 1, • • • , T (40)
Regarding equations ( 1), (2), and (3), the OFF state has the minimum energy consumption between all the non-processing states. Therefore, in the cases that the unite energy prices are increasing, obviously adding some non-processing states which consume more than OFF state would increase the total energy consumptions and consequently the total energy consumption costs. That is why during the rest of this study, for defining the lower bounds, the minimum number of required time-slots are considered for Ton and Toff states, and states of the machine during all the remaining time-slots are considered as OFF state.

Let define LB 1 as the cost obtained allocating the cheapest time-slots to each state.

So, we have:

LB 1 = (e OFF × T -(β 1 +P+β 2 ) ∑ t=1 ct ) + (e Ton × β 1 ∑ t=1 ct ) + (e ON × P ∑ t=1 ct ) + (e To f f × β 2 ∑ t=1 ct ) (41) Lemma 4. LB 1 is a lower bound of pb 4 .
Proof. Regarding the equation ( 4), the optimal value of total energy costs (F 4 ) for the problem pb 4 can be computed as:

F 4 = e OFF × ∑
Based on the problem's assumption (equations ( 8),( 9),( 10)), the cardinal of ϕ k for each state in the optimal solution are as follows (λ ≥ 1):

           |ϕ 4 Ton | = λ × β 1 ; |ϕ 4 ON | = P; |ϕ 4 To f f | = λ × β 2 ; |ϕ 4 Idle | ≥ 0; |ϕ 4 OFF | ≥ λ (43) |ϕ 4 Ton | + |ϕ 4 To f f | + |ϕ 4 Idle | + |ϕ 4 OFF | = T -|ϕ 4 ON | = T -P (44)
Based on equation 40, we have the following equations:

                                       ∑ β 1 t=1 ct ≤ ∑ |ϕ 4 Ton | t=1 ct ≤ ∑ t∈ϕ 4 Ton c t ∑ P t=1 ct ≤ ∑ t∈ϕ 4 ON c t ∑ β 2 t=1 ct ≤ ∑ |ϕ 4 To f f | t=1 ct ≤ ∑ t∈ϕ 4 To f f c t ∑ T -(β 1 +P+β 2 ) t=1 ct ≤ ∑ |ϕ 4 OFF | t=1 ct ≤ ∑ t∈ϕ 4 OFF c t (45)
Based on the above equations (45), the following relation can be obtained for LB 1 and F 3 :

LB 1 -F 4 ≤ 0 (46)
Therefore, LB 1 is a lower bound for pb 4 .

To define the first lower bound (LB 1 ), the non-preemption and precedence constraints for the states of the machine (Fig. 1), and the fact that the machine must be in one and only one state per time-slot are relaxed. Only the importance of energy price in each time-slot is considered. For example, by these constraints, if the machine starts to process job j in time-slot t, the machine must be in ON state from time-slot t to t + p j -1, and it is not possible to be in other states during them. For this purpose, we defines the second lower bound (LB 2 ), which sorts the time-slots based on their energy costs and allocates them into Ton, ON, To f f , and OFF states, respectively and continuously. By this way, in the second lower bound's solution the machine has only one state in each time-slot, but, the non-preemption and the precedence constraints for the states are relaxed yet. LB 2 is computed as follow:

LB 2 = (e Ton × ∑ β 1 t=1 ct ) + (e ON × ∑ β 1 +P t=β 1 +1 ct )+ (e To f f × ∑ β 1 +P+β 2 t=β 1 +P+1 ct ) + (e OFF × ∑ T t=β 1 +P+β 2 +1 ct ) (47)
Lemma 5. LB 2 is a lower bound of pb 4 .

Proof. pb 4 with ct ; ∀t = 1, • • • , T , converts to pb 3 which its optimal solution is provided in section 4.2. Accordingly, the optimal solution of pb 3 (F 3 ) may be used as a lower bound of pb 4 . As it is proved during equations ( 27) to (33), LB 2 ≤ F i 3 ≤ F 4 . For this reason, LB 2 is a lower bound of problem pb 4 .

Let consider C ¯j that computes the minimum cost of performing job j (∀ j = 1, ..., n) non-preemptively during its possible time-slots. As it is explained before, the possible time-slots that the machine can be in Ton, Toff and ON states depend to the total number of time-slots in the horizon, the number of extra time-slots, and the number of required time-slots for performing each job. Thus, C ¯j may be formulated as follow.

C ¯j = min{c t + c t+1 + • • • + c t+p j -1 }; ∀t ∈ {β 1 + 1, • • • , T -p j -β 2 }; ∀ j ∈ {1, • • • , n} (48)
Then, following the same idea, the minimum costs for Ton, Toff and OFF states are obtained with the following formulations.

C ¯Ton = min{c t + c t+1 + • • • + c t+β 1 -1 }; ∀t ∈ {1, 2, • • • , x + 1} (49) C ¯To f f = min{c t + c t+1 + • • • + c t+β 2 -1 }; ∀t ∈ {T -x -β 2 , • • • , T -β 2 } (50) C ¯OFF = T -(β 1 +P+β 2 ) ∑ t=1 ct (51)
As it has been discussed before, regarding equations ( 1

¯OFF ≤ ∑ t∈ϕ 4 OFF c t ; C ¯Ton ≤ ∑ t∈ϕ 4 Ton c t ; C ¯To f f ≤ ∑ t∈ϕ 4 To f f c t ; n ∑ j=1 C ¯j ≤ ∑ t∈ϕ 4 ON c t (53)
And we have:

           e k × C ¯k ≤ e k × ∑ t∈ϕ 4 k c t ; ∀k ∈ {OFF, Ton, To f f } e ON × ∑ n j=1 C ¯j ≤ e ON × ∑ t∈ϕ 4 ON c t (54)
Consequently:

LB 3 ≤ F 3 (55)
Therefore, LB 3 is a lower bound of this problem.

Moreover, the optimal solution of the preemption version of this problem can be defined as LB 4 .

Lemma 7. LB 4 is a lower bound of pb 4 .

Proof. As it is demonstrated in a previous work ( [START_REF] Aghelinejad | Preemptive Scheduling of a Single Machine with Finite States to Minimize Energy Costs[END_REF]), the preemption version of this

Numerical experiments for the proposed lower bounds

To evaluate the efficiency of the proposed lower bounds in this study, several randomly generated instances are considered. Based on the presented examples in a pervious study ( [START_REF] Shrouf | Optimizing the production scheduling of a single machine to minimize total energy consumption costs[END_REF]), the machine setup data for all the examined instances in this study are identical and considered as Table . 2.

For each size of the problem, ten instances have been examined. To generate the instances, the unit of energy price in each time-slot, as well as the processing times of the jobs are randomly generated between [START_REF] Fang | Scheduling on a single machine under time-of-use electricity tariffs[END_REF][START_REF] Tasgetiren | Energy-efficient single machine total weighted tardiness problem with sequence-dependent setup times[END_REF] and [START_REF] Fang | Scheduling on a single machine under time-of-use electricity tariffs[END_REF][START_REF] Yildirim | Single-machine sustainable production planning to minimize total energy consumption and total completion time using a multiple objective genetic algorithm[END_REF], respectively. Table . 3 represents the gap between the objective value of each lower bound and the obtained optimal solution by CPLEX software in percentage. These results are presented for the problem smaller than (35, 209) size problem, because the CPLEX software was not able to find the optimal solution for the instances larger than this size during 3 hours or 10800 seconds time limitation. The numerical results have been illustrated by minimum, average and maximum obtained gap value for each problem size. The results show that between LB 1 , LB 2 , and LB 3 , in all the cases LB 2 proposed a better average gap. As can be seen, among these lower bounds, LB 4 which is the obtained optimal solution of the preemptive case of this problem by CPLEX, presents the solutions that are more near to

Gap LB 4 < Gap LB 2 < Gap LB 1 < Gap LB 3
Moreover, an analysis of the variance (ANOVA) with a confidence level of 95% was taken using the Minitab.17 software to check the statistical validity of the results (Fig. 10).

As can be seen in this figure, for each problem size the interval of the gaps for all the proposed lower bounds (LB 1 , LB 2 , LB 3 , LB 4 ) are presented. In all the cases, LB 4 has the minimum interval of the gaps.

Conclusion

Three categories of the energy-efficient single machine scheduling problems, when the machine has several states, are addressed in this study. The complexity of the problems with the same energy price, increasing (decreasing) energy price during all the unlike what the authors considered in [START_REF] Shrouf | Optimizing the production scheduling of a single machine to minimize total energy consumption costs[END_REF], the problem is polynomial. Then, we also proved that for the case without the fixed sequence, when the energy prices are constant or increasing (1, c t = c|states|T EC and 1, c t < c t+1 |states|T EC), these problems are polynomial. But, for the problems with the TOU energy price, when the jobs have different processing times, the problem is NP-hard. Moreover, some lower bounds solution for the 1, T OU|states|T EC problem are presented.

In the future works, it could be interesting to analyze the complexity of other versions of this problem, i.e. when the jobs have different energy consumptions and the machine is able to process the jobs at different speeds. In addition, considering other assumptions such as the release dates and the due dates for each job the setup times for each state, and dealing with a more complex system like job shop, open shop and flow shop systems, with more than one machine can be established in future research.

Figure 1 :

 1 Figure 1: Machine states and possible transitions.

Figure 2 :

 2 Figure 2: An example of the general problem

2 , p 5 2 .

 252 = 3 and e OFF = 0, e ON = 4, e Idle = 2, e Ton = 5, e To f f = 1 is provided in Fig. As can be seen, for this solution λ = 2 (|ϕ OFF | = 12, |ϕ Ton | = 4, |ϕ ON | = 14, |ϕ To f f | =

as 1 ,

 1 T OU|sequence, states|T EC, where TEC represents our objective which is Total Energy consumption Costs and TOU represents Time-Of-Use energy costs. Then, the complexities of several problems without a pre-determined order are also analyzed when there exists a regular trend for the energy prices during two consecutive timeslots, and when the energy prices are irregular. For this purpose, three different problems such as: (1, c t = c|states|T EC), (1, c t < c t+1 |states|T EC), and (1, T OU|states|T EC)

Figure 3 :

 3 Figure 3: The related graph for instance[START_REF] Mouzon | Operational methods for minimization of energy consumption of manufacturing equipment[END_REF][START_REF] Nattaf | Energetic reasoning and mixedinteger linear programming for scheduling with a continuous resource and linear efficiency functions[END_REF]

  we have A 4,11 = {(3, 10), (3, 6), (3, 5)}.

  graph, is used in this study. The worst case implementation of this algorithm runs in O(|E| + |V | log |V |) (|E|: number of the edges and |V |: number of the nodes) which

4. 1 .

 1 pb 2 : 1, c t = c|states|T EC Theorem 1. If the energy price during the horizon time is constant (c t = c; ∀t = 1, ..., T ), the problem (1, c t = c|states|T EC) is polynomial.

F 2

 2 so, for any feasible solution of pb 2 , the expression of the objective function, denoted by F 2 , may be deduced from Equation (4) as: = [(e OFF × |ϕ OFF |) + (e Ton × |ϕ Ton |)+ (e ON × |ϕ ON |) + (e To f f × |ϕ To f f |) + (e Idle × |ϕ Idle |)] × c

Figure 4 :

 4 Figure 4: The possible optimal solutions of pb 2 for an example with T = 25, P = 14, β 1 = 2, β 2 = 1

4. 2 . 2 .

 22 pb 3 : 1, c t < c t+1 |states|T EC Theorem If the energy prices are increasing between two consecutive time-slots (c t < c t+1 ; ∀t = 1, • • • , T -1) and e OFF = 0, the problem (1, c t < c t+1 |states|T EC) is polynomial.

Figure 5 :Figure 6 :

 56 Figure 5: The comparison between solution S i 3 and S 3 of problem pb 3 : case1

Figure 7 :Figure 8 :

 78 Figure 7: The optimal solution for an instance of problem with c t < c t+1 (∀t = 1, • • • , T -1)

5. 1 . 3 .

 13 pb 4 : 1, T OU|states|T EC Theorem If the jobs have different processing times, the Problem (1, T OU|states| T EC) is strongly NP-hard.

Figure 9 :

 9 Figure 9: An example of pb 4 which transfers to a 3-PARTITION problem

Figure 10 :

 10 Figure 10: Performance comparison of the lower bounds with the obtained optimal solutions by CPLEX

Table 1

 1

		: Parameters' values of instance (3,15)
	State	Power consumption (kW) Required period
	ON	6	5={2,1,2}
	OFF	0	-
	Idle	2	-
	Turn on	8	2
	Turn off	1	1

  Lemma 6. LB 3 is a lower bound of pb 4 .Proof. To evaluate C ¯j; ∀ j ∈ {1, • • • , n}, the constraint that the machine can process one job per time-slot is relaxed and the processing order for the jobs is not considered. C ¯OFF , the constraints that the machine must be in just one state per time-slot, and the relationship between different state of the machine are relaxed. On this account, for a feasible solution of pb 4 we have

	each state to its minimum costs possible C ¯j (∀ j ∈ {1, • • • , n}), C ¯Ton , C ¯To f f , C ¯OFF :
		n
	LB 3 = (e OFF × C ¯OFF ) + (e Ton × C ¯Ton ) + (e ON ×	∑ j=1	C ¯j) + (e To f f × C ¯To f f )	(52)
	Moreover, to evaluate C ¯j (∀ j ∈ {1, • • • , n}), C ¯Ton , C ¯To f f , the following relations:
	C
			), (2), and (3), the Idle state
	consumes more than OFF state, that is why, all the remaining non-processing states are
	considered as OFF states. The idea of the third lower bound named LB 3 is to allocate

Table 2 :

 2 Energy consumption profile of a machine. ([START_REF] Shrouf | Optimizing the production scheduling of a single machine to minimize total energy consumption costs[END_REF])

	States and transitions Power consumption required time-slots
	ON	4 kW	∑ process times
	OFF	0 kW	-
	Idle	2 kW	-
	Toff	1 kW	1
	Ton	5 kW	2
	problem (1, T OU|states, pmtn|T EC) which is a subproblem of pb 4 , is polynomial. As
	a consequence, it's optimal solution may be used as the fourth lower bound (LB 4 ) of
	this problem.

Table 3 :

 3 The comparison results between the proposed lower bounds and obtained optimal solutions by CPLEX in percentage (n,T)Gap LB 1 Gap LB 2 Gap LB 3 Gap LB 4time-slots, and TOU energy price, with the objective of the total energy consumption costs minimization (T EC), are analyzed. First of all, we proved that when the jobs' sequence is fixed and TOU energy price is considered (1, T OU|sequence, states|T EC),

		Min	19.41	8.14	18.94	0.00
	(5,30)	Average	39.79	27.70	39.65	0.07
		Max	54.75	40.68	56.00	0.37
		Min	20.15	13.31	42.53	0.00
	(10,50) Average	33.66	26.44	50.27	2.90
		Max	50.35	43.94	62.13	11.59
		Min	20.02	14.51	47.44	0.00
	(15,70) Average	28.76	23.52	57.10	0.00
		Max	35.60	30.88	68.39	0.00
		Min	15.52	11.05	53.20	0.00
	(20,90) Average	29.83	25.43	57.38	0.00
		Max	36.03	31.23	62.37	0.00
		Min	25.96	22.44	44.55	0.00
	(25,110) Average	30.29	26.59	56.68	0.00
		Max	34.27	30.65	70.64	0.00
		Min	20.29	17.10	54.55	0.00
	(30,130) Average	25.45	22.51	60.67	0.00
		Max	28.29	25.98	71.42	0.00
		Min	24.34	22.57	48.42	0.00
	(35,209) Average	27.27	25.48	53.58	3.11
		Max	30.68	28.91	61.46	5.17
	Average		30.72	25.38	53.62	0.87

2, |ϕIdle | = 0).

feasible lower bound of this problem (pb 3 ), and S 3 is the optimal solution. So, in the optimal solution, the machine must be in Ton state from time-slot 1 to β 1 .

for the jobs is NP-hard, is used for our problem.

Given positive integers {a 1 , a 2 , • • • , a 3t , b}, such that:

3t

The following instance of pb 4 (equations (36) to (39)), with n = 3t jobs and T = tb + t + 3 time-slots can be constructed. The machine consumes the units of energy just when it is in state ON (e ON = 0). Moreover, the unit of energy price in some time-slots (tb time-slots) equals to 0, and for the rest (t + 3 time-slots) is equal to c (c > 0):

Let us consider a decision problem that searches a solution with the total energy consumption costs equal to 0. A schedule with total energy costs of 0 (T EC = 0), exists if and only if, the machine is in one of the states that consume 0 unit of energy during the time-slots with c t = c, and it is in state ON when c t = 0. This can be achieved if and only if, all the 3t jobs are partitioned over the t intervals with the length of b time-slots.