Bohr article

Introduction

Scheduling is the allocation of resources to perform a collection of tasks over a period of time. Scheduling problems determine the order or sequence for processing a set of jobs through several machines in an optimal manner. FSS problems consider m different machines and n jobs; each job consists of m operations and each operation requires a different machine and all the jobs are processed in the same processing order.

The problem to be solved is a FSS 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 weighted tardiness of orders. The constraints are on the sequence of orders, on the sequence of operations in the orders, and on machine changeover time.

The model of the problem is built based on the above assumptions, objectives, and constraints. A TS model is built. Based on the model of the problem, the TS model will find a good solution for the problem, which will be compared with the solution of the currently used heuristic model to evaluate the effectiveness of the TS model.

Literature review and research methodology

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 is categorized as an NP-hard problem, so it is difficult to develop algorithms to solve it (2). Jatinder N. D. Gupta, Nagarajan Palanim Uthu, and Chuen-Lung Chen designed a tabu search-based heuristic for the two-stage flow shop problem with the makespan minimization as the primary criterion and the minimization of total flow time as the secondary criterion (3). Moch Saiful Umam, Mustafid Mustafid, and Suryono Suryono combined the tabu search process with a genetic algorithm to solve flow shop scheduling problem with the objective of minimizing makespan (2). Anna Burduk, Kamil Musiał, Joanna Kochańska, Dagmara Górnicka, and Anastasia Stetsenko 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 (4).

Tabu search

According to Farhad Kolahan et al. (5), heuristic algorithms are widely used to solve very large and complicated optimization problems, in recent years, and Tabu Search (TS) is one of the most efficient neighborhood search algorithms.

Tabu search (TS), suggested by Glover and Laguna in 1997, is one of the most popular meta-heuristics to find solutions of various combinatorial optimization problems. TS guides a local search procedure to explore the solution space beyond local optimality.

In order to apply TS to a problem, generally the solution space of the problem is represented by a population of codes. An evaluation value is associated with each code. The evaluation function is a measure of the extent to which the objective of the problem is achieved. The Fbest value is the best evaluation value, found during the search.

TS allows intelligent problem solving by the incorporation of adaptive memory and responsive exploration. Key elements of the search path are selectively remembered and strategic choices are made to guide the search out of local optima and into diverse regions.

However, considering every possible move from the current solution may be extremely time consuming and computationally expensive. In order to avoid cycling and becoming trapped in local optima, certain moves that lead to previously explored regions are forbidden. Attributes of recently visited solutions are set to be tabu for a certain number of iterations, and these moves are stored in the tabu list. Elements of tabu list define all tabu moves that cannot be applied to the current solution. The size of tabu list is bounded by a parameter. The tabu status of a move may be canceled, making it an allowable move if an aspiration criterion is satisfied. A tabu move can always be allowed to be chosen if it creates a solution better than the incumbent best solution.

A typical TS implementation starts from an initial solution and moves from the current solution to the best one among its neighborhoods at each iteration, even if this new solution is worse than the one available, until a pre-specified termination rule becomes true.

Research methodology

FSS problem is a NP hard problem with a large size of solution space. The methodology, used in this research to solve the problem, includes 2 phases (1):

- Phase A: Construct the model of the problem.

- Phase B: Use TS 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.

Based on the model of the problem, a TS model is used to solve the problem in phase B. The TS procedure (1) is as follows:

Step 1: Initialize the TS model.

Step 2: Generate the initial solution S₀. Set k = 0.

Step 3: Generate the neighborhood population P_N(k).

Step 4: Find the next solution S_k+1. Set k = k + 1,

Step 5: Check the termination rule. If No, return to step 3. If Yes, finish the loop.

Step 1 initializes the TS model by setting up the structure and parameters of the TS model, including the method of coding, the TS factors, and the termination rule.

For coding, the orders are numbered from 1 to n (n is the total number of orders), each code is a string of n numbers. Each number corresponds to an order. The sequence of numbers Gi, i = 1÷n, represents the sequence of orders scheduled.

C = [G 1, G 2, \dots, G n]

The TS factors include the evaluation function, the current best value, the TS operators, and the tabu list. The evaluation function is defined according to the objective function of the problem, is used to evaluate scheduling codes. The current best value Tbest is the best objective value, updated after each iteration.

The TS operators include the neighborhood and search operators. Tabu list is defined by tabu members and tabu list size. Tabu members are moves in the previous loops. Tabu list size is a parameter of the algorithm. Tabu list is updated after each iteration.

The termination rule in this research: The best objective value Tbest does not improve after a specific number of consecutive iterations.

Step 2 generates the initial solution S0. A good initial solution will be a good starting point for the search. The initial solution is often chosen by heuristic methods, SPT, LPT, EDD. In this research, the initial solution is generated by the best heuristic method that gives the best objective value. This steps also starts the algorithm by setting the iteration counting index k to 0.

Step 3 uses neighborhood operator to generate the neighborhood population P_N(k) from the current string S_k. This research uses SWAP as the neighborhood operator. SWAP uses the method of permutation of adjacent numbers in the string to find the neighborhood. For a string with n numbers, SWAP will generate n-1 neighboring strings.

