Keywords

1 Introduction

Combinatorial optimization problems (COPs) consist of situations in which it is necessary to determine, through permutations of elements of a finite set, the configuration of parameters that is more advantageous [26]. Due to its high degree of applicability, many researchers have been using COPs in different contexts. As an example, applications in the logistics [29], vehicle routing [15], railway transport control [22], among other current problems [10]. In particular, one of the most addressed COPs in the literature is production scheduling [27], which, according to Groover [12], is part of the Production Planning and Control activities and is responsible for determining the design of operations that will be carried out, such as: the environment in which products are processed, what resources are used and what is the start and end time for each production order.

Academic research and the development of solution methodologies have focused on a limited number of classic production scheduling problems, one of the most researched is the variation known as Job Shop Scheduling Problem (JSSP) [14], in which a finite set of jobs must be processed by a finite set of machines. In this category of problems, the objective is usually to determine a configuration in the order of processing of a set of jobs, or tasks, to minimize, for example, the time of using resources [39]. In this case, several performance measures are useful to evaluate how satisfactory a given configuration is for a JSSP, with makespan [38], which corresponds to the total time needed to finish the production of a set of jobs, one of the most used.

Belonging to the well-known class of problems NP-Hard, JSSP presents itself as a computational challenge, since it is not a trivial task to develop an approach to determine exact solutions that represent a configuration with an adequate performance measure, within a reasonable time, even considering small and moderate cases [35]. From this need, algorithms that present approximate results in a feasible computational time were developed and applied to JSSP. The main methods used are those composed of meta-heuristics [23], mainly by the Evolutionary Algorithm (EA) known as Genetic Algorithm (GA) [21, 24, 31,32,33]. Even so, the JSSP consists of a class of problems that remain open [6] and with many instances still unsolved in the well-known benchmarks of the area [9]. This is because the existing methods do not have the necessary efficiency to guarantee their practical use.

More specifically, it is possible to highlight some disadvantages in the use of GA in solving COPs [4, 8]. In detail, it is common for this set of techniques that they become stagnant [30], during their iterations, in solutions that are local minimums, which configures the phenomenon known as premature convergence [41]. Also, GAs may require high computational time [20] to obtain good solutions to this type of problem. Therefore, for complex problems, GA needs to be assimilated to specific problem routines to make the approach effective. Hybridization can be a deeply effective way to improve the performance of these techniques. The most common form of hybridization is the addition of GAs to local search strategies and the incorporation of domain-specific knowledge in the search process [28]. In the latter, there are genetic improvement operators through manipulations in specific genes on a chromosome. These have as main objective to provide to individuals who are not able to stand out in a population the reinforcement coming from one or more individuals who have been successful in the adaptation process. In other words, these operators direct the worst individuals in a population to areas known to be good in the search space.

The authors do Amaral and Hruschka JR [2, 3] present an operator in this line of reasoning, entitled transgenic operator and that simulates the process of genetic improvement. To conduct such a procedure, in one of the stages of the GA, the population of the same is replicated to four parallel sub-populations and, in each of these four populations, the best individuals transfer up to 4 genes, based on historical information, to selected individuals. Then, only the best individuals among the four sub-populations remains. Viana, Morandin Junior and Contreras [33] proposed an adaptation of the transgenic operator do Amaral and Hruschka JR [3] to solve a JSSP with GA. The authors propose the identification of relevance in the genes used in the transgenic process through a pre-processing process. However, such preprocessing is computationally time-consuming and may not be viable in large JSSPs.

In this work, we propose a new population guidance operator for GAs: the Genetic Improvement based on Frequency Analysis (GIFA) Operator. Our method consists of a new way to determine the genetic relevance based on the frequency analysis of the genes of individuals who have good fitness values in the population. We also propose the construction of a representative individual that represents this group of good individuals and that it is used in the process of genetic manipulation to guide the worst individuals towards good solutions and, possibly, that these become positive highlights in the population.

This work is divided into five sections. Specifically, in Sect. 2, we describe the JSSP basis. We present, in Sect. 3, the details about the proposed GIFA operator and the requirements that an GA needs to satisfy to use it. Experimental results on different GAs using GIFA and the advancement in the state of the art of JSSPs are presented in Sect. 4. The work is finished in Sect. 5 with conclusions about the developments carried out and future projections for improving the method and possible applications.

