By

*Daniel Morillo Torres, Federico Barber, and Miguel A. Salido*

Instituto de Automática e Informática Industrial,

Universidad Politécnica de Valencia, Valencia, Spain

### Abstract

The study of scheduling problems is one of the core areas in the planning and development of any project. Currently, researchers effort is addressed to optimize the task scheduling considering the energy consumption. In this paper a bi-objective MRCPSP (Multi-Mode Resource-Constrained Project Scheduling Problem)-ENERGY is proposed and transformed into a single-objective problem which takes into account both energy consumption and the *makespan*. Thus, the PSPLIB benchmark library is extended (called PSPLIB-ENERGY) to include energy consumption to each uni-modal RCPSP (Resource Constrained Project Scheduling Problem) instance, through a realistic mathematical model. This extension provides an alternative to the current trend of numerous researches about optimization and manufacturing field, which requires the inclusion of components to reduce the environmental impact in the decision making process. The PSPLIB-ENERGY is available at http://gps.webs.upv.es/psplib-energy/

### Introduction

One of the main challenges in industry is to properly allocate available resources to tasks in order to optimize an objective function (usually *makespan*). The current trend is oriented towards obtaining efficient and sustainable solutions. Thus, the analysis and development of new methodologies for optimizing these problems including energy consumption have taken on greater importance in the last decades [1].

There are different strategies for energy optimization in manufacturing processes. These strategies can be classified into two levels: machine tool level and manufacturing system level [2]. The first level refers to improve the process taking into account the machine design, from a technological point of view [3, 4]. The second model emphasizes the energy optimization through the management and allocation of tasks and resources with the objective of minimizing energy requirements [5, 6]. Energy optimization at this level has a great importance and provides several improvement opportunities [7].

A Multi-Mode Resource Constrained Project Scheduling Problem (MRCPSP) is considered one of most important scheduling problems. These problems are well-known NP-hard problems, where relatively small instances are highly complex and it is not possible to find an optimal solution within a reasonable time.

This paper focuses on optimizing both makespan and energy efficiency in MRCPSP at manufacturing system level, by combining makespan and energy consumption as a single-objective function. Thus, MRCPSP-ENERGY is introduced, where the activities have different energy consumption to be executed at different rates. The objective is to minimize both makespan and energy consumption. Moreover, an extension of the well-known PSPLIB library (Project Scheduling Problem Library) [8] is proposed. This extension is made by associating an energy consumption to each activity in the traditional RCPSP library. This new library, called PSPLIB-ENERGY contains sets of instances for the MRCPSP-ENERGY.

### MRCPSP-ENERGY: A MRCPSP extension for using efficiently energy

Formally, the standard MRCPSP can be defined as follows: A project consists of a set I of n activities I = {1,…,i,…,n}, a set B of K^{ρ} shared renewable resources B = {1,…,b,…K^{ρ}} available in R_{b}^{ρ} units, and a set K of K^{ν} shared non-renewable resources K = {1,…,k,…K^{ν}} available in R_{k}^{ν} units. Each activity i ∈ I holds m = {1,…,M} execution modes and a non-preemptive execution time d_{im}, requires r_{imb}^{ρ} units for every renewable resource b and r_{imk}^{ν} units for every non-renewable resource k. Generally, activities 1 and n are dummy activities that represent the start and the end of a project. Activities are subject to precedence constraints. Thus, an activity can not be started before all its predecessors activities are completed. The objective is to minimize the total duration of the project. The traditional mixed integer linear programming formulation can be found in [9].

Kolisch and Sprecher [8] proposed the PSPLIB library for assessing new developed methods that solve the RCPSP and MRCPSP by providing standard sets of trial cases. When the optimal solution is known, it can be calculated the average deviation regarding the optimal. Otherwise, an error is calculated based on the length of the critical path with the lowest execution time of each activity, called the deviation to LB0

This paper focuses on the MRCPSP considering only renewable resources to propose the MRCPSP-ENERGY. The analysis between energy consumption and makespan in scheduling is outlined below.

It is assumed that energy is a resource consumed by activities. As usually occurs in the machinery of materials, energy consumption of activities is independent of when they are scheduled [10]. Generally, as the energy consumption of an activity increases, its processing time decreases. Typical examples are lathes, milling machines, rolling stock, elevators, etc. [4, 11]. Hence, here it is assumed a similar energy behavior for MRCPSP activities. Finally, the total energy consumption of a project (CETP_{w}) can be calculated by using expression (1), where e_{im} is the energy consumption for an activity i executed in mode m.