Step 4 finds the next solution S_k+1 from the neighborhood population P_N(k) by using the search operator. The search operator relies on the objective function and the tabu list to find the best solution in the neighborhood region, the chosen solution must not violate the tabu list. This solution will be selected for the next iteration, if any. This step also updates the tabu list and the current best Tbest if the objective value of the solution is better than the current Tbest. This step also increases the iteration counting index k by 1 to prepare for the next iteration, if any.

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

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

The model flow shop scheduling problem

The problem to be solved is a FSS problem (1) with 10 orders, O_i, i = 1÷10, scheduling on 4 machines, M₁, M₂, M₃, M₄. Each order has 3 parts, P1, P2, P3, processed in 8 operations, O_j, j = 1÷8, distributed on the 4 machines as in Figure 1.

FIGURE 1

Figure 1. 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 time 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 set up with variables TS_ij being the start time, TE_ij being the completion time of order i at operation j, and T_i being the tardiness time of order i. The constraints on the sequence of operation on each order are as follows.

\begin{array}{l} {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}) . \end{array}

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}_{i j} = {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}_{i j} = {TS}_{ij} + P_{i j}

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 tardiness is defined as follows.

Tbest = Min T, T = Σ (W_{i} * T_{i}, i = i \div 11)

The company is currently using the EDD dispatching method. The sequence of dispatching S and the value of the objective function 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 2.

FIGURE 2

Figure 2. The Gantt Chart by EDD dispatching method.

The TS model for the flow shop scheduling problem

The above FSS problem is a NP hard problem with the size of the solution space of 10! or 3,628,800. The above TS model is used to solve the problem with following steps.

Step 1: Initialize the TS model

This step sets up the method of coding, the TS factors, and the termination rule.

The method of coding: The orders are numbered from 1 to 10. Each code is a string of 10 numbers. Each number corresponds to an order. The sequence of numbers G_i, i = 1÷10 represents the sequence of order scheduled. For example, the string of EDD scheduling method is as follows.

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

The TS factors include the evaluation function, the current best value, the parameters of the TS operators, and the Tabu List as shown in Table 4.

TABLE 4

Table 4. The TS factors.

The termination rule: The best objective value Tbest does not improve after 10 consecutive iterations.

Step 2: Generate the initial solution S₀, set k = 0

A good initial solution will be a good starting point for the search. With the objective of minimizing tardiness time, the initial solution is selected from the EDD method. The strings and its corresponding objective values are as follows.

