Bohr article

1. Introduction

The process of assigning resources to a set of activities so that they can be completed throughout a period of time is known as scheduling. The order or sequence in which a collection of jobs are to be processed by a number of machines in the most efficient manner can be determined via scheduling problems. In FSS problems, m distinct machines and n distinct jobs are considered; each job comprises m operations, and each operation demands a different machine; also, all of the tasks are processed in the same order; this is known as the processing order.

The company studied is currently having problems with late orders, leading to low customer service level. After analysis, the root cause was found to be due to a bad scheduling method. The company is currently using the EDD heuristic method. Order tardiness times were quite high. The company wanted to improve its scheduling methods with the objective of reducing order tardiness times, thereby improving on-time delivery rates, and enhancing customer service levels.

The problem that needs to be handled is an FSS problem, and it is assumed that the orders are ready before the scheduling process begins. The overall weighted tardiness of orders needs to be reduced as much as possible in order to accomplish the objectives of the problem. The constraints are on the sequence of orders, on the sequence of operations in the orders, and on machine changeover time.

In this paper, given the aforementioned assumptions, objectives, and constraints, a model of the problem is constructed, and a GA algorithm is developed to solve it. The GA algorithm will identify an appropriate solution based on the problem model, and then its efficacy will be determined by comparing that solution to the solution obtained by the currently used heuristic model.

2. Literature review and research methodology

2.1. Flow shop scheduling FSS problems

Flow shop scheduling problems consider different machines and different jobs. Each job consists of different operations and each operation requires a different machine and all the jobs are processed in the same processing order (1). Flow shop scheduling problems are NP-hard combinatorial optimization problems. For such problems, heuristics play a major role in searching for near-optimal solutions (2).

O Etiler, B Toklu, M Atak, and J Wilson developed a genetic algorithm-based heuristic for the flow shop scheduling problem with makespan as the criterion (3). Complex GA algorithms have also been researched to solve the FFS problem effectively. Orhan Engin, Gülsad Ceran, and Mustafa K. Yilmaz had developed an efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems (4).

Genetic algorithms are also combined with other algorithms to solve the FSS problem more effectively. Moch Saiful Umam, Mustafid Mustafid, and Suryono Suryono had combined the tabu search process with a genetic algorithm to solve the flow shop scheduling problem with the objective of minimizing makespan (5). Anna Burduk, Kamil Musiał, Joanna Kochańska, Dagmara Górnicka, and Anastasia Stetsenko had applied tabu search and genetic algorithm to solve production process scheduling problems and found that intelligent methods can find, in relatively short time, the solution that is close to the optimal and acceptable from the problem point of view (6).

This paper researches and applies a simple GA algorithm to solve the FSS problem to get better results than those of the current EDD dispatching method. This model is an initial basic model that can be developed into more complex GA models, or models that combine GA with other algorithms to be able to solve FSS problems more effectively.

2.2. Genetic algorithm

In 1975, Holland was the first to introduce the concept of a genetic algorithm (GA), a form of artificial intelligence search that mimics natural processes like evolution and natural selection by using a set of instructions encoded in each individual’s chromosomes. It is an effective method for resolving optimization issues.

In GA, the solution space is typically represented as a population of chromosomes, with each chromosome standing in for a possible solution. In this concept, strings represent chromosomes. A specific string format can be used to code the chromosomes.

Each chromosome has an associated fitness value. The fitness function quantifies how close the solution comes to solving the problem. From the problem’s goal function, we can infer the fitness function. The first generation is determined by the number of chromosomes that are selected. Selection, crossover, mutation, and replacement are only few of the genetic operators used on the current generation’s chromosomes to produce the new generations.

The algorithm takes a starting population and generates offspring that are, in theory, healthier and more robust than their forebears. This procedure is performed until a criterion for stopping the process is met. Each new chromosome represents a different answer at each generation.

2.3. Research methodology

The FSS problem is an example of an NP-hard problem with a substantial amount of potential solution space. The methodology, used in this research to solve the problem, includes 2 phases:

