Solving Rescheduling Problems in Dynamic Permutation Flow Shop Environments with Multiple Objectives Using the Hybrid Dynamic Non-Dominated Sorting Genetic II Algorithm

Abstract

In this work, we seek to design a model that contributes to the study and resolution of a multi-objective rescheduling problem in dynamic permutation flow shop contexts. In this type of problem, where the objectives can be valued in heterogeneous units, the difficulty of achieving an optimal solution leads to finding a set of non-dominated efficient solutions (also called Pareto front). On the other hand, we will also consider the potential appearance of disruptions in planned scheduling (such as machine breakdowns or arrival of new priority jobs) that require a rapid re-planning of the aforementioned scheduling. In this paper, a hybrid dynamic non-dominated sorting genetic II metaheuristic (HDNSGA-II) is proposed to find the optimal Pareto front. The algorithm is applied to a benchmark already tested in previous studies, defined by three conflicting objective functions (makespan, total weighted tardiness, and stability) and three different types of disruption (machine breakdowns, incorporation of new jobs, and modifications in process times). According to the statistical comparison performed, the HDNSGA-II algorithm performs better in the designed environment, especially in larger problems.

1. Introduction

1.1. Flow Shop Problems

The problem of scheduling a set of jobs assigned to different machines in specific production environments has been studied profusely since the 1950s, highlighting its non-deterministic polynomial-time hardness (NP-hardness), as exposed by [1].

In flow shop production systems of “n” jobs to be processed in “m” machines, the usual goal is to seek the optimal scheduling of the “n” jobs. Each job integrates “m” possible operations to be performed on each of the machines. Because each machine must process jobs at specific periods of time, to complete a job on an available machine j, processing must have previously completed on the j-1 machine.

In the factorial permutation flow shop problems (PFSPs), the scheduling of jobs to be processed is the same on all machines. It is usually considered that there are no established orders of precedence among job operations (completed without interruption) and that machines can only perform one operation at a time.

Single-objective flow shop optimization consists of sequencing n jobs on m machines minimizing or maximizing a single determined criterion. There are multiple objective functions applied to flow shop optimization. The most common is the maximum task completion time (makespan). As for the techniques proposed in the literature to solve this problem, they range from exact to approximate methods, based on metaheuristics or using simple heuristics depending on the selected objective.

There are several methods based on mathematical models of integer linear programming (MILP) applied to the problem of minimizing the makespan. As remarkable studies, [2] describes a MILP model of the PFSP problem to minimize the makespan with an exponential growth in the number of restrictions. They propose a technique based on row generation to solve the linear relaxation of the problem in polynomial time. On the other hand, [3] exhibits different formulations for the flow shop problem with permutation, with and without unlimited buffers and with the aim of minimizing the delay of jobs. When solved with exact methods such as branch and bound, the global optimal solution can be found. However, the factorial complexity of the sequencing problems makes it possible to solve them in reasonable time only in small problems, producing memory and execution time troubles with instances starting from 20 jobs to 10 machines ([4]).

Due to the high computational requirements of the aforementioned methods in the face of factorial complexity problems, multiple heuristics have been proposed in the literature (see for example [5,6,7,8]). Ref. [9] carries out an exhaustive comparison of 22 heuristics applied to the problem of minimizing the total flow time in flow shop problems with permutation.

According to [10], on average, the NEH heuristic [7] calculates a makespan close to 3% of the optimum, for a total of jobs varying in the range 5–500 and a number of machines between 5 and 25. Both the NEH and Rajendran and Ziegler heuristics are important because they are widely used in the literature in the process of initializing solutions for later improvement through a metaheuristic. An example of a solution initialization procedure that uses both heuristics is that proposed by [11], used by the RIPG algorithm defined in [12].

Multi-objective optimization problems seek to identify efficient solutions (not dominated) for multiple conflicting objectives (such as cost, quality, or time) by determining the so-called Pareto front, a set of solutions from which the decision maker will choose the one that best meet the specific requirements of the problem.

In this type of problem, it is necessary to choose efficiency metrics that allow comparing the solutions of the Pareto front obtained with the different algorithms used in their resolution. From the analysis of the literature, the following efficiency indicators have been chosen:

• Hypervolume metric, according to the calculation proposed by [13].
• Unary Epsilon Indicator [14,15,16].
• Convergence metric, suggested by [17].
• Rate of non-dominated solutions [18].

The methods applied in multi-objective optimization can be categorized in scalar-based and metaheuristic-based techniques [19]. Regarding the scalar techniques, there are different strategies that convert the starting problem into a single-objective type in order to establish the objective weights which allow to obtain the Pareto front, such as CWA (conventional weighted aggregation), DWA (dynamic weighted aggregation), RWA (randomly weighted aggregation), and BWA (bang-bang weighted aggregation).

