A Multi-Population BRKGA for Energy-Efficient Job Shop Scheduling with Speed Adjustable Machines

Abstract

Energy-efficient scheduling has become a new trend in industry and academia, mainly due to extreme weather conditions, stricter environmental regulations, and volatile energy prices. This work addresses the energy-efficient Job shop Scheduling Problem with speed adjustable machines. Thus, in addition to determining the sequence of the operations for each machine, one also needs to decide on the processing speed of each operation. We propose a multi-population biased random key genetic algorithm that finds effective solutions to the problem efficiently and outperforms the state-of-the-art solution approaches.

This work is financed by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project LA/P/0063/2020.

1 Introduction

The steady increase in energy consumption and public awareness of its environmental impacts bring new challenges for the industrial sector. Thus, practitioners are looking for ways of reducing energy consumption. An effective way to accomplish such a reduction is to implement an energy-efficient scheduling methodology which, additionally, needs no significant capital investments and is particularly relevant for small and medium-sized enterprises [1].

The energy-efficient job shop scheduling problem (EEJSP) attempts to lower energy consumption while providing the same level of service mainly by adjusting machines processing speed [9] and/or by switching machines into a power-saving mode when idle [8]. The former strategy balances energy consumption and production time, while the latter balances energy savings from resorting to the use of a power-saving mode and energy requirements to restart and warm up machines. Furthermore, under the first strategy, non-processing energy consumption can be decreased as adjusting the processing speed may reduce machines’ idle time.

Although only recently energy-efficient scheduling became the subject of systematic research, one of the first works on EEJSP with speed adjustable machines is that of He et al. [5]. They propose a Tabu search (TS) algorithm to find a sequence of operations for each machine as well as the machine processing speed for each operation such that both the makespan ($C_{max}$) and the total energy consumption ($\mathcal {E}$) are optimized. Later, [10] proposes a mixed-integer programming (MIP) model and a genetic-simulated annealing algorithm. Recently, [9, 11] propose similar genetic algorithms (GAs). While [9] minimizes the weighted sum of the normalized $C_{max}$ and the normalized $\mathcal {E}$, [11] also includes the normalized noise emissions in its weighted sum. More recently, hybrid metaheuristics have been proposed. For example, [12] embeds two local search heuristics into a GA to find solutions that minimize the total weighted tardiness (wT) and the $\mathcal {E}$. One of the heuristics attempts to improve the wT by swapping disjoint pairs of adjacent operations on each machine and the other attempts to improve the $\mathcal {E}$ by decreasing the processing speed of non-critical operations. Another example is the work in [7] that decrease energy consumption by decelerating the processing of non-critical operations as much as possible without affecting the completion time of any other operation. A more complete account of recent work on energy-efficient job shop scheduling problems can be found in [3].

This work proposes a multi-objective multi-population biased random key genetic algorithm (multi-objective mpBRKGA) that finds effective solutions to the EEJSP problem efficiently. The computational experiments performed on a set of 13 benchmark problem instances show that the mpBRKGA outperforms the state-of-the-art algorithms. We describe the problem being addressed in Sect. 2 and the proposed multi-objective mpBRKGA in Sect. 3. The computational experiments and results are reported in Sect. 4. Finally, Sect. 5 draws some conclusions and points out future research directions.

2 Problem Definition

The classical job shop scheduling problem (JSP) comprises a set J of independent jobs and a set of machines. Each job consists of a set $O_j=\{1,2,\ldots ,n_j\}, \forall j \in J$ of $n_j$ ordered operations. Each operation must be processed on a given machine and each machine can only process one operation at a time.

The EEJSP with speed adjustable machines requires solving simultaneously two interdependent combinatorial problems: scheduling the operations on each machine (machine scheduling) and determining the speed at which each operation is processed (operation speed assignment).

A machine can process an operation at one of the various speeds requiring a predefined processing time and power consumption. (The higher the processing speed, the higher the power consumption required.) Idle machines are considered in “stand-by” mode and with negligible power consumption.

An operation can be started right after the completion of the previous operation of the same job (or immediately if it is the job’s first operation) if the required machine is idle; otherwise, the job waits for the machine in a buffer. Whenever an operation is completed the machine can start processing the next operation immediately. Among all possible solutions, we are interested in those that minimize the makespan $C_{max}$ and the energy consumed to process all production operations $\mathcal {E}$.

3 The Proposed Multi-objective MpBRKGA

Biased random key genetic algorithms (BRKGAs) have been successfully proposed and implemented to find good quality solutions in several application areas. The multi-objective mpBRKGA proposed in this work borrows its principles from [4] and evolves $\varOmega +\varPi$ populations: each of the $\varOmega$ populations considers one of the $\varOmega$ objectives, while each of the $\varPi$ populations considers simultaneously all $\varOmega$ objectives. The initial populations are uniformly randomly generated. Nevertheless, 20% of the initial solutions of the single-objective population that minimizes $C_{max}$ have the processing speeds set to the maximum value. Similarly, the processing speeds are set to the minimum value for 20% of the initial solutions of the single objective population that minimizes $\mathcal {E}$.

A solution is encoded as a two-part vector with $N = \sum _{j \in J} n_j$ elements each. Each vector element is a random key, i.e., a real number in the interval [0, 1]. The first part provides a sequence of operations and the second assigns a processing speed to each operation. (See Fig. 1.a for an example with three jobs, each with three operations that can be processed at one of the three available speeds.)