2 Formulation of Job Shop Scheduling Problem

We can define JSSP as a COP that has a set of N jobs that must be processed on a set of M machines. Also, each job has a script that determines the order in which it must pass through the machines for its process to be completed. Each job processing per machine represents an operation and the objective of a JSSP can be interpreted as being the challenge of determining the optimal sequencing of operations with one or more performance measures as a guide. The components of this problem follow some restrictions [39]:

  • Each job can be processed on a single machine at a time;

  • Each machine can process only one job at a time;

  • Operations are considered non-preemptive, i.e., cannot be interrupted,

  • Configuration times are included in processing times and are independent of sequencing decisions.

In this work, we adopted makespan (MKS) as a performance measure. The MKS is the total time that a JSSP instance takes to complete the processing of a set of jobs on a set of machines taking into account a given operation sequence.

Mathematically, let’s assume the following components of a JSSP:

  • \(J = \{J_1, J_2,..., J_N\}\) is the set of jobs;

  • \(\mathcal {M} = \{m_1, m_2,..., m_M\}\) is the set of machines;

  • \(O = (O_1, O_2,..., O_ {N\cdot M})\) is a operation sequence that sets the priority order for processing the set of jobs in the set of machines

  • \(T_i (O)\) represents the time taken by the job \(J_i\) to be processed by all machines in its script according to the operation sequence defined in O.

Then, according to [7], the MKS can be defined as the total time that all jobs take to be processed according to a given operation sequence, as presented in Eq. (1).

$$\begin{aligned} \text {MKS} = \max _i T_i (O). \end{aligned}$$
(1)

3 A New Genetic Improvement Operator Based on Frequency Analysis for GA Applied to JSSP

In this section, we will present in detail how the proposed method works. We will specify the idea of determining genetic relevance by analyzing the frequency of genes that represent good characteristics in individuals with adequate fitness values in the population and, with that, we intend to obtain innovation with the following three topics:

  • A new strategy for defining genetic relevance in GAs chromosomes;

  • A new genetic improvement operator that is versatile and can be used in GAs variations,

  • Improving the state of the art of JSSP benchmark results.

3.1 Genetic Representation

Our operator was developed to operate in all GA-like methods with minor modifications. In the meantime, we are going to conduct its fundamentation on a specific encoding. In this case, we will use the “coding by operation order” [5]. In this representation [32], the feasible space of a JSSP instance defined by N jobs and M machines is formed by chromosomes \(c \in \mathbb {N} ^ {N\cdot M}\), such that exactly M coordinates of c are equal to i (representing the job index i), for every \(i \in \{1,2,...,N\}\).

This encoding determines in chromosome the operation priority with respect to machine allocation. For example [31], let’s assume \(c = (2,1,2,2,1,1)\) as being a feasible solution in a JSSP instance with dimension \(2 \times 3\) (\(N=2\) and \(M=3\)). Thus, according to the operations defined in c, the following actions must be carried out in parallel or if the previous action has already been done.:

  • 1st) Job 2 must be processed by the 1st machine of its script.

  • 2nd) Job 1 must be processed by the 1st machine of its script.

  • 3rd) Job 2 must be processed by the 2nd machine of its script.

  • 4th) Job 2 must be processed by the 3rd machine of its script.

  • 5th) Job 1 must be processed by the 2nd machine of its script.

  • 6th) Job 1 must be processed by the 3rd machine of its script.

3.2 Fitness Function

The encoding used makes it natural to define the fitness function of the problem as the makespan of a JSSP instance given according to the stipulated operation sequence. That is, the fitness function [33] used is given according to Eq. (2):

$$\begin{aligned} \begin{array}{llll} F:&{}\mathbb {O} &{} \longrightarrow &{} \mathbb {R} \\ &{}O&{}\longmapsto &{}F(O) := \displaystyle \max _i T_i (O), \end{array} \end{aligned}$$
(2)

in which \(\mathbb {O}\) is the set of all possible operation sequences for the defined JSSP instance.

In this way, for this fitness function, the MKS of the JSSP instance is calculated according to a given operation sequence, then the meta-heuristic must look for an operation sequence in which the MKS is as small as possible and, consequently, the set of jobs must be processed by the set of machines taking the shortest possible time.

3.3 Proposed Genetic Improvement Based on Frequency Analysis Operator