Regarding metaheuristic techniques, we highlight those based on: genetic algorithms [20,21,22,23,24,25,26], particle swarms [27], tabu search [28], simulated annealing [11,29], ant colonies [30,31], decomposition-based kernel techniques [32], greedy algorithms [12], fuzzy-based techniques [33], hybrid algorithms [34], student learning-based approaches [35], or techniques based on local search [36]. Most articles on these methods study two-objective problems that are graphically representable in a simple way and whose results are easier to analyze.

Recent studies indicate the need to first understand the limitations of current algorithms when working with a greater number of objective functions and later to design new techniques that work properly when the number of these functions increases [37,38].

The investigation is structured as follows. The rescheduling systems described in the literature are illustrated first. Then, after defining the integer linear programming model that describes the problem, a rescheduling system is proposed to solve it according to a predictive-reactive strategy. Subsequently, the novel HDNSGA-II metaheuristic is described and validated on Dubois-Lacoste instances in a static and bi-objective environment. Next, after calibrating the model parameters, the HDNSGA-II and RIPG metaheuristics are applied to a benchmark previously designed in this context. Finally, the comparative results obtained by both algorithms are shown and discussed and the main conclusions of the work are presented.

1.2. Rescheduling Systems

Static scheduling problems determine the processing sequence of an initial set of previously established jobs on the available machines of a system whose conditions are known in advance and unchanged over time. In real production environments, disruptions can arise, such as changes in the priority of carrying out jobs, breakdowns, or maintenance operations on machines. These disruptions lead to dynamic scheduling systems, which require the rescheduling of jobs. The literature shows three main strategic approaches for this rescheduling [39,40]: predictive-reactive, proactive (or robust), and dynamic. One of the most used is the predictive-reactive strategy, which will be chosen in this paper. Additionally, the three main decision policies to reschedule jobs in the predictive-reactive approach [41] are: event-driven, periodic, and hybrid (periodic being the one chosen in this paper). There are also three main methods to update an infeasible schedule when interruptions arise in the system (disabling the initial schedule): right-shift rescheduling [42,43], partial regeneration [42], and complete regeneration [44,45]. The complete regeneration method is the one used in this study.

Usual performance indicators for rescheduling systems can be efficiency metrics (e.g., makespan, mean flow time, or total weighted tardiness) or robustness metrics (such as solution robustness metrics, as known as stability metrics as described in [46]) (e.g., system mean stability [41,47,48]).

The literature on rescheduling in dynamic flow shop environments with permutation and multiple objective functions is still scarce. The algorithms for finding non-dominated solutions in PFSP environments, with a proactive-reactive strategy proposed by [49,50], do not use weighting of the objective functions. Ref. [49] utilises the MOSA (multi-objective simulated annealing algorithm) while [50] proposes metaheuristics based on hyper-volume known as IBEA (indicator-based evolutionary algorithm). Ref. [51] proposes the application of a state-of-the-art greedy algorithm for scheduling problems, called RIPG (restarted iterated Pareto greedy) to solve a three-objective permutation flow shop rescheduling problem.

The literature on rescheduling in environments other than the flow shop with permutation is not abundant either. Ref. [52] adjusts the NSGA-II—non-dominated sorting genetic algorithm [21]—for a stochastic FJSP (flexible job shop problem). Ref. [53] builds a multi-objective genetic algorithm to minimize the schedule’s total tardiness and stability in an environment with parallel machines and variations in job delivery dates. Ref. [54] developed a hybrid MPGA-CP (multiple populations genetic algorithm with constraint programming) to solve a three-objective flexible job shop problem under uncertainties. In reviews on rescheduling methods by [55,56], the predictive-reactive strategy is recognised as the most frequent.

2. Problem Statement

The aim followed in this paper is minimizing three objective functions: makespan, weighted total tardiness, and stability. The selection of these objective functions seeks to improve the productivity in the production environment (by minimizing the makespan), the customer service (by minimizing the total weighted tardiness), and the schedule stability in the rescheduling process when sudden disruptions arise. The mathematical formulation of the problem studied in this paper is described below and can be found in detail in [51].

As it is a predictive-reactive rescheduling process, the mathematical formulation can be expressed as a MILP (mixed integer linear problem) and be performed each time we need to reschedule. At each rescheduling point, events (disruptions such as new jobs, machine breakdowns, or processing time variations) are considered in the mathematical formulation as new inputs, affecting the generation of the next schedule as those events represent changes in the scheduling environment.

The problem formulation considers three input sets that define the environment to deal with: J represents the set of jobs (from 1…n) to be scheduled in the permutation flow shop problem, M identifies the processing machines (from 1…m) in the environment, and O defines the operations specified at each machine for each job.

Inputs used by the model are listed below:

• Factors related to the readiness of jobs and machines:

  ○

  rl_i is the time when job J_i is available for being processed after arriving to the shop floor (known as release time).

  ○

  rt_j is the time when machine M_j is ready to process an incoming job (known as ready time).