S {}_{0}= (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

T = 215.95 (h)

The initial tabu list TL and the current best value are as follows.

TL = \emptyset

Tbest = 215.95 (h)

From the initial solution S₀, iteration 1 is executed with steps 3, 4, and 5.

Iteration 1

Step 3: Generate the neighborhood population P_N⁽⁰⁾

This step uses the neighborhood operator SWAP to generate the neighborhood population P_N⁽⁰⁾ from the current string S₀.

P {}_{N}^{(}^{0}^{)}= {N1, N2, N3, N4, N5, N6, N7, N8, N9}

The strings in neighborhood population P_N⁽⁰⁾ and their objective values are shown in Table 5.

TABLE 5

Table 5. The neighborhood population P_N⁽⁰⁾.

Step 4. Find the next solution S₁

This step uses the search operator to find the next solution S₁ that is the best solution in the neighborhood population P_N⁽⁰⁾, and does not violate the current tabu list. The strings in the neighborhood population P_N^(0), and their corresponding tabu members TM are shown in Table 6.

TABLE 6

Table 6. Find the next solution S_1.

From Table 6, the best string in the neighboring population P_N⁽⁰⁾ without violating tabu list and its objective value are as follows.

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

T = 175.65 (h)

This string is selected as the next solution for the next iteration, if any.

S {}_{1}= (1, 2, 3, 4, 5, 6, 7, 8, 10, 9)

The tabu list and the current best Tbest are updated as follows.

TL = {(9, 10)}

Tbest = 175.65 (h) .

Step 5. Check the termination rule

After iteration 1, S₁ is the best string with the best objective value of 175.65, appearing only once. The termination rule is not satisfied, so iteration 2 is executed.

Iteration 2

Step 3: Generate the neighborhood population P_N⁽¹⁾

This step uses the neighborhood operator SWAP to generate the neighborhood population P_N⁽¹⁾ from the current string S₁.

P {}_{N}^{(}^{1}^{)}= {N1, N2, N3, N4, N5, N6, N7, N8, N9}

The strings in neighborhood population P_N⁽¹⁾ and their objective values are shown in Table 7.

TABLE 7

Table 7. The neighborhood population P_N⁽¹⁾.

Step 4. Find the next solution S₂

This step uses the search operator to find the next solution S₂ that is the best solution in the neighborhood population P_N⁽¹⁾, and does not violate the current tabu list. The strings in the neighborhood population P_N^(1), and their corresponding tabu members TM are shown in Table 8.

TABLE 8

Table 8. Find the next solution S_2.

From Table 8, string N9 in P_N⁽¹⁾ violates tabu list. The best string in the neighboring population P_N⁽¹⁾ without violating tabu list and its objective value are as follows.

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

T = 135.60 (h)

This string is selected as the next solution for the next iteration, if any.

S_{2} = N4 = (1, 2, 3, 5, 4, 6, 7, 8, 10, 9)

The tabu list is updated as follows.

TL = {(9, 10), (4, 5)}

The objective value of the best string in this iteration is 135.60, smaller than the current best value, so Tbest is updated as follows.

Tbest = 135.60 (h)

Step 5. Check the termination rule

After iteration 2, S₂ is the best string with the best objective value of 135.60, appearing only once. The termination rule is not satisfied, so iteration 3 is executed.

Iteration 3

Step 3: Generate the neighborhood population P_N⁽²⁾

This step uses the neighborhood operator SWAP to generate the neighborhood population P_N⁽²⁾ from the current string S₂.

P {}_{N}^{(}^{2}^{)}= {N1, N2, N3, N4, N5, N6, N7, N8, N9}

The strings in neighborhood population P_N⁽²⁾ and their objective values are shown in Table 9.

TABLE 9

Table 9. The neighborhood population P_N⁽¹⁾.

Step 4. Find the next solution S₃

This step uses the search operator to find the next solution S₃ that is the best solution in the neighborhood population P_N⁽²⁾, and does not violate the current tabu list. The strings in the neighborhood population P_N^(2), and their corresponding tabu member are shown in Table 10.

TABLE 10

Table 10. Find the next solution S_3.

From Table 10, strings N4, and N9 in P_N⁽²⁾ violate the tabu list. The best string in the neighboring population P_N⁽²⁾ without violating the tabu list and its objective value are as follows.

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

T = 149.12 (h)

This string is selected as the next solution for the next iteration, if any.

S_{3} = N7 = (1, 2, 3, 5, 4, 6, 8, 7, 10, 9)

The tabu list is updated as follows.

TL = {(9, 10), (4, 5), (7, 8)}

The objective value of the best string in this iteration is 149.12 bigger than the current best value 135.60, then Tbest remains the same.

Tbest = 135.60 (h) .

Step 5. Check the termination rule

After iteration 3, S₃ is the best string in P_N⁽²⁾ with the objective value of 149.12, but S₂ is still the best string with the best objective value of 135.60, appearing only twice. The termination rule is not satisfied, so iteration 4 is executed.

The result after 27 iterations is as in Table 11.

TABLE 11

Table 11. The result after 27 iterations.

The best objective value Tbest remains the same from the 17th iteration to the 27th iteration, the termination rule is satisfied, the algorithm ends. The best scheduling string and its objective value are as follows.

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

T = 123.07 (h)

The objective value according to TS model (123.07 h) is better than the objective value according to the EDD heuristic currently used (215.95 h).

Conclusion

The Flow Shop Scheduling Problem with 10 orders on 4 machines has been formulated with the objective of minimizing the total weighted tardiness time and constraint on changeover time in operations. The TS model has been developed and used to solve the problem. The results show that the TS model is better than the heuristic EDD method being used. The objective value has reduced by 43% from 215.95 (h) to 123.07 (h).

However, the factors of the model, including the method for defining the initial solution, factors of neighborhood operator, search operator, tabu list size, the method and parameter of the termination rule, are only selected empirically, so the results are not very good. Future research is to use experimental design DOE to determine the model factors to get better results. Further research is to use the model for larger numbers of orders.

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

Author contributions

Both authors have made a substantial, direct, and intellectual contribution to the work, and approved it for publication.

References

1. Nhu PN, Nhi T, Thi N. Application of TSGA, a hybrid mega heuristic model, to solve flow shop scheduling problems with changeover times in operations. A case study. Proceeding of the 4 th International Conference on Advanced Convergence Engineering (ICACE 2023) August 14th – 16th, 2023, Ho Chi Minh City University of Technology, VNUHCM, Ho Chi Minh City: (2023).

Google Scholar

2. 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 Comp Inf Sci. (2022) 34:7459–67.

Google Scholar

3. Gupta JND. Designing a tabu search algorithm for the two-stage flow shop problem with secondary criterion. Prod Plann Cont Manage Oper. (1999) 10:251–65. doi: 10.1080/095372899233217

CrossRef Full Text | Google Scholar

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

CrossRef Full Text | Google Scholar

5. Kolahan F, Tavakoli A, Tajdin B, Hosayni M. Analysis of neighborhood generation and move selection strategies on the performance of Tabu Search. Proceedings of the 6th WSEAS International Conference on Applied Computer Science, Tenerife, Canary Islands, Spain, December 16-18, Tenerife (2006). p. 503–7.

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 tabu search, TS, to solve a flow shop scheduling problem with changeover times in operations: A case study

Introduction

Literature review and research methodology

Flow shop scheduling FSS problems

Tabu search

Research methodology

The model flow shop scheduling problem

The TS model for the flow shop scheduling problem

Conclusion

Author contributions

References