Sage Journals: Discover world-class research

Abstract

This article focuses on obtaining sustainable and energy-efficient solutions for limited resource programming problems. To this end, a model for integrating $makespan$ and energy consumption objectives in multi-mode resource-constrained project scheduling problems (MRCPSP-ENERGY) is proposed. In addition, a metaheuristic approach for the efficient resolution of these problems is developed. In order to assess the appropriateness of theses proposals, the well-known Project Scheduling Problem Library is extended (called PSPLIB-ENERGY) to include energy consumption to each Resource-Constrained Project Scheduling Problem instance through a realistic mathematical model. This extension provides an alternative to the current trend of numerous research works about optimization and the manufacturing field, which require the inclusion of components to reduce the environmental impact on the decision-making process. PSPLIB-ENERGY is available at http://gps.webs.upv.es/psplib-energy/.

Keywords

MRCPSP PSPLIB energy consumption sustainable scheduling metaheuristic genetic algorithms

Introduction

One of the main challenges in industry is to optimally carry out the process of decision-making. The current trend in various academic areas is oriented toward environmental awareness.^1–3 More precisely, in the last decade, eco-efficiency solutions have taken a relevant position in firms due to pressures from government regulators, community activists, global competition, and non-governmental organizations.⁴ As a consequence, the need for measuring the impact of sustainable solutions has increased since then.⁵

In the artificial intelligence field, as well as in operations research, there is a subset of characteristic problems called scheduling problems, whose objective is to properly allocate available resources to the activities in order to optimize an objective function that is usually related to time (e.g. the total execution time of the project ( $makespan$ ), tardiness, and maximum lateness).⁶ Resources can be machines, materials, people, money, time, and so on. These problems have great importance in industry due to their applications in different fields such as production, distribution, transportation, project management, and supply-chain optimization in general. Currently, the research effort is focused on analyzing and developing new methodologies for the optimal allocation of resources to minimize both $makespan$ and energy consumption.^7,8

In general, scheduling problems are combinatorial optimization problems. Therefore, relatively small instances are highly complex, with most of them being categorized as NP-hard (non-deterministic polynomial-time hard), such as the job shop scheduling problem (JSP), the flow shop scheduling problem (FSP), and the multi-mode resource-constrained project scheduling problem (MRCPSP). Therefore, due to inherent complexity, it is not possible to find an optimal solution in a reasonable period of time. However, these problems show great applicability to real-world situations. Hence, the research community is constantly developing and improving the techniques and methods to solve these problems. Similarly, benchmark libraries are needed to compare and evaluate these algorithms in an empirical way.

The MRCPSP is considered to be one of the most important scheduling problems.⁹ All benchmarks and most algorithms that have been developed to solve this problem have focused on minimizing $makespan$ . However, there are few studies about optimizing energy consumption in MRCPSP.

There are two main contributions of this article. The first one is to propose a specific resource-constrained scheduling problem that takes into account both energy consumption and $makespan$ in order to optimize the project in an efficient way. The second one is to provide a test instance library to compare different algorithms to solve the proposed problem.

Thus, this work is focused on analyzing the MRCPSP in order to propose MRCPSP-ENERGY, which is a single-objective problem where the activities have different energy consumptions to be executed at different rates. The objective is to minimize both $makespan$ and energy consumption. Furthermore, an extension of the most commonly used library to solve the MRCPSP, the PSPLIB (Project Scheduling Problem Library),¹⁰ is proposed. To this end, a mathematical model to relate the energy consumption and the processing time of activities is proposed. Thereby, the instances of the PSPLIB are extended by associating an energy consumption with each activity of the RCPSP (Resource-Constrained Project Scheduling Problem). This new library, called PSPLIB-ENERGY, is available at http://gps.webs.upv.es/psplib-energy/. Finally, a genetic algorithm for solving these instances is proposed to compare the performance of new algorithms. It is based on the heuristic methodologies that produce the best results for solving the MRCPSP.

Literature review

There are different strategies for energy optimization in manufacturing processes. These strategies can be classified into two levels: the machine tool level and manufacturing system level.¹¹ The first level refers to improving the process taking into account the machine design that performs the operation from a technological point of view.^12–14 For a comprehensive review about this first level, we refer the reader to Moradnazhad and Unver.¹⁵ The second level emphasizes energy optimization through the management and allocation of the activities and resources with the objective of minimizing energy requirements.^1,16,17 Energy optimization at this level is of great importance and provides several improvement opportunities.^18,19 This work focuses on this second level to minimize $makespan$ and energy consumption as a single-objective function.

For the manufacturing system level, there are several studies that deal with scheduling optimization taking into account energy consumption, both from a general point of view, by analyzing general scheduling problems as well as from a specific perspective by applying them to specific manufacturing areas. Among these research studies, one of the most important ones was proposed by Mouzon et al.¹ They developed a multi-objective model for minimizing both the energy consumption and $makespan$ of a single machine scheduling problem. They found that it is possible to save up to $80 %$ of energy when non-bottleneck machines were turned off until needed during the period of next job arrival. Fang et al.²⁰ developed a new approach to schedule a flow shop problem in manufacturing for power consumption and carbon footprint reduction. Bruzzone et al.¹⁶ provided an energy-aware mathematical model for the flexible flow shop problem to modify a given schedule in order to account for peaks of power. Artigues et al.²¹ analyzed an industrial case study, which led to a generic problem called the Energy Scheduling Problem. It consists of scheduling a set of activities which have a required total energy and have to be processed using a constrained energy resource. The energy amount used by an activity can be different for each period of time. Activities have a release date and deadline. Furthermore, they have a minimum and maximum energy consumption. The goal is to find the start time of each activity. Luo et al.²² proposed a new ant colony optimization for solving a hybrid FSP taking into account machine electricity consumption cost.