– Phase A: Construct the model of the problem.

– Phase B: Use GA model to solve the problem.

In phase A, the model of the problem is formulated with the objective of minimizing the total weighted tardiness time and constraint on operation changeover time.

To solve the issue in phase B, a GA model is utilized, which is determined by the model of the problem. The process for the GA is as follows:

Step 1: Set the GA model’s initial conditions.

Step 2: Create the first population P⁽⁰⁾. Set k = 0.

Step 3: Establish the elite population P_E^(k).

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

Step 5: Develop the next population P^{(k + 1)}. Set k = k + 1.

Step 6: Make sure that the termination rule has been followed. In the event that the answer is “No,” back to step 3. If the answer is “Yes,” then the cycle should be completed.

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

Step 1 setups the structure and parameters of the GA model, including the method of coding, the GA factors, and the termination rule.

For coding, the orders are numbered, each gene is corresponding to an order, and each chromosome is a string of genes. The sequence of genes represents the sequence of order scheduled. For example, the chromosome format for a scheduling problem with 10 orders is as follows, the order number of order (where G_i is the order number of order i, i = 1 ÷ 10).

C = [G 1, G 2, G 3, G 4, G 5, G 6, G 7, G 8, G 9, G 10]

The GA factors include fitness function, the population size, and the GA operators. The objective function of the problem is utilized to determine how the fitness function should be formulated. The objective value determines the degree to which one’s fitness level can be improved. The selection operator, the crossover operator, the mutation operator, and the replacement operator are all different types of GA operators.

The rule of termination: After a predetermined number of repetitions in a row, the population’s best objective value Tbest does not become any better.

Step 2 generates the first population P⁽⁰⁾ from solution space, with the population size defined by step 1. This step also starts the algorithm by setting the iteration counting index k to 0.

Step 3 uses the selection operator in order to produce an elite population P_E^(k) from current population P^(k). The fitness function is what the selection operator uses to determine which chromosomes from the current population should be included in the elite population. The higher the fitness value, the greater the probability that an individual will be chosen.

Step 4 the elite population P_E^(k) is used in conjunction with the crossover and mutation operators to produce the genetic population P_G^(k).

The P_E⁽⁰⁾ chromosomes that are included in the crossover list P_c are chosen by the crossover operator, which takes into account the crossover probability. Then, using a crossover technique, we choose certain pairs of P_c chromosomes to transpose into a new set of chromosomes that will become part of P_G^(k).

The crossover method used in this research is POX (Precedence Operation Crossover). POX crosses over 2 parents P1 and P2 to make 2 children C1 and C2 as shown in Figure 1.

FIGURE 1

Figure 1. Precedence operation crossover (POX).

With a given mutation probability, the mutation operator chooses chromosomes from P_E⁽⁰⁾ to add to the mutation list P_m. To create the genetic population P_G^(k), mutations are then picked for each chromosome in P_m using a mutation technique.

The mutation method used in this research is SWAP. SWAP mutates parent P to make child M as shown in Figure 2.

FIGURE 2

Figure 2. SWAP mutation method.

Step 5 generates the next population P^{(k + 1)} from the current population P^(k) and the elite population P_E^(k) by using replacement operator. If the fitness values of the chromosomes in P_G^(k) are higher above an acceptable threshold, then they will be joined to the chromosomes in the current population, P^(k), to produce the next population, P^{(k + 1)}.

The value of the n^th chromosome in the ranking of P^(k) is used to determine the threshold for the ranking. With population size P, threshold value K, n is defined as follows:

n = r o u n d \frac{P}{K}

In order to maintain a stable population size, the chromosomes with the lowest values are eliminated from the population after an influx of newcomers. This step also increases the iteration counting index k by 1 to prepare for the next iteration, if any.

Step 6 checks the termination rule. The algorithm usually terminates after a number of iterations if the objective function is not improved. If the termination rule is not met, the algorithm returns to step 3 for the next iteration. If the termination rule is met, the iteration loop is stopped. One run has finished.