In this work, we propose a new genetic improvement operator for evolutionary algorithms: the GIFA operator. The operator is based on a frequency analysis matrix calculated during the iterations of each GA. GIFA aims to calculate which genes on a chromosome can direct individuals with poor fitness values to better solutions and better search spaces. GIFA has two main stages: the first being defined by the making of the representative individual, that is, an individual that is determined by the configuration of the most frequent genes in the best individuals in the population; and the second stage consists of the use of the representative individual in the transgenic process, that is, the genetic manipulation through the insertion of specific genes of the representative individual in genes of the worst individuals in the population. Below, we present these steps in detail.

Stage 1: Composition of the Representative Individual. Initially, a portion of the population that presents the best fitness values is selected. Specifically, we select \( N_\text {Top}\) individuals who are considered good examples of solutions in the population. Then, for each index job i, a frequency vector \( \vec {v}_i \in \mathbb {R}^ {N \cdot M} \) is associated, in which the number of its occurrences is stored in each coordinate where the product i appears exactly at the position of this coordinate on the chromosomes selected for comparison. In Fig. 1, an example of the calculation of the frequency vectors \( \vec {v}_i \) is presented when considering 4 individuals \( c_1, c_2, c_3, \) and \( c_4 \) with the best values of fitness in a \( 3 \times 2 \) dimension JSSP instance.

Fig. 1.
figure 1

Calculating the frequency vectors (\( \vec {v}_i \)) of the three jobs in each coordinate of the four best chromosomes in the population.

Full size image

Once the vector \( \vec {v}_i \) has been made for every job index i, a chromosome whose coordinates are determined by the job with the highest frequency in this coordinate is defined as a representative individual. That is, each gene (coordinate) of the representative individual is defined as the job index that is most present in this coordinate in the best individuals in the population. It is also possible to establish an order of genetic relevance according to the frequency vectors \( \vec {v}_i \). That is, it is possible to define which genes of the representative individual are more suitable to be transferred in the process of genetic improvement. Such relevance is also defined according to the frequency that the products present in each coordinate of the best individuals so that the genes that present the same job in many good individuals can categorize a “trend” that leads to good fitness values. Therefore, these genes must be considered to be relevant, since they describe a positive characteristic in several individuals that stand out in the population. Mathematically, the representative individual and its genetic relevance are made according to the following procedure:

  1. 1.

    Let \( \mathbf {c}\) be the representative individual and w a vector that designates a score for each of its coordinates, initially null. In the following items, the coordinates of \( \mathbf {c}\) and w are made.

  2. 2.

    We define \( I_1 \) as being \(\text {arg} \displaystyle \max _i \{\vec {v}_{i,1}\}.\) That is, \( I_1 \) is the index of the job that has the highest frequency in the first coordinate of the exemplary individuals. Therefore, the first coordinate of the representative individual is defined as \( I_1 \). Mathematically,

    $$\mathbf {c}_1:=I_1.$$

    In addition, a \( w_1 \) score defined as the maximum frequency shown in the first coordinate of the best individuals is associated with the first coordinate of \( \mathbf {c}\). That is,

    $$w_1:=\displaystyle \max _i\{\vec {v}_{i,1}\} = \vec {v}_{I_1,1}.$$
  3. 3.

    Assign the value 2 to j.

  4. 4.

    We define \( I_j \) as being \(\text {arg} \displaystyle \max _i \{\vec {v}_{i,j}\} , \) that is, \( I_j \) is the most frequent product index in the j coordinate in the \( N_\text {Top}\) individuals. However, in order to guarantee the feasibility of the representative individual, it is necessary to establish two more restrictions:

    1. 4.1

      If the product \( I_j \) is not in M coordinates of \( \mathbf {c}\), then it is defined as \( I_j \) the j-th coordinate of the representative individual. That is,

      $$\mathbf {c}_j:= I_j.$$

      In this case, the respective score is associated with the j -th coordinate of the representative individual as the maximum possible value presented in the j -th coordinate of the best individuals. That is,

      $$w_j:=\displaystyle \max _i\{\vec {v}_{i,j}\} = \vec {v}_{I_j,j}.$$
    2. 4.2

      Otherwise, to guarantee the feasibility of \( \mathbf {c}\), the frequencies of the index job \( I_j \) are disregarded, since it is already arranged in M coordinates of \( \mathbf {c}\) and, therefore, does not can occupy any more of its coordinates. To do so, we must cancel its respective frequency vector, that is,

      $$\vec {v}_{I_j}:= \vec {0}.$$

      To make a new attempt, we must return to item 4.

  5. 5.

    If \(j\ne N\cdot M\) then \(j:= j + 1\) and we must return to item 4. Otherwise, the procedure is finished and we have the representative individual pair and its respective genetic score \( (\mathbf {c}, w) \).