#### Project efficiency: optimization criterion in MRCPSP-ENERGY

In this section, an efficiency-based criterion is proposed. MRCPSP-ENERGY requires a bi-objective criterion that simultaneously minimizes both makespan (as the usual MRCPSP’s criterion) and energy consumption. In literature, when managing two objectives, a Pareto front is generated, but it is unsuitable to make a fair performance comparison since the operator must decide the weight to assign to each objective. The efficiency concept tries to give us a better solution for the whole system without influencing the significance of the objectives.

Generally, the concept of efficiency can be defined as the ratio between the energy supplied and the transformed energy delivered. For example, in manufacturing machine operations (like milling, turning, drilling, etc.), the theoretical efficiency of an electric motor is the conversion of electrical energy into mechanical energy. This is represented by expression (2), where η is the efficiency, P_{mechanical} represents the energy output from the motor shaft and P_{electrical} is the energy absorbed [12].

The expression (2) is a theoretical efficiency, which cannot reach a value 1, because of energy losses, mostly in the form of heat. The efficiency is characterized by an initial increasing curve until it reaches a horizontal asymptote (see Figure 1.a), some efficiency curves of different processes maintain the same trend. Theoretical behavior of efficiency is different in real practice, where efficiency decreases after reaching a maximum. For instance, Figure 1.b shows the efficiency performance of a real 4kw electric motor [12].

When energy is supplied to a motor, the output is mechanical energy. Meanwhile, the output for a project in which activities are carried out by machines or people, should be an duration affected by the amount of energy. The more energy, the less duration until the highest reduction is obtained, and then, more input might cause the machines work slower for overload, as it occurs in figure (1.b). The expression (3) describes this behavior for the duration d_{i} and the energy consumption e_{i} of an activity, but the range is not necessarily between 0 and 1.

The previous concept can be extended to an entire project, expression (4). Nonetheless, as this relation is also out of 0 – 1 cannot be considered yet as an efficiency. If the optimal values of makespan and energy consumption were known, expression (4) could be standardized, but these values are unknown. Therefore, they are approximated by two lower bounds: emin_{w} and LB0min_{w}, respectively. The first is computed as (∑ _{i=1}^{n}e_{i1}) where e_{i1} is the minimum energy consumption of activity i. The second is estimated by using the critical path method, considering the minimum processing time of each activity i within its m modes. In this way, an upper bound of the project performance CSR_{w} can be calculated to standardize expression (4). The expression (5) shows how to calculate CSR_{w}. It can be interpreted as the ideal efficiency of a project.

The expression (6) shows expression (4), now standardized. It is defined as the relative efficiency of the project w with respect to ideal.

On the basis of the above concepts, MRCPSP-ENERGY can be defined as follows:

Definition 1: MRCPSP-ENERGY is a project that consists of a set of n activities I = {1,…,i,…,n}, a set B of K^{ρ} shared renewable resources B = {1,…b,…K^{ρ}}, and there is an available amount R_{b}^{ρ} of every renewable resource. Each activity i holds m = {1,…,M} execution modes and a non-preemptive execution time d_{im}, requires a total of r_{ib} renewable resource of type b and an amount of energy e_{im} for its realization. Activities are subject to precedence constraints, which indicate that each activity can not be started before all its predecessor activities are completed. The different energy consumptions for an activity give rise to different execution modes. Thus, MRCPSP-ENERGY is similar to a RCPSP where the activities have different execution modes, associated to different energy consumptions.

The main differences with respect to a traditional MRCPSP are: (1) modes depend entirely on energy consumption e_{im} and the relation between energy consumption and processing time is inverse and (2) the objective is to maximize the project efficiency, which means to minimize both energy consumption and makespan.

The formal mathematical model of the MRCPSP-ENERGY maintains the same constraints than MRCPSP [9] without the non-renewable resources constraints and the objective function is reformulated according to the expression (7).

### PSPLIB-ENERGY: An extension of PSPLIB library

In this section the PSPLIB-ENERGY library is proposed. It complements the PSPLIB with different levels of energy consumptions and processing times associated to each activity. This extension aims to evaluate search methods for optimizing the MRCPSP-ENERGY, taking into account both makespan and energy consumption, by using the proposed efficiency-based criterion.

#### Model proposed for energy consumption