Step 7 runs the algorithm a number of times to choose the best scheduling result among the runs.

The research methodology of the GA model is shown in the following sections.

3. The model of the flow shop scheduling problem

The problem that needs to be solved is an FSS problem (2) with 10 orders, O_i, where i is an integer from 1 to 10, and scheduling on 4 machines, M₁, M₂, M₃, and M₄. Each order is comprised of three distinct pieces, labeled P₁, P₂, and P₃, which are divided among four different machines in the manner shown in Figure 3.

FIGURE 3

Figure 3. The production process.

The weight W_i, i = 1÷10, and the due date D_i, i = 1÷10, of order i are estimated in Table 1.

TABLE 1

Table 1. The weight W_i, i = 1÷10, and the due date D_i, i = 1÷10, of order i.

The processing times P_ij of order i, i = 1÷10, on operation j, j = 1÷8, are estimated in Table 2.

TABLE 2

Table 2. The processing time P_ij of order i, i = 1÷10, on operation j.

The changeover times in hours on operation j, j = 4÷8 are equal to 0, S_j = 0, j = 4÷8. The changeover times in hours on operation j, j = 1÷3 are the same and depend on the current order i = 1÷10, and the next order, i’ = 1÷10, as shown in Table 3.

TABLE 3

Table 3. Changeover time (h) S_j, j = 1÷3.

The model is built up using the start time (TS_ij), the completion time (TE_ij) of order i at operation j, and the tardiness time (Ti) of order i as independent variables.

The constraints on the sequence of operation on each order are as follows:

TS {}_{i4}\geq TE {}_{i1},

TS {}_{i5}\geq TE {}_{i2},

TS {}_{i6}\geq TE {}_{i3},

TS {}_{i7}\geq TE {}_{i5},

TS {}_{i8}\geq \max (TE {}_{i4}, TE {}_{i6}, TE {}_{i7}) .

The start time of order i at operation j, TS_ij, depends on the end time of the previous order i’, TE_i’j, and the changeover time between the orders on operation j.