Note that it is not necessary to project the representative individual in the feasible space of the problem since due to its construction and the item 4 above, it is already feasible. In Fig. 2, an example of the calculation of the representative individual (\( \mathbf {c}\)) and the relevance of its genes (w) in a JSSP instance of dimension \( 4 \times 3 \) is presented, taking as best individuals the \( N_\text {Top}= 5 \) individuals with the lowest fitness values available in the population.

Fig. 2.
figure 2

Computation of the representative individual (\( \mathbf {c}\)) and its genetic relevance (w).

Full size image

Stage 2: Use of the Representative Individual in Genetic Improvement. Once the representative individual and the relevance of each of its genes have been calculated, then it is proposed that its most relevant genes be transferred to the worst individuals in the population, thus simulating a mechanism for genetic improvement, or transgenics. For this, we take \( P_\text {Worst}: = \{x_1, x_2, \dots , x_{N_\text {Worst}} \} \) as the set of the worst \( N_\text {Worst}\) individuals in a population. Subsequently, the most significant, or most relevant, \( N_\text {Genes}\) genes of the representative individual are transferred to all individuals in the \( P_\text {Worst}\) maintaining their original positions. This procedure can generate infeasible solutions. Thus, it is necessary to conduct a correction, or projection, process on the individuals resulting from this operation. For this, we carry out the projection through the Hamming distance [37] modifying only the genes that were not received from the representative individual. In this way, the individuals generated in this procedure are projected on the feasible set of the problem, giving rise to the genetically improved individuals \( P_\text {Improved}= \{\hat{x}_1, \hat{x}_2, \dots , \hat{x}_{N_\text {Worst}} \} \).

It is also necessary to establish how many genes will be transferred from the representative individual to the individuals of \( P_\text {Worst}\). For this, we will follow a procedure similar to that of Viana, Morandin Junior, and Contreras [33], which empirically determine that the adequate amount of genes used in the genetic improvement process is given by the root of the number of coordinates of the chromosome. Thus, the process remains advantageous and does not cause early convergence in the population. Thus, in this work, \( N_\text {Genes}\) is defined as \( \text {round}\left( \sqrt{N \cdot M}\right) \). In Fig. 3, an example of the determination of the most significant genes of a representative individual \( \mathbf {c}\) when it is given the scores of his genes w while addressing a JSSP with dimension \(4\times 3\).

Fig. 3.
figure 3

Determination of the most significant genes of a representative individual.

Full size image

Assuming \( N_\text {Worst}= 3 \) and \( P_\text {Worst}= \{x_1, x_2, x_3 \} \) as the set of the worst 3 individuals in a population, the improvement process is shown in Fig. 4 genetic that transfers the \( N_\text {Genes}\) best genes from the representative individual \( \mathbf {c}\) of Fig. 4 to all individuals in the set \( P_\text {Worst}\).

Fig. 4.
figure 4

Genetic improvement proposed. The genes highlighted on a black background are the most relevant, while the genes highlighted with the red sectioned circle are those that need correction.

Full size image

The genetic improvement procedure must be performed after the standard operators of the GA, or the GA-like method used, and right after the generation of a new population. Thus, the set \( P_\text {Worst}\) must be formed by individuals from the new population of the method. Besides, after the application of the genetic improvement, the evaluation of improvement or worsening of the affected individuals is made, so that the genetic changes made will only be saved in individuals who have obtained an improvement in fitness. That is, only individuals who have gained an advantage in the process of genetic improvement will be substituted in the population; the other individuals should be discarded and replaced by new individuals generated randomly.

3.4 Scheme of Use for Proposed Operators: Algorithm Structure