For expanding the PSPLIB library it is necessary that the values of energy consumption for activities and their corresponding processing times to be consistent with the behavior of real machines. For this purpose, a standard value of energy consumption e_{i} and a processing time d_{i} for each activity is assigned a priori. Afterward, a mathematical model relates the standard values with every mode of an activity to compute its value of energy consumption and processing time.

In machining, there is not a global mathematical model that describe all behaviors of energy consumptions in machine tools. This is due to the fact that energy consumption behavior depends on several technical factors. Nevertheless, the behavior is quite similar in most machines. The relationship between energy consumption and processing time of machining has a decreasing trend [10]. In this way, it proposes the expression (8), where t_{i}(c_{i}) is the proportion of processing time compared with the standard duration of the activity i, and c_{i} is the proportion of energy consumption compared with the standard consumption of the activity i. The expression (8) has a decreasing trend in a similar way to that of the energetic behavior on machine tools. This function represents an approximation of the efficiency model proposed in the previous section. The values of the constants A_{1} = 4.0704 and A_{2} = 2.5093 center the function in c_{i} = 1(100%) and t_{i} = 1(100%), representing the standard of the energy consumption and the processing time, respectively. As example, a value of c_{i} = 1,6(160%) represents a consumption of 60% of additional energy for activity i, and an obtained value t_{i} = 0,67(67%) represents a decrease of 33% in the processing time of the activity i. Figure 2-a) shows the graph of the expression (8).

As a result of previous energy-time model, expression η_{i}(c_{i}) (9) is defined as the relative efficiency of the activity i depending on c_{i}. This expression can be interpreted as the efficiency percentage of the activity i respect to its efficiency, when both standard energy and standard processing time are used. For instance, a η_{i}(c_{i}) = 130% indicates that, given a proportion of energy consumption c_{i}, an efficiency of 30% higher than the standard is obtained. Figure 2-b) shows the relative efficiency expression (9). It is important to note how the trend of the curve is similar to the real efficiency shown in figure 1.

#### Energy extension for PSPLIB

To extend the PSPLIB to PSPLIB-ENERGY, it includes energy consumption and processing time to each activity in the uni-modal RCPSP instances, through the mathematical model described above (expression 8). Thus, the four problems sets: j30,j60j90 and j120 were created. With 30, 60, 90, and 120 activities, respectively. Each of them with 480 instances, except the last one that have 600 instances. The values of the standard efficiency of each instance are available on the PSPLIB-ENERGY library.

Without loss of generality, three specific values for energy consumption e_{im} were taken. Thus, three modes are defined. The first mode (c_{i1} = 0.8) corresponds to a decrease of 20% in the energy consumption related to the standard value e_{i2}. The second mode (c_{i2} = 1) has the standard value of energy consumption e_{i}^{std} = e_{i2} which corresponds to the standard duration d_{i}^{std} = d_{i2} provided by the original PSPLIB library. The third mode (c_{i1} = 1.2) corresponds to an increase of 20% in energy consumption related to the standard value e_{i2}.

The corresponding values of processing time (d_{im}) and energy consumptions (e_{im}) can be calculated using expressions (10) and (11), respectively. The values of t_{i}(c_{im}) are calculated using expression (8).

The values of e_{i}^{sdt} are defined by assigning to each activity on the PSPLIB-ENERGY library a random consumption value that range in [1,10]. This ranges of values was proposed considering the same intervals used for the original parameters on the PSPLIB library. As all parameter values in the PSPLIB library are integers, the values of the parameters for PSPLIB-ENERGY library are also integers.

For the evaluation of further developed techniques using the PSPLIB-ENERGY library, the criteria is to maximize the relative efficiency presented in expression (6). This expression takes into account both makespan_{w} and the energy consumption CETP_{w} (expression 1) in a single-objective.

To calculate the average value j30, j60, j90 or j120 on PSPLIB-ENERGY, the expression (12) is defined, where nP is the number of evaluated projects.

for the problems of the sets### An example of a MRCPSP-ENERGY instance

In this section, an example of a small MRCPSP-ENERGY instance is presented. This instance consists of n = 8 activities and B = 3 renewable resources. Figure 3 shows the energy consumption (e_{im}), the processing time (d_{im}) and the resource usage (r_{imb}^{ρ}).

Figure 4 shows three Gantt charts of three solutions for the given instance. Figure 4.a shows an optimal solution when the problem only uses a proportion of energy consumption c_{i} = 100%. Figure 4.b and Figure 4.c represent two solutions using different energy consumption, and consequently, different processing times.