The decoding of the first N elements uses the smallest position value rule to construct a permutation representation of the RKs. Elements are sorted in ascending order, thus, providing a sequence of operations, see part (i) of Fig. 1.b). Then, the permutation is converted into a feasible sequence of operations by sorting the operations of each job in ascending order; this way ensuring precedence constraints, see part (i) of Fig. 1.c). Each RK in the second part of the chromosome is decoded into the processing speed of the corresponding operation. The processing speed of operation l is given by the smallest integer greater than or equal to $\text{ RK}_l \times |\mathcal {P}_l|$, where $|\mathcal {P}_l|$ is the number of speed values available for operation l, see Fig. 1 - part (ii).

Fig. 1.

Solution encoding and decoding procedures.

The evolutionary strategy is similar for all populations. At each generation, a new population is obtained by joining the set $N_e$ of $n_e$ elite solutions, the set $N_o$ of $n_o$ offspring solutions, and the set $N_m$ of $n_m$ mutant solutions. For each of the $\omega \in \varOmega$ single objective populations, the set $N_e^\omega$ of elite solutions comprises the best $n_e$ solutions of its current generation. Regarding each of the $\pi \in \varPi$ multi-objective populations, the set $N_e^\pi$ of elite solutions are the best $n_e$ solutions chosen from a pool of solutions consisting of the best $n_e$ solutions of its current generation and the best $n_e$ solutions of the current generation of each $\omega \in \varOmega$ population, from which the repeated solutions are removed. Additionally, the $\varPi$ multi-objective populations exchange their elite solutions after a pre-determined number of generations ($g_{ex}$). Thus, every $g_{ex}$ generations, the pool of solutions also contains the best $n_e$ solutions of each $\pi \in \varPi$ population. To identify the best solutions for the multi-objective populations, we employ a non-dominated ranking procedure [2] and the crowding distance [2] to sort solutions of the same rank.

Regardless of the population being evolved, the $n_o$ offspring solutions are obtained by a biased parameterized uniform crossover [4, 6] and the $n_m$ mutants are randomly generated in the same manner as the initial population was.

The evolutionary process is repeated for a predetermined number of generations $G_{max}$. Then, a pool is created by joining the best solutions of the $\varOmega$ populations and the non-dominated solutions of the $\varPi$ populations and removing repeated and dominated solutions. The remaining solutions are Pareto solutions and provide an approximation to the Pareto optimal front.

4 Numerical Results

The multi-objective mpBRKGA was implemented in Python^® 3.8 and all computational experiments were carried out on a 3.20 GHz Intel^® Core^™i7-8700 PC with 24 GB RAM. We solve three problem instances proposed in [11] and 10 proposed in [9]. The former instances are designated as Yin01, Yin02, and Yin03 and have four, 10, and 20 jobs with 12, 40, and 60 operations, respectively. Instances Yin01 and Yin03 have five machines while instance Yin02 has six. Operations can be processed at two or three speeds. The instances proposed in [9] are designated as Sal01 $\sim$ 10 and each has three jobs with 25 operations each and three machines. Operations can be processed at three speeds.

Following on literature recommendations, the control parameters of the mpBRKGA were set as: population size $P=500$, number of elite solutions $n_e=0.2 P$, number of mutants $n_m=0.1 P$, and inheritance probability $p_e=0.7$ [4, 6]. The remaining control parameters were set through empirical testing to $G_{max}=300$, $\varPi =2$, $\varOmega =2$, and $g_{ex}=30$.

The benchmark instances were solved in [11] by a genetic algorithm (GA) and in [9] by a multi-objective GA (moGA) and constraint programming (CP). Both [11] and [9] employed a weighted summation approach and reported the $C_{max}$ and $\mathcal {E}$ values under different weight assumptions. Table 1 reports the boundary solutions, that is, the minimum makespan $C_{max}^*$ and associated energy consumption $\mathcal {E}$ and the minimum energy consumption $\mathcal {E}^*$ and associated makespan $C_{max}$, obtained by the mpBRKGA and by the GA [11] for the Yin instances. Similar results are reported for the Sal instances. However, the reported values are averages over the 10 problem instances since this is what is reported for the CP and the moGA approaches in [9]. As it can be seen, the mpBRKGA is capable of finding very good solutions and it outperforms the GA, the CP, and the moGA approaches. Although the mpBRKGA finds the same boundary solutions and PF for Yin01, it finds better ones for Yin02 and Yin03. Indeed, the mpBRKGA boundary solutions dominate those of [11]. Regarding instances Sal01 $\sim$ 10, our averages are always better, except for the minimum energy that we have the same value.

Table 1. The makespan and energy consumption values at boundary solutions for the EEJSP benchmark problem instances.

Fig. 2.

Pareto fronts found by the mpBRKGA and the GA [11] for instances Yin01 $\sim$ 03.

Figure 2 depicts the Pareto fronts (PFs) obtained by the mpBRKGA and the ones obtained by the GA [11] for problem instances Yin01 $\sim$ 03. As it can be seen, for instance Yin01, the (PFs) are the same for both methods. However, for Yin02 and Yin03, the mpBRKGA produces much better solutions. All the solutions found by the GA proposed in [11] are dominated by the ones found by the mpBRKGA. In contrast, none of the mpBRKGA solutions are dominated.

5 Conclusion

We address the EEJSP with speed adjustable machines. We propose a multi-objective mpBRKGA that is capable of finding good solutions efficiently and outperforms the state-of-the-art solution approaches. Experiments show that, our PFs are the better than those of [11] for instances Yin01 $\sim$ 03; and our average values for boundary solutions are better than those reported in [9] for instances Sal01 $\sim$ 10. This work can be extended by considering other energy factors such as peak power, which usually is a major concern if renewable energies are being used.