The proposed genetic improvement strategy was developed to be as versatile as possible in the sense that it can be attached to any GA-like method. Thus, the proposed operator must be used after the execution of the original operators of the method considered in order to guide solutions that were not able to stand out through the traditional strategies defined in the method. In other words, to use the proposed operator in a given GA-like method, we must obey the following steps:

  1. 1.

    Define the initial parameters and specifics of the chosen GA-like method.

  2. 2.

    Execute the operators that make up the GA-like method. These being, for example, the operators of crossover, mutation, local search, creation of new population, etc.

  3. 3.

    At the end of an iteration involving the traditional operators of the selected GA-like method, we will make a sub-population \( P_\text {Worst}\) with the worst \( N_\text {Worst}\) individuals in the current population.

  4. 4.

    At the same time, we will select the best \( N_\text {Top}\) individuals in the population to make up the representative individual.

  5. 5.

    Build the representative individual using the strategy described in Stage 1 of the Sect. 3.3.

  6. 6.

    Determine a relevance scale to the genes of the representative individual.

  7. 7.

    Conduct the genetic improvement of the \( P_\text {Worst}\) individuals using the most relevant \( N_\text {Genes}\) genes of the representative individual.

  8. 8.

    Replace in the current population of the method all individuals who obtained an improvement in the fitness value in the process of genetic improvement and return in the execution of the original operators of the considered GA-like method. Those who have not improved should be replaced by new individuals randomly generated according to Levy’s exponential distribution, following the procedure of Al-Obaidi and Hussein [1].

In Fig. 5, we present a flowchart that illustrates the sequence of steps of the proposed genetic improvement process.

Fig. 5.
figure 5

Flow chart of our proposed Genetic Improvement operator for Genetic Algorithm.

Full size image

4 Implementation and Experimental Results

4.1 Experimental Environment

For the conduction of the experiments, we considered two different situations: in the first, we evaluated the impact that the proposed operator causes on five GA-like methods, all of which were obtained using the framework of Viana, Morandin Junior and Contreras [32], in three JSSP instances of varying complexity; in the second, we compare with recent methods in the literature the ability of the proposed operator to look for good solutions in 43 instances of JSSP that make up the area benchmark, with 3 from Fisher and Thompson (FT) [11] and 40 from Lawrence (LA) [19]. In detail, in this second situation, we consider relevant and recent methods which deal with the JSSP with the same specific instances and, when existing, presented in papers published in the last three years. In all, we consider for comparison the following methods: mXLSGA [32], NGPSO [40], SSS [13], GA-CPG-GT [18], DWPA [34], GWO [16], IPB-GA [17] and aLSGA [4]. The proposed algorithm is coded in MATLAB and we performed the evaluations on a computer with 2.4 GHz Intel(R) Core i7 CPU and 16 GB of RAM.

4.2 Results and Comparison with Other Algorithms

For the first testing situation, we will consider five variations of the Viana, Morandin Junior and Contreras [32] framework: a basic GA (GA), GA with Search Area Adaptation (GSA) [36], GA with Local Search (LSGA) [25], GA with Elite Local Search and agent adjustment (aLSGA) [4], and GA with multi-crossover and massive local search (mXLSGA) [32]. In each of these versions, we added the proposed genetic enhancement operator, GIFA, and conducted our evaluations on three JSSP instances: FT 06, with a dimension of \(6 \times 6\), and the best-known solution (BKS) equal to 55; LA 01, with a dimension of \(10 \times 5\), and BKS equal to 666; and LA 16, with a dimension of \(10 \times 10\), and BKS equal to 945. Thus, each GA-like method considered has a version with the proposed operator, represented by the acronym GIFA together with its standard acronym. Our main purpose in this situation is to evaluate the impact of using GIFA in each of the GA-like methods, so we kept the best possible configuration of each of the methods available in the original works, with the exception that everyone had 100 individuals in their populations and run for 100 generations. In addition, we added to each of them the configuration referring to GIFA, which is defined as follows: \(N_\text {Top}= N_\text {Worst}= 10\). In this case, the best value, the worst value, the mean, and the standard deviation (SD) of the makespan values calculated at 35 independent executions of each method on the three JSSP instances considered are presented in Table 1.

Table 1. GA-like methods statistics for 35 executions of each method.
Full size table