More recently, Okubo et al.²³ proposed a model that can deal with energy consumption during the setup operation on the RCPSP using partially renewable resources. Zhang et al.²⁴ proposed a mathematical formulation for minimizing the energy consumption of a machining system by integrating planning and scheduling. The solution method was a genetic algorithm. That model considers a set of jobs with few alternative process plans and a set of machines. Each job is loaded and processed according to the predetermined sequence of operations in the process plan. Thus, the objective is to find the optimal process plan and machine allocation for each job. Li et al.²⁵ proposed a multi-objective mathematical model for the permutation flow line scheduling problem in order to simultaneously minimize the total flow time and the energy consumption. Since this problem has an NP-hard complexity, they adapted the non-dominated sorting genetic algorithm II to solve it.

However, there are few studies that consider energy efficiency or provide a common benchmark where these methods can be evaluated. Specifically, the MRCPSP under energy efficiency optimization has not been studied in great depth, and there is no common benchmark that includes both $makespan$ and energy consumption. Therefore, the library proposed in this article is a clear contribution to the evaluation of energy efficiency–based solutions to the MRCPSP.

However, different metaheuristic strategies to solve the MRCPSP have been proposed. These are mainly based on genetic algorithms, scatter search, simulated annealing, and particle swarm optimization, among others. According to computational experiments from academic literature, the population-based heuristics are those that achieve the best results. For an extensive review of the most relevant methodologies, we refer the reader to Dai et al.²⁶ and Kolisch and Hartmann.²⁷

Description of the MRCPSP

Formally, the standard MRCPSP can be defined as follows.²⁸ A project consists of a set $I$ of $n$ activities $I = {1, \dots, i, \dots, n}$ , a set $B$ of $K^{ρ}$ shared renewable resources $B = {1, \dots, b, \dots, K^{ρ}}$ , and there is a maximum amount $R_{b}^{ρ}$ of every renewable resource. There exists a set $K$ of $K^{ν}$ shared non-renewable resources $K = {1, \dots, k, \dots, K^{ν}}$ , and there is a maximum amount $R_{k}^{ν}$ of every non-renewable resource. A list of all the symbols used in this article is included in Appendix 1.

Each activity $i \in I$ has $m = {1, \dots, M}$ execution modes and a non-preemptive execution time $d_{im}$ , which requires a total $r_{imb}^{ρ}$ renewable resource of each type $b$ and a total $r_{imk}^{ν}$ non-renewable resource of each type $k$ for its realization. Generally activities $1$ and $n$ are dummy activities and their duration and resource consumption are zero, representing the start and end of the project. Activities are subject to precedence constraints, which indicate that each activity cannot be started before all its predecessor activities are completed. The objective is to minimize the total duration of the project.

The MRCPSP is a well-known NP-hard problem.²⁹ It can be modeled as a mixed-integer linear programming formulation which is detailed in expressions (1)–(6). The decision variables $ξ_{imt}$ take the value 1 when the activity $i$ is executed in mode $m$ and finishes at time $t$ , and 0 otherwise. It is noteworthy that this formulation needs time intervals: an early start time and a late start time $[e s_{i}, l s_{i}]$ for each activity by computing an upper bound and applying the method of forward pass and backward pass with the lowest execution time of activities.

Expression (1) shows the optimization function where the objective is to minimize the finish time of the last activity $(n)$ . Expression (2) ensures that each activity starts only once. Expression (3) represents the precedence constraints, and the set $P_{i}$ contains the immediate predecessor activities of activity $i$ . Expressions (4) and (5) ensure that the capacity of each type of resource is not exceeded

Min : \sum_{t = e s_{n}}^{l s_{n}} t * ξ_{n 1 t}

(1)

Subject to

\sum_{m = 1}^{M} \sum_{t = e s_{i}}^{l s_{i}} ξ_{imt} = 1 \forall i \in I

(2)

\sum_{m = 1}^{M} \sum_{t = e s_{j}}^{l s_{j}} t * ξ_{j m t} \leq \sum_{m = 1}^{M} \sum_{t = e s_{i}}^{l s_{i}} (t - d_{i m}) * ξ_{i m t} \forall j \in P_{i}, \forall i \in I

(3)

\sum_{i = 0}^{n} \sum_{m = 1}^{M} r_{i m b}^{ρ} * \sum_{s = m a x {t - d_{i m}, e s_{i}}}^{m i n {t - 1, l s_{i}}} ξ_{i m s} \leq R_{b}^{ρ} \forall b \in B; \forall i \in I

(4)

\sum_{i = 0}^{n} \sum_{m = 1}^{M} r_{imk}^{ν} * \sum_{t = e s_{i}}^{l s_{i}} ξ_{imt} \leq R_{k}^{ν} \forall k \in K

(5)

ξ_{imt} \in {0, 1}

(6)