To calculate the efficiency η_{w} of each solution, the values LB0_{w} = 6 and emin_{w} = 21 were calculated from Figure 3. Figure 4 shows the upper level of project performance CSR_{w}, the value of the total project duration makespan_{w}, the total energy consumption of the project CETP_{w} and the value of the evaluation criterion η_{w} for three different solutions.

The solution (a) has the lowest value of efficiency η_{a} = 38,2%. The lowest makespan is achieved in solution (c). However it has the highest energy consumption so its efficiency is η_{c} = 41,1% and it is considered better than solution (a). The solution (b) maintains the same energy consumption than solution (a) but improves in makespan so it achieves the highest value of the relative efficiency of the project η_{b} = 42%. Thus, the solution (b) is considered to be the best solution of the three ones.

It is noteworthy that the efficiency values are relatively low in all cases (close to 40%), because they are compared with the ideal value of the upper bound of project performance CSR_{w}.

### Conclusions

Currently, many researches follow the strong trend to develop models that include an energy component for obtaining sustainable solution to scheduling problems. As a result, it is necessary to develop new libraries to evaluate the behavior of further developed heuristics.

A single-objective MRCPSP efficiency-based criterion has been proposed. It is called MRCPSP-ENERGY, which includes the energy consumption in a scheduling problem. The proposed approach consists in maximizing the relative project efficiency. This is carried out by minimizing simultaneously the makespan and the energetic consumption. The efficiency concept tries to find the best solution for the system as a whole and to avoid the generation of the Pareto front. Whereas the activities can be done with different modes, each with different energy consumption, the obtained results show that can be obtained more energy efficient solutions.

Therefore, the PSPLIB-ENERGY library is proposed. This library introduces a new set of test cases where new computational methods can be tested for efficient resolution of MRCPSP with the combined objectives of energy efficiency and makespan. PSPLIB-ENERGY is supported by a proposed model of energy consumption, which is consistent with surveys reported in the academic literature about energy consumption for machines. It has been developed keeping the same format than PSPLIB library, with four sets of problems (j30, j60, j90 and j120), every of those with 480 problems, except the set j120, with 600 instances. This library is available at http://gps.webs.upv.es/psplib-energy/.

### References

[1] Rahimifard S, Seow Y and Childs T. Minimising Embodied Product Energy to support energy efficient manufacturing. CIRP Annals – Manufacturing Technology 2010; 59(1): 25–28.

[2] Salonitis K and Ball P. Energy Efficient Manufacturing from Machine Tools to Manufacturing Systems. Procedia CIRP 2013; 7: 634–639.

[3] Seow Y and Rahimifard S. A framework for modelling energy consumption within manufacturing systems. CIRP Journal of Manufacturing Science and Technology 2011; 4(3): 258–264.

[4] Li L, Yan J and Xing Z. Energy requirements evaluation of milling machines based on thermalequilibrium and empirical modelling. Journal of Cleaner Production 2013; 52: 113–121.

[5] Salido M, Escamilla J, Giret A et al. A genetic algorithm for energy-efficiency in job-shop scheduling. The International Journal of Advanced Manufacturing Technology 2016; 85(5): 1303–1314.

[6] Niu S, Ong S and Nee A. An improved intelligent water drops algorithm for solving multi-objective job shop scheduling. Engineering Applications of Artificial Intelligence 2013; 26(10): 2431–2442.

[7] Duflou JR, Sutherland JW, Dornfeld D et al. Towards energy and resource efficient manufacturing: A processes and systems approach. CIRP Annals – Manufacturing Technology 2012; 61(2): 587–609.

[8] Kolisch R and Sprecher A. PSPLIB – A project scheduling library. European Journal of Operational Research 1996; 96: 205–216.

[9] Talbot FB. Resource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case. Management Science 1982; 28(10): 1197–1210.

[10] Oberg E, Jones FD, Horton HL et al. Machinery’s Handbook. 27 ed. New York, USA: Industrial Press Inc., 2004. ISBN 0-8311-2737-6.

[11] Fang K, Uhan N, Zhao F et al. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. Journal of Manufacturing Systems 2011; 30(4): 234–240.

[12] Boglietti A, Cavagnino A, Lazzari M et al. International Standards for the Induction Motor Efficiency Evaluation: A Critical Analysis of the Stray-Load Loss Determination. IEEE Transactions on Industry Applications 2004; 40(5): 1294–1301.

[13] Beggs C. Energy: management, Supply and Conservation. Butterworth Heinemann, 2002. ISBN 0750650966.