• Jobs-related specification factors:

  ○

  p_ij indicates the processing time needed by the job J_i to be processed on the machine M_j.

  ○

  d_i represents the due date for job J_i, as requested by the client.

  ○

  w_i indicates a weight for the job J_i, representing its urgency.

• Predictive-reactive-related factors:

  ○

  RT is the current rescheduling instant time.

  ○

  $S_{i,j}^{baseline}$ represents the starting time of job J_i on machine M_j in the predictive baseline schedule calculated initially.

• Disruption events-related factors:

  ○

  $B_{start}^J$ represents the starting time of a breakdown disruption for machine M_j.

  ○

  $B_{end}^J$ represents the end time of a breakdown disruption for machine M_j.

Variables optimized and calculated by the model are described below:

• x_ij are binary variables indicating the position of each Job J_i in the schedule:

  $$\forall i, j \in J: x_{ij}=\{\begin{array}{c}1, if J_i is at j location in the schedule\\ 0, otherwise\end{array}$$
• S_i,j represents the starting time of job J_i on machine M_j in the calculated new optimal schedule.
• C_i indicates the completion time of job J_i, and it depends on the competition time on each machine M_j (C_i,j).
• y_i,j,1, y_i,j,2, and y_i,j,3 are binary variables that represents three possible situations of machine breakdowns:

  ○

  $\forall i\in J \wedge j\in M: y_{i,j,1}$ is 1 (job already processed situation) in case operation of job J_i on machine M_j $\left(O_{i,j}\right)$ finishes before we have a breakdown in the machine; otherwise takes 0 value.

  ○

  $\forall i\in J \wedge j\in M: y_{i,j,2}$ is 1 (conflict situation) in case operation $O_{i,j}$ is not finished when the breakdown occurs; otherwise takes 0 value.

  ○

  $\forall i\in J \wedge j\in M: y_{i,j,3}$ is 1 (job starting time displacement situation) in case operation $O_{i,j}$ needs to be done after a machine breakdown; otherwise takes 0 value.

As objectives to optimize, we need to minimize the following to get the Pareto frontier (PF): makespan (Cmax), total weighted tardiness (TWT), and stability (STB).

$$\min PF \left(C_{max}, TWT, STB\right)$$

(1)

Makespan (first objective function) indicates the maximum completion time for all jobs. It is a common objective to be minimized in permutation flow shop problems and it is calculated as the completion time of the last scheduled job in the sequence:

$$C_{max}=\underset{i=1,\dots ,n}{\mathit{max}}\left(C_i\left(\pi \right)\right)=C_n$$

(2)

Completion time for each job depends on the processing in the last machine M in a permutation flow shop problem:

$$\forall i\in J: C_i=C_{i,j=M}$$

(3)

The three defined machine breakdowns situations are considered in this mathematical formulation to adjust the competition time of jobs in the machines:

Job already processed situation:

$$\forall i\in J \wedge \forall j\in M:C_{i,j}+\left(1-y_{i,j,1}\right)·BigM\ge S_{i,j}+{{\displaystyle \sum }}_{k=1}^n{x}_{ki}·p_{kj}$$

(4)

$$\forall i\in J \wedge \forall j\in M:C_{i,j}-\left(1-y_{i,j,1}\right)·BigM\le S_{i,j}+{{\displaystyle \sum }}_{k=1}^n{x}_{ki}·p_{kj}$$

(5)

Conflict situation (in this case, job needs to re-start after machine is ready):

$$\forall i\in J \wedge \forall j\in M:C_{i,j}+\left(1-y_{i,j,2}\right)·BigM\ge S_{i,j}+{{\displaystyle \sum }}_{k=1}^n{x}_{ki}·p_{kj}+(B_{end}^J-B_{start}^J)$$

(6)

$$\forall i\in J \wedge \forall j\in M:C_{i,j}-\left(1-y_{i,j,2}\right)·BigM\le S_{i,j}+{{\displaystyle \sum }}_{k=1}^n{x}_{ki}·p_{kj}+(B_{end}^J-B_{start}^J)$$

(7)

Job starting time displacement situation (in this case, job waits to start):

$$\forall i\in J \wedge \forall j\in M:C_{i,j}+\left(1-y_{i,j,3}\right)·BigM\ge Max(S_{i,j}, B_{end}^J)+{{\displaystyle \sum }}_{k=1}^n{x}_{ki}·p_{kj}$$

(8)

$$\forall i\in J \wedge \forall j\in M:C_{i,j}+\left(1-y_{i,j,3}\right)·BigM\ge Max(S_{i,j}, B_{end}^J)+{{\displaystyle \sum }}_{k=1}^n{x}_{ki}·p_{kj}$$

(9)

The next equation ensures that only one out of the three previous situations occurs for a job, when a machine breakdown event arises in the production environment:

$$\forall i\in J \wedge \forall j\in M:{{\displaystyle \sum }}_{k=1}^3{y}_{i,j,k}=1$$

(10)

Starting times for jobs J_i on each machine M_j, need to be calculated depending on the completion times:

$$\forall i\in J \wedge j\in M:S_{i,j}=Max(C_{i,j-1}, C_{i-1,j})$$

(11)

To linearise the Max function and completely model the starting times, we include the equations below:

A job cannot start in a machine if a previous job has not finished on the same machine:

$$\forall i>1\in J \wedge \forall j\in M:S_{i,j}\ge C_{i-1,j}$$

(12)

and if its previous operation has not yet finished:

$$\forall i\in J \wedge \forall j>1\in M:S_{i,j}\ge C_{i,j-1}$$

(13)

Starting time in the first machine of the production environment needs to respect the jobs release times:

$$\forall i\in J:S_{i,1}\ge r{l}_i$$

(14)

Moreover, the formulation needs to respect the machine readiness specifications:

$$\forall i\in J \wedge \forall j\in M:S_{i,j}\ge r{t}_j$$

(15)

The second objective considered in this problem is the total weighted tardiness (TWT) that depends on the differences between the due dates of the jobs and their completion time in the permutation flow shop system, weighted by its urgency, that is:

$$TWT={{\displaystyle \sum }}_{i=1}^{n}Max(C_{im}-d_i,0)·w_i$$

(16)

The next equations are included to linearise the Max function:

$$TWT\ge {{\displaystyle \sum }}_{i=1}^n(C_{im}-d_i)·w_i$$

(17)

$$TWT\ge 0$$

(18)

Stability (STB) is the third objective optimized in our problem statement. It represents the differences in starting times of unprocessed scheduled jobs in the baseline schedule of the predictive-reactive paradigm versus their new starting times as calculated by the optimization. STB is calculated following the next equation:

$$STB=\frac{1}{n_{not processed}}·{{\displaystyle \sum }}_{i=1}^n\left(\left|S_{i,1}-S_{i,1}^{baseline}\right|+\frac{scale}{\sqrt{S_{i,1}^{baseline}-RT}}\right)$$

(19)

As the absolute value function is non-linear and non-differentiable, we add the next equations to model STB in a suitable shape for the MILP formulation. We initially replace the absolute function by a variable, DeltaStartTime:

$$STB=\frac{1}{n_{not processed}}·{{\displaystyle \sum }}_{i=1}^n\left(DeltaStart Tim{e}_i+\frac{scale}{\sqrt{S_{i,1}^{baseline}-RT}}\right)$$

(20)

Then, we add binary variables to define two different situations (d₁ and d₂):

$$\forall j\in J:0\le S_{j,1}\le BigM$$

(21)

$$\forall j\in J:0\le DeltaStart Tim{e}_j-\left(S_{j,1}-S_{j,1}^{baseline}\right)\le 2·BigM·d_{2j}$$

(22)

$$\forall j\in J:0\le DeltaStart Tim{e}_j-\left(S_{j,1}^{baseline}-S_{j,1}\right)\le 2·BigM·d_{1j}$$

(23)

$$\forall j\in J:d_{1j}+d_{2j}=1$$

(24)

In case d₁ takes value 1, it means that the DeltaStartTime variable will take: $S_{j,1}-S_{j,1}^{baseline}$; otherwise $S_{j,1}^{baseline}-S_{j,1}$.

Finally, we add equations to ensure that the jobs can only be located at just one position in the schedule and that there cannot be more than one job in the same position:

$$\forall i\in J:{{\displaystyle \sum }}_{j=1}^n{x}_{ij}=1$$

(25)

$$\forall j\in J:{{\displaystyle \sum }}_{i=1}^n{x}_{ij}=1$$

(26)

3. Proposed Solution

The architecture of the proposed rescheduling system and the HDNSGA-II proposed algorithm are subsequently described.

HDNSGA-II is a population algorithm based on the NSGA-II technique, developed by [21], which incorporates various improvement mechanisms. In particular, it adds a probabilistic model for estimating distributions to restart the population when stagnation occurs, a local tabu search process, and an initialization of the population based on a GRASP procedure and prior knowledge. In addition to the improvements introduced in the NSGA-II, the algorithm is applied to a context where the NSGA-II has never been applied, that is, in the multi-objective framework for task rescheduling. Additionally, the HDNSGA-II algorithm is compared with the RIPG algorithm [51].

3.1. Rescheduling Architecture

In this paper, the rescheduling strategy used builds on the predictive-reactive approach. Thus, in the first place a baseline schedule is established that is later updated according to the disruptions that appear in the system. It is essential to indicate the appropriate period for the rescheduling cycles, depending on the dimensions of the problem. In the paper, this period is obtained dividing the maximum jobs’ completion time (Cmax) by the total number of rescheduling points to be executed in the system (five rescheduling points were considered as being an adequate number to evaluate the capacity of adaptation of the architecture without having to excessively increase the number of executions in the system) [51].

3.2. Hybrid Dynamic NSGA-II Algorithm

The HDNSGA-II algorithm proposed in this study is based on the NSGA-II multi-object evolutionary algorithm, developed by [21], considered one of the best multi-object techniques in the scientific literature. The HDNSGA-II algorithm adapts the NSGA-II technique to dynamic rescheduling environments, hybridizing it with estimation of distribution algorithms (EDAs) and implementing a memetic approach to improve each individual in the population based on a local search using a Tabu technique.

The built-in probabilistic learning model is based on the probability of dependence of each job on their predecessors and successors and on the probability of sorting and placing each job in the sequence corresponding to the best individuals. The model allows to generate good quality artificial chromosomes (new individuals) when there is a stagnation of the algorithm, avoiding convergence towards local optimal solutions.

There are previous studies that use memetics and EDAs. Thus, [57] proposes a genetic memetic algorithm for a bi-objective flow shop problem with permutation called NNMA that integrates NEH heuristic (as a local search improvement procedure) with NSGA-II metaheuristic. On the other hand, [58] develops a hybrid genetic algorithm for a mono-objective flow shop problem with permutation. In addition to classic crossover and mutation operators, artificial chromosomes are generated through estimation of distributions algorithms (EDAs) modelling, learning, and sampling. This hybridization seeks to develop the solution population both evolutionarily and artificially. The proposed algorithm is called ACGA (artificial chromosomes with genetic algorithm), applying genetic evolution until the process reaches a stable situation. At that point, the distribution estimation algorithm (EDA) is alternated with the genetic algorithm, during a certain number of pre-set iterations. The EDA strategy is based on the combination of univariate and bivariate modelling. The univariate probabilistic model represents the importance of job order in the sequence, and the bivariate model represents the block structure in the sequence, that is, the probability that one job precedes or succeeds another. Figure 1 shows an outline of the proposed HDNSGA-II algorithm, consisting of the following steps:

Step 1. The population of solutions is initialized. Initialization incorporates knowledge of previous reschedules when building individuals taking advantage of previously performed optimizations in order to start from a good set of initial solutions. If the system is in the first rescheduling period, lacking knowledge about previous searches, initialization is performed using a GRASP (greedy randomized adaptive search procedure) algorithm along with a tabu local search procedure.

This idea of GRASP initialization is used to obtain good candidate solutions at the start of a genetic algorithm [59]. During this initialization, two solutions are generated by applying the NEH heuristic with the aim of minimizing makespan and the NEH-EDD technique in order to minimize total weighted tardiness [60]. In the NEH-EDD procedure, the jobs are initially scheduled according to their delivery date (applying the EDD rule) and later, the final sequence is obtained by applying NEH. The remaining N-2 individuals, N being the size of the initial population, are generated randomly to subsequently apply a process to improve the quality of each individual, using a GRASP algorithm together with a local tabu search.

The GRASP algorithm [59,61] is an iterative search process in two phases, where each iteration carries out a constructive process and a local search procedure. In the construction phase, a greedy randomized function is used to construct initial solutions, generating feasible solutions at each iteration. Subsequently, this solution is exposed to a local search procedure to improve its quality. Finally, the best solution found in all iterations is returned. In the construction phase, a greedy randomized adaptive procedure is applied, based on a restricted list of candidates, called RCL (restricted candidate list), where elements are iteratively incorporated into a structure, initially empty, until a solution of the problem is obtained. The choice of the next element to include is based on heuristic information on how convenient it is to include the element in the solution. A single execution of the GRASP algorithm is carried out for each solution to be generated in order to quickly obtain an initial set of solutions.

In GRASP construction phase, the evaluation of incremental costs is carried out by calculating the distances after incorporating new candidate elements (jobs) in the solution through the CDA (crowding distance assignment) operator of the NSGA-II. After the incremental evaluation, the best solutions will be those with the highest CDA value, within the set of partial non-dominated solutions, in order to achieve greater diversification in the search process. The Tabu search used in the construction of the solution initial population follows a scheme based on the neighbourhood exchange operator by permutation of two randomly selected jobs.

When the dynamic system is at rescheduling points after the initial one, an alternative “population reinitialization method” is used. In these situations, a prior knowledge mechanism is incorporated into the proposed HDNSGA-II method. In this case, N/4 individuals, N being the population size, are selected from the Pareto front obtained in the previous rescheduling point by the HDNSGA-II metaheuristic. For each of the chosen solutions, jobs already processed in the system are eliminated and jobs previously scheduled are assigned in the same order specified by the selected non-dominated solution. Subsequently, new jobs arriving at the system are scheduled according to NEH and NEH-EDD heuristics. Thus, for each of the N/4 solutions found, two solutions are generated and consequently N/2 individuals from the initial population are covered. The remaining N/2 solutions in the population are generated as in the first rescheduling period, that is, by random initialization together with a GRASP and Tabu search-based improvement procedure. The reason for this random initialization in half population is to allow the algorithm the possibility of obtaining many changes on the new Pareto front.

Step 2. The elements of the population are sorted using the NSGA-II fast non-dominated sorting method.

Step 3. According to the crowding distance assignment (CDA) method of the NSGA-II, a distance value assigned to each individual in the population is calculated. The MCDA (modified crowding distance assignment) method applied in the RIPG is not used in this case as selection mechanism. The MCDA method was proposed to avoid population stagnation, avoiding the selection of the same solution in consecutive iterations, when there is no improvement [62]. In the case of HDNSGA-II, this stagnation is controlled by applying EDAs, which reinitialize the solution population when a certain threshold of the consolidation ratio is exceeded (Step 4).

Step 4. The descendant population generation method is selected using the traditional evolutionary genetic approach or through the generation of artificial chromosomes, depending on the EDA implemented. To select one or the other method, the mechanism proposed by [63] is used, considering the consolidation ratio as an online mechanism for stopping and detecting stagnation of solutions in multi-objective problems. This ratio is a convergence metric based on the concept of dominance and the total set of non-dominated solutions found during the entire execution of the algorithm. It is defined as the relative number of non-dominated solutions that still hold on the approximate Pareto front calculated in the current iteration. In the algorithm improvement phases, the consolidation ratio has a low value, reaching high values as the Pareto front converges. In HDNSGA-II, when the population consolidation ratio reaches a certain threshold, the population is reinitialized by generating artificial chromosomes using an EDA. In this way, the knowledge obtained in previous searches is used to generate as individuals of the new population those with the greatest potential from a probabilistic point of view.

Step 5. If the consolidation ratio has been exceeded, the implemented EDA is used to generate artificial chromosomes until the maximum size of the population is reached. The EDA algorithm consists of two phases: a first phase of modelling and learning and later a solution sampling phase. In the modelling phase, two learning models are used analogously to the proposal presented by [58]: a univariate and a bivariate modelling. The univariate model represents the existing correlations in the order of the different jobs in the sequence. On the other hand, the bivariate model represents the structure of job blocks in the sequence, allowing to evaluate the probability that one job precedes or succeeds another, characterizing the job transition relationships. Finally, in the sampling phase, the solution population in the current generation is reinitialized. For this reason, the two statistics calculated in the modelling phase are used, creating a probabilistic model which evaluates the probability that a job i is located in position i.

Step 6. If the consolidation threshold limit is not reached, the population of descendants is generated by selecting pairs of individuals from the population, by means of a selection process through a binary tournament and applying genetic operators. The one point order (OP) is used as crossing operator. This method has been selected as it provides good results in scheduling problems [64]. On the other hand, inversion is used as mutation operator [65].

Step 7. After crossing and mutating individuals (Step 6) or having generated the population using the EDA (Step 5), a local search is performed on the descendants of the population, specializing and improving the new generation. Therefore, an iterated memetic search is incorporated based on a hybrid algorithm through the local search process mentioned in the RIPG algorithm [51] together with an improvement of the solutions through a tabu search. Hence, in a similar way to RIPG, the selected job is reinserted in n_neigh positions close to a random position in the sequence, obtaining a set of solutions of which only the non-dominated solutions are considered. From the obtained solutions, the solution with the greatest distance (using the CDA method) is selected through the local RIPG search to subsequently improve it by means of a local Tabu search procedure, following the same scheme used in Step 1 of this algorithm.

Step 8. Finally, the total set of non-dominated solutions is returned, storing them in an external file that is updated in each iteration of the genetic.

4. Results

For the algorithm, the benchmark proposed by [51] is used. Instances can be accessed at http://dx.doi.org/10.17632/4p4jcwdwpt.2 (accessed on 20 May 2022) (Mendeley Website).

4.1. Parameter Calibration

The hardware used in the experimentation was a computer with an Intel Xeon X5675 Quad-Core 3.07 GHz processor and 16 GB of RAM. The operating system used was Windows 7 Enterprise Edition, 64-bit architecture. The software was developed on the .NET platform with the C# programming language and using Microsoft Visual Studio 2010 Development Framework.

To fairly compare all algorithms, the same stopping criterion was used. This criterion is defined from different approaches in the literature [64,66,67,68,69,70]. Most of them use a maximum execution time as stopping criterion, estimated in relation to the size of the problem, which is defined by the number of jobs and machines that the system has available. In this paper, the time limit was calculated with the following equation:

$$t=n\times m^2\times 100$$

where t is the total time expressed in milliseconds, n indicates the number of jobs considered in the problem instance, and m is the number of machines defined. The above equation is used to calculate the execution time because both the number of jobs and the number of machines played a role in the complexity of the problem to be solved. In addition, it allows to use more calculation time in problems with greater complexity.

Likewise, an automatic configuration methodology of the parameters defining the algorithms is proposed, based on an extension of the iterated F-Race method, implemented in the irace tool [71]. For this, hypervolume is defined as the metric to evaluate the configurations, as it is the most used criterion. To select the training instances, a complexity analysis is performed based on the results provided by the scientific literature on the Taillard instances [36,72].

A total of six problems have been selected (ta02, ta031, ta047, ta061, ta080, and ta024) as representative instances. Two of them of low complexity, in terms of resolution difficulty, another two of medium complexity, and another two of high complexity. The criterion selected to assess the complexity of an instance was based on a trade-off between the number of non-dominated solutions found in the scientific literature in terms of bi-objective static problems (makespan and total weighted tardiness) and the relative error found in single-objective problems considering the makespan criterion. The instances employed in the calibration phase were not subsequently used for algorithm evaluation in order to avoid overfitting.

After analyzing the Irace results, the HDNSGA-II algorithm has greater variability in the face of changes in the parameters.

Table 1. Automatic HDNSGA-II configuration via Irace.

Parameter	Value	Data Type	Range Established for Irace
Population size (N)	54	Integer	(50, 150)
Crossover probability	0.71	Decimal	(0.5, 0.9)
Mutation probability	0.15	Decimal	(0.05, 0.2)
nneigh (consecutive positions where a job is reinserted in the local search phase)	1	Integer	(1, 12)
Number of iterations after which an offspring population is obtained using the probabilistic EDA method (interval iterations)	9	Integer	(2, 10)
Maximum consolidation ratio. Once passed, the population is reinitialized using the probabilistic model	0.51	Decimal	(0.4, 0.9)
Maximum number of iterations to reach a consolidation rate greater than the maximum threshold	55	Integer	(30, 70)
Maximum number of iterations improving the solution (the solution is improved in multi-objective when the size of the non-dominated solutions set is increased). Used in tabu search (k)	2	Integer	(1, 7)
Number of iterations for which a movement is marked as tabu (tenure factor)	3	Integer	(1, 5)

shows the results of the automatic configuration using the HDNSGA-II algorithms.

4.2. Comparison of HDNSGA-II and RIPG Metaheuristics in Dynamic Multi-Objective Environments

In order to verify the performance of the proposed HDNSGA-II metaheuristic, it is executed together with the RIPG [51] metaheuristic on the 50 benchmark problems, specifically developed in this work for a flow shop rescheduling environment.

The main differences between HDNSGA-II and RIPG are focused on its architecture: HDNSGA-II is a population-based algorithm, whereas RIPG is a constructive algorithm. HDNSGA-II integrates a learning method based on EDAs to learn from past searches (previous knowledge), while RIPG restarts the working set to avoid stagnation effect. Finally, HDNSGA-II integrates an advanced Tabu local search to improve the solutions.

Each algorithm is executed 10 times independently for each of the experiments, in order to be able to perform a statistical analysis of confidence. Wilcoxon statistical test is used to evaluate the comparison between the HDNSGA-II and RIPG at an α = 0.05 level of significance.

Next, a comparison of the metaheuristics is represented for each of the performance metrics used and based on the types of problems analyzed. Figure 2 shows the evolution of the median of the hypervolume during 10 independent executions of the algorithms. It can be seen how RIPG performs better, reaching a higher hypervolume value than HDNSGA-II in small-sized instances (20 jobs). With 50, 100, and 200 jobs, HDNSGA-II exceeds RIPG, clearly accentuating this difference the larger the size of the problem to be solved.

The unary multiplicative epsilon indicator behaves in a similar way to hypervolume, as shown in Figure 3. In this case, the lower the value, the better the algorithm.

Regarding the ratio of non-dominated solutions (see Figure 4), RIPG exceeds HDNSGA-II in instances of 20 jobs. In the rest of the problems, HDNSGA-II clearly improves, reaching a ratio of non-dominated solutions of 1 against the RIPG, which is around 0.25 in most of the problems. Finally, with respect to the D1R metric, the situation is analogous to the rest of the metrics. RIPG is better for scenarios with 20 jobs, and HDNSGA-II far exceeds RIPG the larger the problem size, as shown in Figure 5.

As a result of the performed analysis, HDNSGA-II performs worse than RIPG technique for small instances (20 jobs). However, when the number of jobs and machines increases, HDNSGA-II performs better than the non-population RIPG technique. One of the reasons for this worsening of RIPG as the size of the problem increases is the growth of the number of non-dominated solutions in the constructive/destructive process of the algorithm, increasing the computational strength of the technique. To statistically demonstrate this conclusion, the results of the Wilcoxon statistical test are shown below, depending on the dimensions of the problem. Thus,

Table 2. Wilcoxon test results on metaheuristics for problems with 20 and 50 jobs.

20 Jobs	Percentage			50 Jobs	Percentage
Metric	W−	W+	W=	Metric	W−	W+	W=
Hipervolume	90.67	0.00	9.33	Hipervolume	5.33	82.67	12.00
D1R	92.00	0.00	8.00	D1R	8.00	66.67	25.33
RNDS	57.33	5.33	37.33	RNDS	0.00	98.67	1.33
Epsilon	80.00	0.00	20.00	Epsilon	9.33	69.33	21.33

describes the comparative results between HDNSGA-II and RIPG algorithms in problems with 20 and 50 jobs. This table shows HDNSGA-II outperforms RIPG (W+) if it has a worse performance (W−) or if there are no significant differences between them (W=). The best results of RIPG can be seen in problems with 20 jobs, improving in all metrics to the HDNSGA-II. Better results are obtained in 90.67% of the instances for hypervolume, 80% for the epsilon unary indicator, 92% for D1R, and 57.33 for the ratio of non-dominated solutions. For issues with 50 jobs, HDNSGA-II outperforms RIPG on all performance metrics evaluated.

Table 3. Wilcoxon test results on metaheuristics for problems with 100 and 200 jobs.

100 Jobs	Percentage			200 Jobs	Percentage
Metric	W−	W+	W=	Metric	W−	W+	W=
Hipervolume	0	100	0	Hipervolume	0	100	0
D1R	0	100	0	D1R	0	100	0
RNDS	0	100	0	RNDS	0	100	0
Epsilon	0	100	0	Epsilon	0	100	0

presents the results of the Wilcoxon test for the largest problems (100 and 200 jobs). It is observed how HDNSGA-II surpasses RIPG in all cases. Therefore, it can be concluded that HDNSGA-II performs better in dynamic multi-objective environments than RIPG, except in smaller problems (20 jobs).

Below is the evolution of Pareto fronts in some instances selected for the HDNSGA-II and RIPG algorithms at different rescheduling points (nevertheless, all Pareto fronts obtained with RIPG and HDNSGA-II can be found on http://dx.doi.org/10.17632/4p4jcwdwpt.2 (accessed on 20 May 2022)—Mendeley Website). Different symbols and grey levels in the charts represent different rescheduling points.

Figure 6 depicts the Pareto fronts obtained by HDNSGA-II at each rescheduling point in a problem with 20 jobs and 10 machines.

Figure 7 shows the Pareto fronts obtained by RIPG, observing its better performance against the HDNSGA-II by allowing to distribute in a more uniform way the non-dominated solutions and covering better alongside the three axes (makespan, total weighted tardiness, and stability), as it is clearly shown in rescheduling points 4 and 5.

Figure 8 illustrates the dynamic evolution of the Pareto front obtained by HDNSGA-II in a problem with 100 jobs and 20 machines.

In RIPG (see Figure 9), the solution space is not explored as uniformly as in HDNSGA-II.

Finally, with the aim of being able to make a fair comparison, it should be noted that the execution times used to run every instance are the same for each of the metaheuristics. Figure 10 illustrates a graphical summary of the execution times of each instance according to the size of the problem.

5. Conclusions and Future Lines of Research

Several relevant contributions are made in this study. First, a benchmark has been generated to model dynamic rescheduling problems incorporating potential disruptions in the production environment. Likewise, a periodic rescheduling architecture has been designed and implemented, based on a predictive-reactive strategy. On the other hand, a population metaheuristic (HDNSGA-II) has been developed and compared with another non-population metaheuristic (RIPG) in dynamic rescheduling systems. Finally, it should be noted that the proposed HDNSGA-II algorithm incorporates the knowledge gained in previous rescheduling points in the population reinitialization process.

The HDNSGA-II algorithm proposed in this study notably improves the RIPG—commonly used in the state of the art of bi-objective flow shop optimization problems—except for small problems (20 jobs)—in all the performance metrics evaluated. On the other hand, it should be noted that the RIPG technique is more robust than the HDNSGA-II population technique since any parameterization of the algorithm achieves similar results in median value. Finally, the number of evaluations of the objective functions is greater in the RIPG algorithm than in the HDNSGA-II. This is due to the greedy phase of solution construction, where the set of non-dominated solutions has to be maintained. For this reason, the number of iterations executed by RIPG is less than in HDNSGA-II when scaling the number of objective functions.

As future lines of research, the impact of using probabilistic models (EDAs) in the HDNSGA-II algorithm and the consideration of previous rescheduling points in the population reinitialization process in future rescheduling periods could be analyzed. Likewise, the study of local search in the HDNSGA-II genetic algorithm could be deepened. The results of the automatic parameterization given by Irace in the algorithm do not ensure the efficiency of the local search in the genetic, since the optimal parameterization of HDNSGA-II only takes into account a single neighboring position in which to reinsert the selected job in the local search phase (parameter named nneigh). The interaction between the two steps applied in the local search—GRASP process and improvement of the solution through a Tabu search—could also be analyzed.

On the other hand, the influence of the baseline used in the evaluation of the objective stability function could also be analyzed. Likewise, the dynamic system could be evaluated according to the number of rescheduling points chosen. In the study, all the experiments were analyzed using five rescheduling points, but the variations could be evaluated with a number of rescheduling points between 0 and 1000, as is done in [73]. Finally, the proposed metaheuristics could be adapted to dynamic environments in problems called many-objective optimization, where the number of objective functions is greater than three.