TS {}_{ij}= TC {}_{i^{'} j}+ S {}_{j}.

The end time of order i on operation j, TE_ij, is determined by the start time and processing time of the order.

TC {}_{ij}= TS {}_{ij}+ P {}_{ij}.

The tardiness time of order i, T_i, is determined by the end time in the last operation and due time of the order.

T {}_{i}= Max (0, TE {}_{i8}- D {}_{i}) .

The objective function that minimizes the total weighted tardiness is defined as follows:

Tbest = Min T,

T = \sum W_{i} * T_{i} (i = 1 : 11)

The company is currently using the EDD dispatching method. The sequence of dispatching S and the value of the objective function T are as follows:

S = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

T = 215.95 (h) .

The Gantt Chart is as in Figure 4.

FIGURE 4

Figure 4. The Gantt chart for the pilot problem by EDD dispatching method.

4. The GA model for the flow shop scheduling problem

The previously mentioned FSS problem is an NP-hard problem, and the total number of possible solutions is 10!, which is equivalent to 3,628,800. The problem is solved by applying the GA model in the same steps as described in the section “2.3. Research methodology”.

Step 1: Set the GA model’s initial conditions

In this stage, GA model factors such as coding technique, GA parameters, and termination rule are set up.

The method of coding: Each chromosome is a string of 10 genes. Each gene corresponds to an order. The orders are numbered from 1 to 10. The sequence of genes represents the sequence of order scheduled. For example, the chromosome of EDD scheduling method is as follows:

C = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

The GA factors include fitness function, the population size, and the GA operators. Here is how we characterize F, the fitness function:

F {}_{i}= T {}_{\max}- T {}_{i}.

When F_i and T_i represent the fitness and objective values of chromosome i, respectively, T_max refers to the highest possible value in the population. Table 4 provides an overview of the population size as well as the GA operators.

TABLE 4

Table 4. The population size, and the GA operators.

The termination rule: After 10 iterations, there is no change in the population’s best objective value Tbest.

Step 2: Create the first population P⁽⁰⁾, set k = 0

The initial population comprises 10 chromosomes. There are 3 chromosomes generated from 3 heuristic rules, EDD, SPT, and LPT. The remaining chromosomes R1, …, R7 are randomly generated.

P {}^{(0)}= {EDD, SPT, LPT, R1, R2, R3, R4, R5, R6, R7}

The chromosomes in the initial population with their fitness values are shown in Table 5.

TABLE 5

Table 5. The initial population P⁽⁰⁾ with fitness values.

Step 3: Establish the elite population P_E^(k)

This stage involves selecting a subset of the population, P^(k), to form the elite population, P_E^(k). Based on its fitness value F_i, each member of the present population is given a certain chance of being included in the elite population P_E^(k), denoted by the selection probability P_i.

P_{i} = \frac{F_{i}}{\sum_{1}^{10} F_{i}}

The selection probabilities P_i and cumulative probabilities CP_i of chromosomes in the initial population are calculated and shown in Table 6.

TABLE 6

Table 6. The initial population P⁽⁰⁾ with selection and cumulative probabilities.

Based on CP_i, 10 random numbers RN are generated, the chromosomes selected into the population P_E⁽⁰⁾ are as in Table 7.

TABLE 7

Table 7. The chromosomes selected into elite population P_E⁽⁰⁾.

P {}_{E}^{(0)}= {R3, R2, LPT, SPT, EDD, SPT, SPT, EDD, R2, R5}

Step 4: Establish the genetic population P_G^(k)

The newly created chromosome is a part of the genetic population known as P_G^(k), which was produced by the crossover and mutation operators.

A crossover probability of 0.8 is applied when selecting the chromosomes of P_E⁽⁰⁾ to be included in the P_c list of potential crossover partners. After producing 10 random numbers RN, the set P_c is calculated, and the results are presented in Table 8.

TABLE 8

Table 8. The chromosomes selected into the crossover list P_c.

P {}_{c}= {R3, LPT, SPT, EDD, SPT, EDD}

By using the POX approach, we choose to cross over 6 pairs of chromosomes in population P_c, which results in the addition of 12 new chromosomes to population P^C, as shown in Table 9.

TABLE 9

Table 9. Population P^C.

With a mutation probability of 0.2, the chromosomes of P_E⁽⁰⁾ are as well chosen for inclusion in the mutation list P_m. Ten sets of random numbers (RN) are generated, and then P_m is calculated and displayed in Table 10.

TABLE 10

Table 10. The chromosomes selected into the mutation list P_m.

P {}_{m}= {EDD}

As can be seen in Table 11, the SWAP method is used to select for mutations in each chromosome in P_m, leading to the gain of 1 additional chromosome in population P^M.

TABLE 11

Table 11. Population P^M.

A total of 13 additional chromosomes are added into the population P_G⁽⁰⁾ as a result of crossover and mutation:

P_{G}^{(0)} = {C1, C2, C3, C4, C5, C6, C7, C8,

C9, C10, C11, C12, M1}

Step 5. Develop the next population P^{(k + 1)}

The next population, P^{(k + 1)}, is formulated with the help of the replacement operator at this stage. If chromosomes from P_G^(k) have fitness values higher than the threshold value, they will be included into the current population P^(k) in order to generate the following population P^{(k + 1)}. With K = 2:

n = \frac{P}{K} = \frac{10}{2} = 5

The threshold value is the value of the 5th chromosome of P^(k) in the ranking. For this iteration, the 5th chromosome of P⁽⁰⁾ in the ranking is R2, and the threshold value is 986.0005. Chromosomes C1, C2, C3, C4, C7, C8, and M1 are selected for inclusion to P⁽¹⁾.

In order to maintain the same total number of individuals in the P⁽¹⁾ population, the chromosomes M1, R7, R6, R5, R4, R3, R2, and R1 are eliminated. The next population, P⁽¹⁾, is calculated and displayed as in Table 12.

TABLE 12

Table 12. The next population P⁽¹⁾.

Step 6. Make sure the termination rule is followed

The best chromosome after the first iteration is C1, which has an objective value of 188.60 and appears only once in the population. Since the rule of termination has not been met, iteration 2 will be carried out. Table 13 displays the outcomes after 17 iterations.

TABLE 13

Table 13. The results after 17 iterations.

Seeing that from the 8th iteration to the 17th iteration, the best objective value remains the same, the termination rule is satisfied; hence, the algorithm ends. The scheduling result in this run is as follows:

S = (1, 3, 2, 4, 510, 8, 7, 9, 6), T = 123.07 (h) .

Step 7. 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 14.

TABLE 14

Table 14. The results after 10 runs.

The best scheduling result is found on the 1st run, with a number of iterations n of 17. The sequence of dispatching S, the values of the objective function are as follows:

S = (1, 3, 2, 4, 510, 8, 7, 9, 6),

T = 123.07 (h) .

The objective value by the GA model, 123.07 (h) is smaller than the objective value of EDD models, 215.95 (h).

5. Conclusion

With the goal of minimizing the total weighted tardiness time and constraint on changeover time in operations, the Flow Shop Scheduling Problem with 10 orders on 4 machines has been created. The Flow Shop Scheduling Problem has been successfully resolved with the help of the GA model. Compared to the heuristic EDD technique, the results reveal that the GA model provides a lower objective value of weighted tardiness time.

Nevertheless, given that the model’s factors, such as the population size, the crossover method and probability Pc, the mutation method and probability, as well as the method and parameter of the termination rule, are only determined empirically, the findings are not very impressive. In the upcoming study, the experimental design DOE will be utilized to identify the model parameters in order to produce more accurate results. Another area for research for the future is to apply the model to more extended order quantities.

Moreover, GA, a global search method, if combines with another local search method like Tabu search, the result would be better in terms of quality, better objective value, and cost, smaller number of iterations.

References

1. Phong N, Thu N. Application of GATS, a hybrid mega-heuristic model, and DOE, to solve flexible flow shop scheduling problems: a case study. BOHR Int J Operat Manag Res Pract. (2023) 2:28–35. doi: 10.54646/bijomrp.2023.14

CrossRef Full Text | Google Scholar

2. Phong N, Thuy N. Application of Tabu Search, TS to solve a flow shop scheduling problem with changeover times in operations. A case study. BOHR Int J Operat Manag Res Pract. (2024) 3:1–7. doi: 10.54646/bijomrp.2024.22

CrossRef Full Text | Google Scholar

3. Etiler O, Toklu B, Atak M, Wilson J. A genetic algorithm for flow shop scheduling problems. J Operat Res Soc. (2004) 55:830–5. doi: 10.1057/palgrave.jors.2601766

CrossRef Full Text | Google Scholar

4. Engin O, Ceran G, Yilmaz MK. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems. Appl Soft Comput. (2011) 11:3056–65. doi: 10.1016/j.asoc.2010.12.006

CrossRef Full Text | Google Scholar

5. Umam MS, Mustafid M, Suryono S. A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem. J King Saud Univ Comput Informat Sci. (2022) 34:7459–67. doi: 10.1016/j.jksuci.2021.08.025

CrossRef Full Text | Google Scholar

6. Burduk A, Musiał K, Kochańska J, Górnicka D, Stetsenko A. Tabu Search and genetic algorithm for production process scheduling problem. Sci J Logist. (2019) 5:181–9. doi: 10.17270/J.LOG.2019.315

CrossRef Full Text | Google Scholar

© The Author(s). 2024 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Application of genetic algorithm, GA, to solve a flow shop scheduling problem with changeover times in operations: a case study

1. Introduction

2. Literature review and research methodology

2.1. Flow shop scheduling FSS problems

2.2. Genetic algorithm

2.3. Research methodology

3. The model of the flow shop scheduling problem

4. The GA model for the flow shop scheduling problem

5. Conclusion

References