Kolisch and Sprecher¹⁰ proposed a generator algorithm of instances for the uni-modal and multi-modal RCPSP (ProGen, http://www.om-db.wi.tum.de/psplib/main.html). The set of generated instances was grouped into the PSPLIB. The purpose of this library is to provide a common set of test cases to evaluate the efficiency of newly developed methods to solve the RCPSP and the MRCPSP, and it has become a reference point for researchers of these problems. The test cases for the RCPSP consist of four sets ( $j 30$ , $j 60$ , $j 90$ , and $j 120$ ), each of which has $480$ instances (except the set $j 120$ , which has $600$ instances), and the test cases for the MRCPSP consist of seven sets ( $j 10$ , $j 12$ , $j 14$ , $j 16$ , $j 18$ , $j 20$ , and $j 30$ ), each of which has $640$ instances, with some of them being infeasible. For instances where the optimal solution is known, the average deviation regarding the optimal can be calculated. For those sets of problems whose optimal solution is unknown, the error is calculated based on the length of the critical path with the lowest execution time of activities, which is called the deviation to $LB 0$ .

MRCPSP-ENERGY: a MRCPSP extension for energy efficiency

This article focuses on the MRCPSP considering only renewable resources to propose MRCPSP-ENERGY, which incorporates energy consumption that allows the execution time of jobs to be changed. The analysis between energy consumption and $makespan$ in scheduling is outlined below.

It assumes that energy is a resource consumed by activities. As usually occurs in the machinery of materials, the energy consumption of activities is independent of when the activities are scheduled.³⁰ Generally, the greater the energy consumption of an activity, the shorter the processing time of it. Typical examples are lathes, milling machines, rolling stock, and elevators.^13,20 Hence, here a similar energy behavior for MRCPSP activities is assumed. Finally, the total energy consumption of a project $(CET P_{w})$ can be calculated by expression (7), where $e_{im}$ is the energy consumption of activity $i$ executed in mode $m$

CET P_{w} = \sum_{i = 1}^{n} e_{im}, m \in {1, 2, \dots, M}

(7)

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 criterion) and energy consumption. In the literature, when managing two objectives, a convex combination is normally used to generate the Pareto front; however, it is not appropriate for making a fair performance comparison between them since the weights of both objectives may vary from one method to another. Grouping them into a single objective that is related to the concept of efficiency allows us to obtain 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 of the energy supplied to a process to the transformed energy that it delivers. For example, in manufacturing machine operations (e.g. like milling, turning, and drilling), the theoretical efficiency of an electric motor is the conversion of electrical energy into mechanical energy. This is represented by expression (8), where $η$ is the efficiency, $P_{mechanical}$ represents the energy output from the motor shaft, and $P_{electrical}$ is the energy absorbed³¹

η = \frac{P_{mechanical}}{P_{electrical}} = \frac{P_{mechanical}}{P_{mechanical} + \sum losses}

(8)

Expression (8) represents a theoretical efficiency, which cannot reach a value $1$ because, during the transformation of electricity to mechanical energy, there are always losses, mostly in the form of heat. These losses tend to increase as the electrical energy consumption increases.³² Therefore, efficiency is characterized by an initial increasing curve until it reaches a horizontal asymptote (see Figure 1(a)). Different efficiency curves of different processes or machines maintain the same trend, varying according to the technical specifications of each machine. The theoretical behavior of efficiency is different from the real one since the real behavior of efficiency decreases after reaching a maximum. For instance, Figure 1(b) shows the efficiency performance of a real 4-kW electric motor.³¹

Figure 1.

(a) Theoretical efficiency of an engine³³ and (b) real efficiency of a motor.³¹

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 a duration that is affected by the amount of energy. The more the energy, the shorter the duration until the highest reduction is obtained and then more input might cause the machines to work slower due to overload, as occurs in Figure 1(b). Expression (9) 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$

η'_{i} (e_{i}) = \frac{1 / d_{i} (e_{i})}{e_{i}}

(9)

The previous concept can be extended to an entire project (expression (10)). Nonetheless, as this relation is outside of the interval $[0 - 1]$ , it cannot yet be considered an efficiency value. If the optimal values of $makespan$ and energy consumption were known, expression (10) could be standardized, but these values are unknown. Therefore, they are approximated by two lower bounds: $emi n_{w}$ and $LB 0 mi n_{w}$ , respectively. The first one is computed as $(\sum_{i = 1}^{n} e_{i 1})$ where $e_{i 1}$ is the minimum energy consumption of activity $i$ . The second one is estimated 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 $CS R_{w}$ can be calculated to standardize expression (10). Expression (11) shows how to calculate $CS R_{w}$ . It can be interpreted as the ideal efficiency of a project

η_{w}^{*} = \frac{1 / makespa n_{w}}{CET P_{w}}

(10)

Expression (12) standardizes expression (10) by dividing it by expression (11). It is defined as the relative efficiency of the project $w$ with respect to an ideal efficiency value

CS R_{w} = \frac{1 / LB 0 mi n_{w}}{emi n_{w}}

(11)

η_{w} (makespa n_{w}, CET P_{w}) = \frac{1}{CS R_{w}} * \frac{1 / makespa n_{w}}{CET P_{w}}

(12)

As pointed out above, the energy consumption of a project is the sum of the energy consumptions of its activities. However, it is important to remark that project efficiency is not equal to the sum of the efficiencies of its activities. The reason is that the $makespan$ of a project (which represents the inverse of $P_{mechanical}$ of the project) is not the sum of the durations of its activities.

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, \dots, i, \dots, n}$ , a set $B$ of $K^{ρ}$ shared renewable resources $B = {1, \dots, b, \dots, K^{ρ}}$ , and there is an available amount $R_{b}^{ρ}$ of every renewable resource. Each activity $i$ has $m = {1, \dots, M}$ execution modes and a non-preemptive execution time $d_{im}$ , requiring a total of $r_{ib}$ renewable resources of type $b$ and an amount of energy $e_{im}$ for its realization. Activities are subject to precedence constraints, which indicate that each activity cannot be started before all its predecessor activities are completed. The different energy consumptions of an activity give rise to different execution modes. Thus, MRCPSP-ENERGY is similar to the RCPSP, where the activities have different execution modes that are associated with different energy consumptions.

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

