Application of GATS, a hybrid mega-heuristic model, and DOE, to solve flexible flow shop scheduling problems: a case study

Introduction

Scheduling problems define the sequence in which a group of orders is efficiently processed through several machines. Flow shop scheduling (FSS) problems consider m machines and n orders, and all orders are processed in the same sequence. Parallel machine scheduling (PMS) problems involve sending n jobs to m parallel machines. An order can be processed on any machine. Machines can be homogeneous or heterogeneous. Machines are homogenous when they have the same processing time for each job. Machines are heterogeneous when the times to process the same job on different machines are different.

Flow shop scheduling problems are problems that combine FFS problems and PMS problems. So, FFSS problems are more complicated than FFS problems and PMS problems. FFSS problems include dispatching n jobs across w stations; each station has several parallel machines. Each job is executed sequentially through the stations in the same sequence, and only one machine at each station is selected for execution.

The problem to be solved is an FFSS problem, with the assumption that the orders are ready at the start of the scheduling process. The objective of the problem is to minimize the total tardiness of orders. The constraints are on the sequence of orders, on the sequence of operations in each order, on the allocation of orders on parallel machines in each station, on machine changeover time, and on batches produced in each machine.

The model of the problem is built based on the above assumptions, objectives, and constraints. The GATS algorithm is a combination of GA and TS, with the foundation of GA. Based on the model of the problem, the GATS algorithm will find a good solution for the problem. Design of experiment (DOE) is used to optimize the parameters of the GATS model. The solutions of GATS and GATS with DOE are compared with the solutions of the traditional heuristics being used to evaluate their effectiveness.

Literature review

Flexible flow shop scheduling

Flow shop scheduling is renowned and classified as an NP-hard optimization problem (Berlinska and Przybylski, 2021), and several algorithms have been developed to overcome this problem (1, Lee and Loong, 2019). Palmer et al. and Gupta et al. proposed heuristic methods to solve n-job problems on m-machines (2). Chen et al. applied GA to these problems. However, the problem solving time of GAs is quite long.

The PMS problem has two distinct decisions: allocation and sequencing. Allocation is a decision concerning the assignment of jobs to machines, while sequencing is to order the jobs assigned to each machine (3). When the number of machines is large, mega-heuristic algorithms such as GA and TS are usually used instead of optimal methods to solve the problem. To reduce the time to solve the problem, one solution is to coordinate between GA and TS (where GA is used for global search and TS is used for local search).

Genetic algorithm

Genetic algorithm, first introduced by Holland in 1975, is a powerful search engine to solve optimization problems using evolution and natural selection of selected individuals called chromosomes. Feasible solutions to the problem are modeled by chromosomes. The population of chromosomes represents the solution space of the problem. Chromosomes are represented by strings. A method of coding is used to define the string format for the chromosomes.

Each chromosome has a corresponding fitness value. The fitness function is a measure of the extent to which the objective of the problem is achieved. The fitness function is derived from the objective function of the problem.

An initial population is made up of several chromosomes. The next population is created by applying genetic operators to the chromosomes of the current generation. Genetic operators include selection, crossover, mutation, and replacement. The algorithm creates a new population from the existing population. The next population is probably better than the current population. This process is repeated until a specified stopping condition is met.

Tabu search

Tabu search, introduced by Glover and Laguna in 1997, is also an effective search engine to solve optimization problems. Feasible solutions to the problem are modeled by strings. The population of strings represents the solution space of the problem. Strings are represented by codes. A method of coding is used to define the string format for the codes.

Each string has a corresponding evaluation value. The evaluation function is a measure of the extent to which the objective of the problem is achieved. The evaluation function is derived from the objective function of the problem. The F-best value is the best evaluation value found during the search.

Tabu search explores the solution space beyond local optimality. The properties of the search path are memorized, and choices are made to guide the search out of the local optimum and into different regions. Some moves to previously explored areas are prohibited to avoid local optimization. Recent moves are taboo and stored in the tabu list. The tabu list identifies all moves that do not apply to the current solution. The size of the tabu list is an algorithm parameter that needs to be determined.