Looking at Table 1, we noticed that the operator made all methods more stable, reducing the magnitude of the worst makespan value found, the mean and standard deviation of all of them in all situations where it was possible to have improvement. However, in the most complex instance, the LA 16, our operator was able to improve the best makespan value only in the case of the aLSGA technique. This serves as an indication that the proposed operator brings a considerable increase in the stability of the method, but the ability to explore the search space still has a strong dependence on the original technique used. This is because our GIFA guides the population towards guiding individuals with bad makespan values in regions where individuals with good fitness values are known to increase local exploration and, therefore, find good solutions, but it is up to the base technique to indicate good search regions.

Thus, the second situation considered should serve as an experiment in this sense, so that we can evaluate the ability of the proposed operator to increase the search and exploration power of a given technique. For this, we will add the proposed GIFA operator in a technique already known to be effective in finding good solutions in the JSSP instances that make up the benchmark today: the mXLSGA [32]. In this case, we will evaluate GIFA-mXLSGA at 40 instances LA and 3 FT instances. In Table 2, we presented the results derived from 10 independent executions of our method on the LA and FT instance tests. The columns indicate, respectively, the instance that was tested, the instance size (number of Jobs \(\times \) number of Machines), the optimal solution of each instance, the results achieved by each method considering all the executions (best solution found and error percentage (Eq. (3)), and the mean of the error with respect to each benchmark (MErr).

$$\begin{aligned} \text {E}_\% = 100 \times \frac{\text {Best} - \text {BKS}}{\text {BKS}}, \end{aligned}$$
(3)

in which \(\text {E}_\%\) is the relative error, “BKS” is the best known Solution and “Best” is the best value obtained by executing the algorithm 10 times for each instance.

Table 2. Comparison of computational results between mXLSGA and other algorithms. The symbol “-” means “no evaluated in that instance”.
Full size table

Analyzing Table 2, we can verify that the GIFA operator was able to improve the search capability of the mXLSGA method. Specifically, considering only the LA instances, the use of the proposed operator was able to reduce the magnitude of the average relative error by 0.12, which corresponds to a reduction of \(19.67\%\) of its value. In other words, the GIFA operator made the mXLSGA method able to find the best-known makespan in \(72.5\%\) of LA instances, obtaining an average relative error of 0.49, the lowest of all methods. Concerning FT instances, the proposed GIFA operator did not compromise the search capability of mXLSGA, causing the best-known solutions to be found in all instances. In summary, we can highlight some points when analyzing the results referring to Table 2:

  • There was no worsening of the results in any instance with the use of the proposed operator;

  • The GIFA-mXLSGA method obtained the lowest \(\text {E}_\%\);

  • The proposed operator made mXLSGA able to find the BKS in the LA 22 instance,

  • The proposed operator improved the results of mXLSGA by 7 LA instances.

With the results of the two situations considered, we note that the proposed method is effective in increasing the stability and efficiency of finding good solutions for GA-like methods.

5 Conclusion

The objective of this work was to develop a new GA-like method operator to minimize the makespan in JSSP instances. The proposed technique was a new genetic improvement operator based on a new frequency analysis strategy to detect relevance in genes, titled GIFA operator. To evaluate the proposed approach, experiments were conducted in 43 JSSP instances of varying complexity. The instances used were FT [11] and LA [19]. The results obtained were compared with other approaches in related works: mXLSGA [32], NGPSO [40], SSS [13], GA-CPG-GT [18], DWPA [34], GWO [16], IPB-GA [17] and aLSGA [4].

We evaluate the potential of the proposed operator in two analysis situations. In the first, we involved the use of GIFA in five different GA-like methods, which were simulated by the framework of Viana, Morandin Junior and Contreras [32], and in all cases, the operator increased the stability of the technique considered improving the mean and standard deviation of the solutions found in three instances of JSSP. In the second, the performance of the GIFA used in the mXLSGA [32] was compared with methods that make up the state of the art in the specialized literature and we note that the use of the proposed operator was effective in increasing the search capacity of the mXLSGA, since GIFA-mXLSGA was the method with the lowest average relative error among all the techniques considered. Thus, we conclude that the proposed operator was able to achieve the stipulated objective since it statistically directed the GA-like methods evaluated for search spaces with better solutions.

In future works, we will make use of deep learning techniques to detect relevance during GAs iterations through reinforcement learning approaches, which should make the methodology more robust and accurate. Also, we will add assessments about processing time measurements and expand the methodology to a greater number of instances and benchmarks.