The formal mathematical model of MRCPSP-ENERGY maintains the same constraints as the MRCPSP (constraints (2)–(6)), without the non-renewable resource constraints (5). The objective function for PSPLIB-ENERGY is reformulated according to expression (13)

Max : η_{w} (makespa n_{w}, CET P_{w})

(13)

PSPLIB-ENERGY: an extension of the PSPLIB

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

The proposed model for energy consumption

In order to expand the PSPLIB, the values of energy consumption for activities and their corresponding processing times must be consistent with the behavior of real machines. For this purpose, a standard value of energy consumption $e_{i}$ and 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 no global mathematical model that describes all behaviors of energy consumptions of 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 in machining has a decreasing trend.³⁰ Thus, expression (14) is proposed, where $t_{i} (c_{i})$ is the proportion of processing time compared with the standard duration of activity $i$ , and $c_{i}$ is the proportion of energy consumption compared with the standard consumption of activity $i$ . Expression (14) has a decreasing trend in a way similar to the energetic behavior in machine tools. This function represents an approximation of the proposed efficiency model 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 an example, a value of $c_{i} = 1.6 (160 %)$ represents a consumption of $60 %$ of additional energy for activity $i$ , and a value of $t_{i} = 0.67 (67 %)$ represents a decrease of $33 %$ in the processing time of activity $i$ . Figure 2 shows the graph of expression (14)

t_{i} (c_{i}) = \frac{A_{1} * \ln (2)}{\ln (1 + {(c_{i} * A_{2})}^{3})}

(14)

Figure 2.

The proportion of processing time in relation to proportion of energy consumption (expression (14)).