An initial solution is identified. The neighborhood operator will determine the neighborhood region for the current solution. The next solution, which may not be as good as the current solution, is determined by applying the selection operator to select the best solution in the current neighborhood region. The selected solution must not violate the tabu list. The process is repeated until a specified stopping condition is met.

The flexible flow shop scheduling problem

The problem to be solved is an FFSS problem with nine orders, O_i, i = 1 ÷ 9, and scheduling on four stations, S_j, j = 1 ÷ 4. Each order consists of many products, manufactured in batches at each machine in the stations. Each station has three homogeneous machines. The due time D_i, the processing time P_ij, and the batch time B_ij for order i, i = 1 ÷ 9, on station j, j = 1 ÷ 4, are estimated in Table 1.

The setup times of the machines in station j are estimated in Table 2.

The model is set up with variables. TS_ijk being the time to start order O_i, i = 1 ÷ 9 on station S_j, j = 1 ÷ 4, machine k, k = 1 ÷ 3; X_ijk being the binary variable, whether order O_i, i = 1 ÷ 9 will process on station S_j, j = 1 ÷ 4, machine k, k = 1 ÷ 3 or not; TE_ijk being the time to end order O_i, i = 1 ÷ 9 on station S_j, j = 1 ÷ 4, machine k, k = 1 ÷ 3; T_i being the tardiness time of job i. The model of the problem is as follows:

St.

– TE_ijk = TS_ijk + (S_j + P_ij) * X_ijk, i = 1 ÷ 9, j = 1 ÷ 4, k = 1 ÷ 3

– T_i = max (TE_i4k – D_i, 0), i = 1 ÷ 9, k = 1 ÷ 3

– Σ_kX_ijk = 1, Σ_iX_ijk = 1, i = 1 ÷ 9, j = 1 ÷ 4, k = 1 ÷ 3

– TS_ijk ≥ Max (TS_i(j–1)k + B_i(j–1), TE_(i–1)jk), i = 1 ÷ 9, j = 1 ÷ 4, k = 1 ÷ 3

– TS_ij1 = max(0, min(TE_(i–1),j1)), i = 1 ÷ 9, j = 1 ÷ 4

– TS_ijk = max(min(TE_(i–1)jk), TS_ij(k–1) + B_ij), i = 1 ÷ 9, j = 1 ÷ 4, k = 2 ÷ 3

– TS_ijk, TE_ijk ≥ 0; X_ijk = {0,1}, i = 1 ÷ 9, j = 1 ÷ 4, k = 1÷3

The company is currently using the LPT dispatching method. The objective value of T is 46.93 (h).

The GATS model for the Flexible flow shop scheduling problem

The above FFSS problem is a non-linear problem with a solution space of 4*9!, or 1,451,520. The GATS model is used to solve the problem. In the model, GA is used to perform a global search of the solution space, and TS is used to perform a local search to refine the solution found by GA. The GATS procedure is as follows:

Step 1: Initialize the GATS model.

Step 2: Generate the initial population, P⁽⁰⁾. Set k to 0.

Step 3: Generate elite population P_E^(k).

Step 4: Generate the genetic population P_G^(k).

Step 5: Generate the neighborhood population P_N^(k).

Step 6: Generate the next population P^(k+1). Set k = k + 1.

Step 7: Check the termination rule. If not, return to Step 3. If yes, finish the loop.

Step 8: Run the algorithm a number of times to choose the best scheduling result.

Step 1: Initialize the GATS model.

This step sets up factors in GATS models, including the method of coding, the GA parameters, the TS parameters, and the termination rule.

The method of coding: Each chromosome C is a string of four sub-chromosomes, S_j, j = 1 ÷ 4, corresponding to four stations. The orders are numbered from 1 to 9. Each sub-chromosome is a string of nine genes, G_i, i = 1 ÷ 9, corresponding to nine orders. The sequence of genes in a sub-chromosome represents the sequence of orders scheduled in the corresponding station:

The GA parameters include fitness function, population size, and the parameters of GA operators, including selection, crossover, mutation, and replacement operators. The fitness function F is defined as F_i = T_max – T_i, where F_i and T_i are the fitness and objective values of chromosome i and T_max is the maximum objective value in the population. The crossover method is POX (precedence operation crossover), the mutation method is REM (reciprocal exchange mutation), and the replacement method is acceptance threshold. The model parameters P, P_c, P_m, and K are chosen as follows:

The TS parameters include the neighborhood operator and the tabu list. The neighborhood operator uses the SWAP method to find the neighborhood chromosomes of a chromosome. The tabu list contains the chromosomes found in the previous iterations. At the end of each iteration, chromosomes moving into the next population must not be on the tabu list.

The termination rule: The best objective value of the population T_min does not improve or decrease after 10 consecutive iterations.

Step 2: Generate the initial population P⁽⁰⁾ and set k = 0.

The initial population consists of nine chromosomes. There are four chromosomes generated from four heuristic rules: EDD, ERD, SPT, and LPT. The remaining chromosomes R1, …, R5 are randomly generated. The chromosomes in the initial population, arranged in descending order of their objective values with their corresponding objective and fitness values, are shown in Table 3.

This step also initializes the tabu list, TL, containing the chromosomes in P⁽⁰⁾.

Step 3: Generate an elite population P_E^(k).

This step uses the selection operator to generate the elite population P_E^(k) from P^(k). Each chromosome in the current population has a corresponding fitness value F_i and is selected for inclusion in the elite population P_E^(k), with the selection probability P_i determined as follows:

The selection probabilities P_i are calculated as shown in Table 3. Random numbers are generated nine times based on P_i; the chromosomes in P⁽⁰⁾ selected into the population P_E⁽⁰⁾ are as follows:

Step 4: Generate the genetic population P_G^(k).

This step uses the crossover and mutation operators to generate the genetic population P_G^(k) from the elite population P_E^(k). The genetic population P_G^(k) includes the new chromosome generated from the crossover and mutation operators. The chromosomes of P_E⁽⁰⁾ are selected to be included in the crossover list P_c with a crossover probability of 0.8. After generating nine random numbers, the set P_c is determined as follows:

Each pair of chromosomes in P_c is selected to cross over by the POX method, resulting in two new chromosomes in population P^C. R2 and ERD are crossed over to each other and generate two children, C1 and C2. SPT and R4 are crossed over to each other and generate two children, C3 and C4. The chromosomes in P^C and their objective values are shown in Table 4.

The chromosomes of P_E⁽⁰⁾ are also selected to be included in the mutation list P_m, with a mutation probability of 0.2. After generating nine random numbers, the set P_m is determined as follows:

Each chromosome in P_m is selected to mutate by the REM method, resulting in one new chromosome in population P^M. R3 is mutated and generates M1. SPT is mutated and generates M2. The chromosomes in P^M and their objective values are shown in Table 5:

After crossover and mutation, six new chromosomes are created in the population P_G⁽⁰⁾. Their chromosomes and objective values are shown in Table 5:

Step 5: Generate the neighborhood population P_N^(k).

The populations P^(k) and P_G^(k) form the union population P_U^(k) = P^(k) ∪ P_G^(k). This step uses the neighborhood operator to generate the neighborhood population P_N^(k) from the union population P_U^(k). For the first iteration, P_U⁽⁰⁾ includes 15 chromosomes, of which 9 are in P⁽⁰⁾ and 6 are in P_G⁽⁰⁾:

The neighborhood operator swaps adjacent sub-chromosomes in each chromosome to generate neighborhood chromosomes. Each chromosome in P_U⁽⁰⁾ will have three neighborhood chromosomes. The best chromosome will be selected to move into P_N⁽⁰⁾ to go forward. Population P_N⁽⁰⁾ includes the best neighborhood chromosomes, as shown in Table 6:

In P_N⁽⁰⁾, there are two chromosomes, N1 and N2, in the tabu list; the rest are not.

Step 6: Generate the next population P^(k+1).

The step uses the replacement operator to generate the next population P^(k+1) from the populations P^(k) and P_N^(k). The chromosomes from P_N^(k) will be added to the current population P^(k) to make the next population P^(k+1), if they are not in the current tabu list and their objective values exceed an acceptable threshold, defined by the objective value of the threshold chromosome. The threshold chromosome is a chromosome in P^(k) with position n defined by population size P and threshold parameter k as follows:

With a population size of nine and a threshold parameter of two chosen, the threshold chromosome is the fourth chromosome of P^(k) in the top-down ranking. In order to keep the next population size constant, chromosomes in P^(k) with the lowest values are removed from the next population. This step also updates the tabu list by adding the chromosomes moved into the next population P^(k+1).

In this iteration, the threshold chromosome is SPT, with a threshold value of 16.34. Chromosomes N3, N4, and N12 move into, and R3, R5, and LPT move out of the population. The chromosomes in the next population, P⁽¹⁾, are shown in Table 7:

The tabu list is updated after iteration 1 as follows:

Step 7: Check the termination rule.

After iteration 1, EDD is again the best chromosome with the best objective value of 9.41, appearing twice. The termination rule is not satisfied, so iteration 2 is executed. The results after 14 iterations are shown in Table 8.

From the 12th iteration to the 21st iteration, the best objective value remains the same, the termination rule is satisfied, and the algorithm ends. The scheduling result for this run is as follows:

Step 8: Run the algorithm a number of times to choose the best scheduling result.

The algorithm is run 10 times with the results as shown in Table 9.

The best scheduling result is found on the first run. The scheduling sequence C and the objective value T are as follows:

The Gantt chart for the GATS model is shown in Figure 1.

The objective value according to the GATS model (2.37h) is less than the objective value according to the LPT model currently used (46.93h).

The GATS with DOE to solve the FFSS problem

The parameters of the above GATS model were selected empirically, so the results are not very good. Experimental design is used to determine the model parameters. Firstly, a binary experiment is conducted with the model parameters P, P_c, and P_m chosen as the input factors and the total tardiness time T chosen as the output factor. The levels of the input factors are chosen as in Table 10.

Each combination of input factors is tested five times. The total number of experiments is 40. The experimental results are collected. From the data, Analysis of variance is performed as in Figure 2.

From the above ANOVA table, with α of 0.05, the affected factors are factors P and P_c. The values of parameters to give the minimum objective value are shown in Figure 3.

A further experiment is conducted with the two affected factors chosen as the input factors and the total tardiness time T chosen as the output factor. The mutation probability P_m is kept at 0.2. The levels of the input factors are chosen as in Table 11.

There are 25 combinations of input factors. Each combination is experimented with four times. The total number of experiments is 100. The experimental results are collected. From the data, analysis of variance is performed as in Figure 4.

From the ANOVA shown in Figure 4, with α of 0.05, the most affected factor is population size P. The values of parameters to give the minimum objective value are shown in Figure 5.

The GATS model with DOE is run 10 times with the parameters defined by the experiment as follows:

The results of the GATS model with DOE are shown in Table 12.

The best scheduling result is found on the 8th run. The scheduling sequence C and the objective value T are as follows:

The Gantt chart for the GATS model with DOE is shown in Figure 6.

The objective value according to the GATS model with DOE (0h) is less than the objective value according to the GATS model without DOE (2.37h).

Conclusion

The GATS model has been used to solve the FFSS problem with nine orders on four stations and three homogeneous parallel machines. In the model, GA is used as the platform to perform a global search of the solution space, and TS is used to perform a local search to refine the solution found by GA. The results show that the GATS model gives a better objective value of tardiness time than the heuristic LPT method being used.

Design of experiments has been used to optimize the parameters of the GATS model. The results show that the GATS model with DOE gives a better objective value of tardiness time than the GATS model without DOE. The GATS models without and with DOE have been used to solve the FFSS problem with small sizes. Future research will use the models to solve real-world problems.

Author contributions

PN is the thesis advisor for TL. PN has developed the research models for the thesis. TL has collected the data and written a program to run the algorithms based on the models. PN has composed the research article based on the thesis. Both authors contributed to the article and approved the submitted version.

Acknowledgments

We extend our heartfelt appreciation to everyone who has contributed to the completion of this research article, especially our families, the HCMC University of Technology, and the scientific community for their invaluable support. We endorse the fact that your contributions have been instrumental in the successful completion of this work.

References