As a result of the above energy–time model, $η_{i} (c_{i})$ (expression (15)) is defined as the relative efficiency of activity $i$ depending on $c_{i}$ . This expression can be interpreted as the efficiency percentage of activity $i$ with respect to its efficiency, when both standard energy and standard processing time are used. For instance, $η_{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 3 shows the relative efficiency (expression (15)). It is important to note how the trend of the curve is similar to the real efficiency shown in the works by Boglietti et al.³¹ and Draganescu et al.³⁴

η_{i} (c_{i}) = \frac{1 / t_{i} (c_{i})}{c_{i}} = \frac{\ln (1 + {(c_{i} * A_{2})}^{3})}{c_{i} * A_{1} * \ln (2)}

(15)

Figure 3.

Relative efficiency of the activity (expression (15)).

Energy extension for PSPLIB

To extend PSPLIB to MRCPSP-ENERGY, energy consumption and processing times are included for each activity in the uni-modal RCPSP instances through the mathematical model described above (expression (14)). Therefore, four problems sets $j 30$ , $j 60$ , $j 90$ , and $j 120$ are created with $30$ , $60$ , $90$ , and $120$ activities, respectively. The values of the standard efficiency of the projects are available in the PSPLIB-ENERGY.

Without loss of generality, three specific values of energy consumption $e_{im}$ are taken. Therefore, three modes and three proportions of energy consumption (c _im ) for each mode m associated to each activity i are defined. The first mode ( $c_{i 1} = 0.8$ ) corresponds to a decrease of $20 %$ in the energy consumption related to the standard value $e_{i 2}$ . The second mode ( $c_{i 2} = 1$ ) has the standard value of energy consumption $e_{i}^{std} = e_{i 2}$ , which corresponds to the standard duration $d_{i}^{std} = d_{i 2}$ provided by the original PSPLIB. The third mode ( $c_{i 3} = 1.2$ ) corresponds to an increase of $20 %$ in energy consumption related to the standard value $e_{i 2}$ .

The corresponding values of processing time ( $d_{im}$ ) and energy consumption ( $e_{im}$ ) can be calculated using expressions (16) and (17), respectively. The values of $t_{i} (c_{im})$ are calculated using expression (14)

d_{im} = t_{i} (c_{im}) * d_{i}^{std}, i \in I, m \in {1, 2, 3}

(16)

e_{im} = c_{im} * e_{i}^{std}, i \in I, m \in {1, 2, 3}

(17)

The values of $e_{i}^{std}$ are defined by assigning a random consumption value with an interval $[1, 10]$ to each instance’s activity on the PSPLIB-ENERGY library. This range of values was proposed considering the same intervals used for the original parameters in the PSPLIB. Since all parameter values in the PSPLIB are integers, the values of the parameters in the PSPLIB-ENERGY library are also integers. Note that an activity $i$ with duration $d_{im} = 1$ cannot be reduced. Similarly, if an activity $i$ has an energy consumption of $e_{im} = 1$ , it cannot be reduced. The approximation of the other cases was made taking into account their corresponding mode $m$ . Then, for $m = 3$ , $d_{im}$ was rounded downward and $e_{im}$ was rounded upward. In the case $m = 1$ , $d_{im}$ was rounded upward and $e_{im}$ was rounded downward.

For the evaluation of future techniques to be developed using the PSPLIB-ENERGY library, the evaluation criteria is to maximize the relative efficiency presented in expression (12). This expression takes into account both the $makespa n_{w}$ and the total energy consumption $CET P_{w}$ (expression (7)) in a single objective.

To calculate the average value $\bar{η}$ for the problems of the sets $j 30$ , $j 60$ , $j 90$ , or $j 120$ in PSPLIB-ENERGY, expression (18) is defined, where $nP$ is the number of evaluated projects

\bar{η} = \frac{\sum_{w = 1}^{nP} η_{w} (makespa n_{w}, CET P_{w})}{nP}

(18)

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. Table 1 shows the energy consumption ( $e_{im}$ ), the processing time ( $d_{im}$ ), and the resource usage. The first column shows the activities (activities $1$ and $8$ are fictitious with duration and consumption equal to $0$ ). The second to the seventh columns show the modified duration of the activities and the corresponding energy consumption $(d_{im}, e_{im})$ . The values of $d_{i 2}$ and $e_{i 2}$ (columns in bold) are considered the standard values with a usage of $100 %$ in energy consumption and processing time. The eighth to the tenth columns show the resource usage.

Table 1.

Energy consumption ( $e_{im}$ ), processing time ( $d_{im}$ ), and resource usage for the MRCPSP-ENERGY instance.

No. of jobs	$d_{i 1}$	$e_{i 1}$	$d_{i 2}$	$e_{i 2}$	$d_{i 3}$	$e_{i 3}$	$r_{i 1}$	$r_{i 2}$	$r_{i 3}$
1	0	0	0	0	0	0	0	0	0
2	4	4	3	5	2	6	1	1	1
3	3	1	2	2	1	3	2	1	1
4	2	5	1	7	1	7	1	0	1
5	7	3	5	4	4	5	0	1	1
6	3	4	2	6	1	8	2	1	0
7	8	4	6	6	5	8	2	1	2
8	0	0	0	0	0	0	0	0	0

Figure 4 shows the precedence relationships and the information provided in Table 1: the use of each renewable resource, and the processing time versus the energy consumption in each mode of execution.

Figure 4.

A network for the MRCPSP-ENERGY instance.

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

Figure 5.

Three Gantt charts of the example in Figure 4.

To calculate the efficiency $η_{w}$ of each solution, the values $LB 0_{w} = 6$ and $emi n_{w} = 21$ were calculated from Figure 4. Figure 5 shows the upper level of project performance $CS R_{w}$ , the value of the total project duration $makespa n_{w}$ , the total energy consumption of the project $CET P_{w}$ , and the value of the evaluation criterion $η_{w}$ of three different solutions.

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, its efficiency is $η_{c} = 41.1 %$ , and it is considered better than Solution ( $a$ ). Solution ( $b$ ) maintains the same energy consumption as Solution ( $a$ ) but improves in $makespan$ . Therefore, it achieves the highest value of the relative efficiency of the project $η_{b} = 42 %$ . In conclusion, Solution ( $b$ ) is considered to be the best solution of the three.

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 $CS R_{w}$ .

A genetic algorithm for solving the PSPLIB-ENERGY library

Generally, genetic algorithms are well-recognized and appropriate approaches for solving MRCPSP.^27,35 Therefore, in this section, a genetic algorithm is proposed for solving MRCPSP-ENERGY library instances. This is considered a good starting point for the research community to compare the performance of their techniques for solving MRCPSP-ENERGY library instances. The main contribution in this section is the new application and adaptation of a genetic algorithm to the proposed library. The pseudocode for the proposed genetic algorithm is shown in Algorithm 1.

Algorithm 1. Pseudo code for the proposed genetic algorithm.
1: Initiation and data reading; 2: Calculation of values by using the PERT/CPM method; 3: Generation of the initial population; 4: Evaluation of the initial population; 5: while Scheduling number ≤ iterations do 6: Parent selection; 7: Crossover of selected parents; 8: Offspring mutation; 9: Replacement of the current population; 10: Evaluation of the new population; 11: end while 12: Local improvement; 13: return The best schedule in the population;

Algorithm 1. Pseudo code for the proposed genetic algorithm.

1: Initiation and data reading;
2: Calculation of values by using the PERT/CPM method;
3: Generation of the initial population;
4: Evaluation of the initial population;
5: while Scheduling number ≤ iterations do
6: Parent selection;
7: Crossover of selected parents;
8: Offspring mutation;
9: Replacement of the current population;
10: Evaluation of the new population;
11: end while
12: Local improvement;
13: return The best schedule in the population;

Codification of solutions

There are several compatible codifications for modeling the MRCPSP in terms of genes and chromosomes.³⁶ The activity list representation and random key representation are those that have obtained the best results.²⁷ In this work, the activity list is used as codification. It consists of a precedence feasible activity list ${a_{1}, a_{2}, \dots, a_{i}, \dots, a_{n}}$ , in which the activity position in the list represents the priority to be scheduled.

A chromosome is created to contain all of the information of a complete feasible schedule. It consists of $n$ activity genes (the activity list), one schedule generation scheme (SGS) gene, and one direction gene. The activity genes have a pair of values $(a_{i}, z_{i})$ , where $a_{i}$ represents the activity position and $z_{i}$ represents how the activity consumes energy. The SGS gene is $0$ when the serial scheme is used and $1$ when the parallel scheme is used. The direction gene is $0$ when the forward direction is used and $1$ when the backward direction is used. An example of the codification used is shown in Figure 6.

Figure 6.

The codification used in the genetic algorithm.

The initial population and population size

Following Kolisch and Hartmann,³⁶ the regret-based biased random sampling (RBBRS) and the latest start time (LST) priority rule^37,38 are used to generate an initial population, with the parameters $ϵ = 1$ and $α = 1$ .

In the methodologies for solving the MRCPSP, there is no standard method to estimate an appropriate population size. Debels and Vanhoucke³⁹ state that the larger the number of activities, the smaller the population size. Cervantes et al.⁴⁰ propose a mathematical expression where the relation between the population and the activities is inverse. Based on these statements, expressions (19) and (20) are proposed

p o p u l a t i o n = (\frac{2700}{N}) * l n (\frac{e * i t e r a t i o n s}{1000}) with N \leq 120

(19)

generations = \frac{iterations}{population}

(20)

Fitness function

The fitness function allows the quality of solutions to be determined. The proposed relative efficiency (expression (12)) is used in this work as a fitness function. Thus, a solution with a greater relative efficiency value $η_{w}$ is considered better than another with a lower value.

Selection

In the MRCPSP, roulette and ranking are the most commonly used selection methods. The selection by roulette does not work properly when the range between the fitness values of individuals gets bigger. It happens in the MRCPSP, but not in MRCPSP-ENERGY because all of the values of relative efficiency of the project are ranged in the interval $[0, 1]$ . Therefore, the roulette selection is used, in which the parents are selected according to their fitness. The best chromosomes are more likely to be selected.⁴¹

Crossover

An appropriate crossover operator has to be defined for each gene type. For activity genes, one-point crossover is used. A random integer $q$ with $0 < q < N$ is generated. Thus, the first genes from $0$ to $q$ are taken from Parent $1$ , while the remaining ones are taken from Parent $2$ . Thus, the list of activity genes is gone over one by one and only those that are different from Parent $1$ are chosen. For SGS and direction genes, the gene value is inherited when it is the same in both parents, otherwise it is randomly generated.

Mutation

The proposed genetic algorithm uses the insertion of Boctor⁴² because it is considered a good operator since it produces feasible solutions and is compatible with the activity list codification. Thus, given an activity $i$ to be inserted into the activity list, first, the maximum position of all its predecessors in the list $(maxPred)$ and the minimum position of all its successors $(minSuc)$ are computed and then a random integer $Rnd$ is generated with $maxPred \leq Rnd \leq minSuc$ . Activity $i$ is inserted in this position. A mutation probability value of $0.05$ for each activity is selected. An activity that has been selected to mutate will change the position in the activity list as well as its energy consumption and execution time.

Replacement

The replacement strategies are the way the next generations are formed. A semi-elitist strategy is used, which consists of building the new population from the individual with the best solution in the current population and the offspring of that population.

Local improvement

Finally, a local improvement is applied to the best solution. It consists of going over all of the activities and checking whether they can be executed with less energy consumption (longer execution time) without breaking precedence or resource constraints.

Evaluation and analysis of results

The experiments were performed on a PC with Intel^® Core™ $i 7$ CPU of $2.20 GHz$ and $16 GB$ RAM. The proposed genetic algorithm was developed in $C + +$ . First, the results are shown by keeping the standard academic format and then the behavior of the proposed algorithm is presented. Finally, how different energy levels can increase process efficiency is analyzed.

The results are shown in Table 2. The sets of problems $j #$ are shown in the first column and the remaining columns show the average value of relative efficiency $(\bar{η})$ for the problem sets $j 30$ , $j 60$ , $j 90$ , and $j 120$ of the PSPLIB-ENERGY library, for $1000$ , $5000$ , and $50, 000$ , respectively. Kolisch and Hartmann²⁷ clarify the reason for using iterations as comparison criterion, and they define what an iteration is. In Table 3 the execution times (in seconds) are shown for the same number of iterations ( $1000$ , $5000$ , and $50, 000$ ).

Table 2.

$\bar{η}$ obtained using the proposed genetic algorithm for solving the MRCPSP-ENERGY library.

j#	Iterations ( $\bar{η}$ )
	$1000$	$5000$	$50, 000$
j30	$0.5966$	$0.6091$	$0.6293$
j60	$0.6029$	$0.6182$	$0.6424$
j90	$0.6052$	$0.6216$	$0.6478$
j120	$0.4760$	$0.4875$	$0.5032$

Table 3.

Processing time obtained using the proposed genetic algorithm for solving the MRCPSP-ENERGY library.

j#	Iterations (s)
	$1000$	$5000$	$50, 000$
j30	$0.053 s$	$0.198 s$	$1.514 s$
j60	$0.159 s$	$0.544 s$	$4.163 s$
j90	$0.286 s$	$0.957 s$	$8.210 s$
j120	$0.424 s$	$1.282 s$	$10.624 s$

To test the consistency and the convergence behavior of the proposed genetic algorithm, the algorithm was executed up to $100, 000$ iterations. The relative efficiency $(\bar{η})$ of each iteration for all sets is shown in Figure 7. It exhibits a typically growing function with a horizontal asymptote when the iterations tend toward infinity for the four sets. In fact, all of the sets obtained an average improvement that was lower than $0.083 %$ in the last $5000$ iterations.

Figure 7.

Convergence behavior of the proposed genetic algorithm for sets $j 30$ , $j 60$ , $j 90$ , and $j 120$ .

However, it is important to analyze the search space when the energy consumption is included. In order to do this, the results obtained for solving PSPLIB-ENERGY using one and three levels of energy are compared (see Figure 8). For the first case, only the standard duration and the standard energy consumption (i.e. $d_{i 2}$ and $e_{i 2}$ ) are used, whereas for the second case, the three levels of energy consumption are used. It can be observed that as the number of energy levels increases, a better solution can be achieved.

Figure 8.

Comparison between levels of energy consumption and relative efficiency of sets $j 30$ , $j 60$ , $j 90$ , and $j 120$ .

Conclusion and further works

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

In this article, an efficiency-based MRCPSP is proposed. It is called MRCPSP-ENERGY, which includes energy consumption in a scheduling problem. The proposed bi-objective approach consists of maximizing relative project efficiency. This is carried out by simultaneously minimizing the $makespan$ and the energy 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. Furthermore, the library PSPLIB-ENERGY is proposed. It is an extension to PSPLIB for assessing the MRCPSP-ENERGY solution methods. This extension is supported by a proposed model of energy consumption. This model is consistent with the surveys reported in the academic literature about energy consumption for machines. Therefore, this library can be used to evaluate and compare different solving methods.

Since genetic algorithms have been competitive methods for solving the classical MRCPSP, a genetic algorithm has been proposed to solve MRCPSP-ENERGY by adapting well-known strategies that have been previously developed. The results show the convenience of assigning different energy consumptions and processing times to activities in machine scheduling problems in order to achieve energy-efficient solutions. The aim of these results is to establish an initial comparison point for future solving methods.

The PSPLIB-ENERGY library has been developed, keeping the same format as the PSPLIB, with four sets of problems ( $j 30$ , $j 60$ , $j 90$ , and $j 120$ ), each of which has $480$ problems (except the set $j 120$ , which has $600$ instances). This library is available at http://gps.webs.upv.es/psplib-energy/.

In further works, we aim to extend this work to consider the energy consumption as a non-renewable resource with a dynamic threshold. This problem occurs when a limited energy budget is allocated to a project or the available energy is limited in some time intervals. As long as the available energy allows the construction of feasible solutions, the new solutions must take into account these dynamic thresholds, so the search must be focused on these bottlenecks to obtain energy-efficient solutions. Thus, our metaheuristic proposal must be extended to address this issue.

Finally, this article aims to encourage the development of future research to find sustainable and efficient solutions to resource-constrained scheduling problems.

Footnotes

Appendix 1 Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the Spanish Government under the research projects TIN2013-46511-C2-1 and TIN2016-80856-R.

References

Mouzon

Yildirim

Twomey

. Operational methods for minimization of energy consumption of manufacturing equipment. Int J Prod Res 2007; 45(18–19): 4247–4271.

Rahimifard

Seow

Childs

. Minimising Embodied Product Energy to support energy efficient manufacturing. CIRP Ann 2010; 59(1): 25–28.

Cucala

Fernández

Sicre

. Fuzzy optimal schedule of high speed train operation to minimize energy consumption with uncertain delays and drivers behavioral response. Eng Appl Artif Intel 2012; 25(8): 1548–1557.

Govindan

Sarkis

Jabbour

CJC

. Eco-efficiency based green supply chain management: current status and opportunities. Eur J Oper Res 2014; 233(2): 293–298.

Hassini

Surti

Searcy

. A literature review and a case study of sustainable supply chains with a focus on metrics. Int J Prod Econ 2012; 140(1): 69–82.

Escamilla

Salido

. A dual scheduling model for optimizing robustness and energy consumption in manufacturing systems. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(1): 5–16. DOI: 10.1177/0954405415625915.

Zhang

Jiang

Zhang

. Energy-aware integration of process planning and scheduling of advanced machining workshop. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(11): 2040–2055. DOI: 10.1177/0954405415616785.

Iqbal

Aziz

Jahanzaib

. Integration of cell formation and job sequencing to minimize energy consumption with minimum make-span. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(14): 2636–2651. DOI: 10.1177/0954405416630182.

Lova

Tormos

Cervantes

. An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. Int J Prod Econ 2009; 117(2): 302–316.

10.

Kolisch

Sprecher

. PSPLIB: a project scheduling library. Eur J Oper Res 1996; 96: 205–216.

11.

Salonitis

Ball

. Energy efficient manufacturing from machine tools to manufacturing systems. Proc CIRP 2013; 7: 634–639.

12.

Seow

Rahimifard

. A framework for modelling energy consumption within manufacturing systems. CIRP J Manuf Sci Technol 2011; 4(3): 258–264.

13.

Yan

Xing

. Energy requirements evaluation of milling machines based on thermal equilibrium and empirical modelling. J Clean Prod 2013; 52: 113–121.

14.

Liang

. A critical energy model for brittle-ductile transition in grinding considering wheel speed and chip thickness effects. Proc IMechE, Part B: J Engineering Manufacture 2016; 230: 1372–1380.

15.

Moradnazhad

Unver

. Energy efficiency of machining operations: a review. Proc IMechE, Part B: J Engineering Manufacture 2017; 231(11): 1871–1889. DOI: 10.1177/0954405415619345.

16.

Bruzzone

Anghinolfi

Paolucci

. Energy-aware scheduling for improving manufacturing process sustainability: a mathematical model for flexible flow shops. CIRP Ann 2012; 61(1): 459–462.

17.

Niu

Ong

Nee

. An improved intelligent water drops algorithm for solving multi-objective job shop scheduling. Eng Appl Artif Intel 2013; 26(10): 2431–2442.

18.

Liu

. Methods for integrating energy consumption and environmental impact considerations into the production operation of machining processes. Chin J Mech Eng 2010; 23(4): 428–435.

19.

Duou

Sutherland

Dornfeld

. Towards energy and resource efficient manufacturing: a processes and systems approach. CIRP Ann 2012; 61(2): 587–609.

20.

Fang

Uhan

Zhao

. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. J Manuf Syst 2011; 30(4): 234–240.

21.

Artigues

Lopez

HaÏt

. The energy scheduling problem: industrial case-study and constraint propagation techniques. Int J Prod Econ 2013; 143(1): 13–23.

22.

Luo

Huang

. Hybrid flow shop scheduling considering machine electricity consumption cost. Int J Prod Econ 2013; 146(2): 423–439.

23.

Okubo

Miyamoto

Yoshida

. Project scheduling under partially renewable resources and resource consumption during setup operations. Comput Ind Eng 2015; 83: 91–99.

24.

Zhang

Tang

Peng

. A method for minimizing the energy consumption of machining system: integration of process planning and scheduling. J Clean Prod 2016; 137(20): 1647–1662.

25.

Liu

Zhou

. Multi-objective energy-saving scheduling for a permutation flow line. Proc IMechE, Part B: J Engineering Manufacture 2018; 232(5): 879–888. DOI: 10.1177/0954405416657583.

26.

Dai

Tang

Giret

. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robot CIM-Int Manuf 2013; 29(5): 418–429.

27.

Kolisch

Hartmann

. Experimental investigation of heuristics for resource-constrained project scheduling: an update. Eur J Oper Res 2006; 174(1): 23–37.

28.

Talbot

. Resource-constrained project scheduling with time-resource tradeoffs: the nonpreemptive case. Manage Sci 1982; 28(10): 1197–1210.

29.

Blazewicz

Lenstra

Kan

. Scheduling subject to resource constraints: classification and complexity. Discrete Appl Math 1983; 5(1): 11–24.

30.

Oberg

Jones

Horton

. Machinery’s handbook. 27th ed.New York: Industrial Press Inc., 2004.

31.

Boglietti

Cavagnino

Lazzari

. International standards for the induction motor efficiency evaluation: a critical analysis of the stray-load loss determination. IEEE T Ind Appl 2004; 40(5): 1294–1301.

32.

Saidur

. A review on electrical motors energy use and energy savings. Renew Sust Energ Rev 2010; 14(3): 877–898.

33.

Beggs

. Energy: management, supply and conservation. Oxford: Butterworth Heinemann, 2002.

34.

Draganescu

Gheorghe

Doicin

. Models of machine tool efficiency and specific consumed energy. J Mater Process Tech 2003; 141(1): 9–15.

35.

Van Peteghem

Vanhoucke

. An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. Eur J Oper Res 2014; 235(1): 62–72.

36.

Kolisch

Hartmann

. Chapter 7: heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis. In: Weglarz

(ed.) Project scheduling. New York: Springer, 1999, pp.147–178.

37.

Hartmann

Kolisch

. Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur J Oper Res 2000; 127(2): 394–407.

38.

Klein

. Bidirectional planning: improving priority rule-based heuristics for scheduling resource-constrained projects. Eur J Oper Res 2000; 127(3): 619–638.

39.

Debels

Vanhoucke

. A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem. Oper Res 2007; 55(3): 457–469.

40.

Cervantes

Lova

Tormos

. A dynamic population steady-state genetic algorithm for the resource-constrained project scheduling problem. In: Thanh Nguyen

Borzemski

Grzech

. (eds) New frontiers in applied artificial intelligence (vol. 502). Berlin, Heidelberg: Springer, 2008, pp.611–620.

41.

Hartmann

. A competitive genetic algorithm for resource-constrained project scheduling. Nav Res Log 1998; 45(7): 733–750.

42.

Boctor

. Resource-constrained project scheduling by simulated annealing. Int J Prod Res 1996; 34(8): 2335–2351.

No. of jobs	$d_{i 1}$	$e_{i 1}$	$d_{i 2}$	$e_{i 2}$	$d_{i 3}$	$e_{i 3}$	$r_{i 1}$	$r_{i 2}$	$r_{i 3}$
1	0	0	0	0	0	0	0	0	0
2	4	4	3	5	2	6	1	1	1
3	3	1	2	2	1	3	2	1	1
4	2	5	1	7	1	7	1	0	1
5	7	3	5	4	4	5	0	1	1
6	3	4	2	6	1	8	2	1	0
7	8	4	6	6	5	8	2	1	2
8	0	0	0	0	0	0	0	0	0

No. of jobs	$d_{i 1}$	$e_{i 1}$	$d_{i 2}$	$e_{i 2}$	$d_{i 3}$	$e_{i 3}$	$r_{i 1}$	$r_{i 2}$	$r_{i 3}$
1	0	0	0	0	0	0	0	0	0
2	4	4	3	5	2	6	1	1	1
3	3	1	2	2	1	3	2	1	1
4	2	5	1	7	1	7	1	0	1
5	7	3	5	4	4	5	0	1	1
6	3	4	2	6	1	8	2	1	0
7	8	4	6	6	5	8	2	1	2
8	0	0	0	0	0	0	0	0	0

A new model and metaheuristic approach for the energy-based resource-constrained scheduling problem

Abstract

Keywords

Introduction

Literature review

Description of the MRCPSP

MRCPSP-ENERGY: a MRCPSP extension for energy efficiency

Project efficiency: optimization criterion in MRCPSP-ENERGY

Definition 1

PSPLIB-ENERGY: an extension of the PSPLIB

The proposed model for energy consumption

Energy extension for PSPLIB

Example of a MRCPSP-ENERGY instance

A genetic algorithm for solving the PSPLIB-ENERGY library

Codification of solutions

The initial population and population size

Fitness function

Selection

Crossover

Mutation

Replacement

Local improvement

Evaluation and analysis of results

Conclusion and further works

Footnotes

Appendix 1

Declaration of conflicting interests

Funding

References

No. of jobs	$d_{i 1}$	$e_{i 1}$	$d_{i 2}$	$e_{i 2}$	$d_{i 3}$	$e_{i 3}$	$r_{i 1}$	$r_{i 2}$	$r_{i 3}$
1	0	0	0	0	0	0	0	0	0
2	4	4	3	5	2	6	1	1	1
3	3	1	2	2	1	3	2	1	1
4	2	5	1	7	1	7	1	0	1
5	7	3	5	4	4	5	0	1	1
6	3	4	2	6	1	8	2	1	0
7	8	4	6	6	5	8	2	1	2
8	0	0	0	0	0	0	0	0	0