Multi-objective re-entrant hybrid flow shop scheduling problem considering fuzzy processing time and delivery time

Abstract

Although re-entrant hybrid flow shop scheduling is widely used in industry, its processing and delivery times are typically determined using precise values that frequently ignore the influence of machine failure, human factors, the surrounding environment, and other uncertain factors, resulting in a significant gap between theoretical research and practical application. For fuzzy re-entrant hybrid flow shop scheduling problem (FRHFSP), an integrated scheduling model is established to minimize the maximum completion time and maximize the average agreement index. According to the characteristics of the problem, a hybrid NSGA-II (HNSGA-II) algorithm is designed. Firstly, a two-layer encoding strategy based on operation and machine is designed; Then, a hybrid population initialization method is designed to improve the quality of the initial population; At the same time, crossover and mutation operators and five neighborhood search operators are designed to enhance the global and local search ability of the algorithm; Finally, a large number of simulation experiments verify the effectiveness and superiority of the algorithm.

Keywords

Re-entrant hybrid flow shop multi objective optimization fuzzy scheduling average agreement index

1 Introduction

The re-entrant hybrid flow shop scheduling problem (RHFSP) combines the characteristics of re-entrant scheduling and hybrid flow shop scheduling. It has been widely applied in industrial fields, such as thin-film transistor liquid crystal display and semiconductor wafer manufacturing. However, in prior studies, the processing time and delivery time were regarded to be accurate values. In reality, it is difficult to get a precise time because of the effect of different elements such as equipment, personnel, and the environment. As a result, it is more practical to regard processing and delivery times as fuzzy values. This kind of issue is referred to as the fuzzy re-entrant hybrid flow shop scheduling problem (FRHFSP). Due to its large scale and high complexity, RHFSP are difficult to solve effectively in an acceptable time using traditional mathematical modeling methods. In addition, according to the “No Free Lunch” theorem [1], no algorithm can achieve better results for all application problems, so it is important to design and develop new intelligent optimization algorithms to solve it.

With the ongoing growth and refinement of fuzzy theory, many researchers have been interested in the use of fuzzy numbers to define and solve uncertain job shop scheduling optimization problems. Lei [2] developed a genetic algorithm based on co-evolution to handle the fuzzy flexible flow shop scheduling problem (FFJSP). To solve the FFJSP, Gao et al. [3] suggested a discrete harmony search algorithm. Wang et al. [4] suggested an enhanced distributed estimating algorithm in which they incorporated a left shift approach to the decoding to fully use the machine’s idle waiting time. Huang et al. [5] initialized the operations sequence using six heuristic rules and developed an improved discrete particle swarm optimization algorithm to solve FFJSP. Wang et al. [6] introduced a hybrid artificial bee colony algorithm for FFJSP, which uses a range of ways to establish the population and increases the algorithm’s local search capabilities via variable neighborhood search. Gao et al. [7] developed an enhanced artificial bee colony algorithm for solving FFJSP, aiming at minimizing the maximum fuzzy completion time and total machine load. Arik et al. [8] investigated a kind of multi-objective parallel machines scheduling problem with fuzzy learning effect, fuzzy deterioration effect and fuzzy processing time. Cai et al. [9] studied the fuzzy distributed two-stage hybrid flow shop scheduling problem considering sequence-dependent setup times, and took the total agreement index and fuzzy makespan as the optimization objectives. Gao et al. [10] suggested a differential evolution algorithm enhanced by a selection mechanism for the job shop scheduling problem with the fuzzy processing time. Engin et al. [11] prosed an genetic algorithm to solve the hybrid flow shop scheduling problem (HFSP) with fuzzy processing time and a fuzzy due date. Focus on the cellular manufacturing system considering automated guided vehicles under fuzzy processing time, a hybrid genetic algorithm and a whale optimization algorithm are developed [12].

To summarize, research on scheduling problems with fuzzy processing time and delivery time is still in its early stages, while research on FRHFSP is even more limited. Recent study indicates that the hybrid algorithm can complement the qualities of two or more algorithms and is more adaptable and robust than a single algorithm. It is an important direction for researching and solving FRHFSP. The local search algorithm based on NSGA-II is described in this research, and a hybrid NSGA-II is developed to solve the issue with the optimization objectives of minimizing the fuzzy completion time and maximizing the average agreement index.

The rest of the paper is structured as follows: Section 2 describes the FRHFSP in depth and establishes the mathematical model. The suggested HNSGA-II algorithm is discussed in depth in Section 3. Section 4 depicts the experimental simulation and outcome analysis. Section 5 includes a conclusion and a prospect.

2 Problem statement and mathematical model

2.1 Problem statement

In FRHFSP, some jobs need to go to some stages several times, and the processing time of each operation and the delivery time of each job are fuzzy numbers. The diagram of RHFSP is shown in Fig. 1. The main objective of this paper is to assign jobs to machines, determine the set of operations on each machine, calculate the fuzzy start and end time of each operation, and optimized the solution with the objective of minimizing the maximum completion time $\tilde{C_{max}}$ and maximizing the average agreement index AI_avg.

Fig. 1

Re-entrant hybrid flow shop scheduling.

In the study, the fuzzy processing time of operation O_jk is represented by the triangular fuzzy number $\tilde{P_{jk}} = (P_{jk}^{1}, P_{jk}^{2}, P_{jk}^{3})$ , where $P_{jk}^{1}$ and $P_{jk}^{3}$ are the lowest and upper limits of the processing time, $P_{jk}^{2}$ is the most likely processing time, and the fuzzy membership function is illustrated in Fig. 2(a). The fuzzy delivery time $\tilde{d_{j}} = (d_{j}^{1}, d_{j}^{2})$ of jobj is a trapezoidal fuzzy number, and Fig. 2(b) depicts the fuzzy membership function.

Fig. 2

Fuzzy processing time and delivery time.

The larger-taking operation is used to calculate the fuzzy start time of each operation in fuzzy scheduling, the addition operation is used to calculate the fuzzy completion time of jobs, and the comparison operation is primarily used to measure the relationship among the solutions. Assuming two fuzzy numbers $\tilde{s} = (s_{1}, s_{2}, s_{3})$ and $\tilde{t} = (t_{1}, t_{2}, t_{3})$ , the three operations are defined as follows.

Addition operation: $\tilde{s} + \tilde{t} = (s_{1} + t_{1}, s_{2} + t_{2}, s_{3} + t_{3}) .$

Comparison operation:

(1) if $\tilde{r_{1} (s)} = (s_{1} + 2 s_{2} + s_{3}) / 4 >$

$\tilde{r_{1} (t)} = (t_{1} + 2 t_{2} + t_{3}) / 4$ , then $\tilde{s} > \tilde{t}$ , otherwise, $\tilde{s} < \tilde{t}$ .

(2) if $\tilde{r_{1} (s)} = r_{1} (\tilde{t})$ , when $\tilde{r_{2} (s)} = s_{2} > r_{2} (\tilde{t}) = t_{2}$ , then $\tilde{s} > \tilde{t}$ , otherwise, $\tilde{s} < \tilde{t}$ .

(3) if $\tilde{r_{2} (s)} = r_{2} (\tilde{t})$ , when $\tilde{r_{3} (s)} = s_{3} - s_{1} > r_{3} (\tilde{t}) = t_{3} - t_{1}$ , then $\tilde{s} > \tilde{t}$ ,otherwise, $\tilde{s} < \tilde{t}$ .

Larger-taking operation:

if $\tilde{s} > \tilde{t}$ , then $\tilde{s} \lor \tilde{t} = \tilde{s}$ ; if $\tilde{s} < \tilde{t}$ , then $\tilde{s} \lor \tilde{t} = \tilde{t}$ .

2.2 Mathematical model

The mathematical symbols in the model and their meanings are as follows:

n: total number of jobs;

j, j′: serial number of jobs, j, j′ = 1, 2, . . . , n;

s: total number of stages;

i: serial number of stages, i = 1, 2, . . . , s;

m_i: number of parallel machines at stage i;

l : serial number of machines at stage i, l = 1, 2, . . . , m_i;

q: number of machines based on all machines;

N_j: total number of processes of job j;

k: serial number of operations of job j, k = 1, 2, . . . , N_j;

O_jk: the k - th operation of job j;

$\tilde{C_{jk}}$ : the completion time of operation O_jk;

$\tilde{P_{jk}}$ : the fuzzy processing time of operation O_jk;

M: a positive number large enough;

U_i: the set of operations at stage i;

$\tilde{S_{jk}}$ : the fuzzy start time of operation O_jk;

$\tilde{E_{jk}}$ : the fuzzy completion time of operation O_jk;

$\tilde{C_{j}}$ : the fuzzy completion time of job j;

$\tilde{d_{j}}$ : the fuzzy delivery time of job j;

M_il: the l - th machine at stage i;

AI_j: the agreement index of job j;

r_ijkl: 1, if the operation O_jkis processed by the l-th machine at the stage i, and 0 otherwise

Z_jkj′k′: 1, if the operation O_jk is processed before O_j′k′, and 0 otherwise

Based on the existing literature [13, 14], a mathematical model for bi-objective FRHFSP is presented. To solve the FRHFSP, each operation must be performed on an appropriate machine under fuzzy circumstances, and in a sensible order. An essential index in the scheduling problem is the maximum completion time. Improving this index may assist enhance production efficiency. The fuzzy completion time of each job is equal to the last operation’s fuzzy completion time, and the maximum value is $\tilde{C_{\max}}$ , as shown in Formula (1). $minimize f_{1} = \tilde{C_{\max}} = \max \tilde{C_{j}}$ (1)

The second optimization objective is to maximize the average agreement index AI_i. For convenience, we simplify it by converting it to a minimal issue, as illustrated in Formula (2) $minimize f_{2} = - {AI}_{avg} = - \frac{1}{n} (\sum_{j = 1}^{n} {AI}_{j})$ (2)

The agreement index AI_i is the ratio of the graph area $area (\tilde{C_{j}} \cap \tilde{d_{j}})$ enclosed by the intersection of the fuzzy completion time membership function and fuzzy delivery time membership function to the area $area (\tilde{C_{j}})$ formed by the fuzzy completion time membership function, as shown in Fig. 3 and Formula (3).

Fig. 3

Agreement index of job j.

${AI}_{j} = area (\tilde{C_{j}} \cap \tilde{d_{j}}) / area (\tilde{C_{j}})$ (3)

The constraints of the objective functions are: $\sum_{l = 1}^{m_{i}} r_{ijkl} (\tilde{S_{jk}} + \tilde{P_{jk}}) ⩽ \sum_{l = 1}^{m_{i^{'}}} r_{i^{'} jk + 1 l} \tilde{S_{jk + 1)}} \forall i, i^{'}, j, k$ $\sum_{l = 1}^{m_{i}} r_{ijkl} = 1 \forall i, j, O_{jk} \in U_{i}$ (4)

$\begin{matrix} M (2 - r_{ijkl} - r_{{ij}^{'} k^{'} l}) + M (1 - Z_{{jkj}^{'} k^{'}}) + \tilde{S_{j^{'} k^{'}}} \\ ⩾ \tilde{P_{jk}} + \tilde{S_{jk}} \forall i, j < j^{'}, l, O_{jk} \in U_{i}, O_{j^{'} k^{'}} \in U_{i} \end{matrix}$ (5) $M (2 - r_{ijkl} - r_{{ij}^{'} k^{'} l}) + {MZ}_{{jkj}^{'} k^{'}} + \tilde{S_{jk}} ⩾ \tilde{P_{j^{'} k^{'}}} + \tilde{S_{j^{'} k^{'}}}$ $\forall i, j < j^{'}, l, O_{jk} \in U_{i}, O_{j^{'} k^{'}} \in U_{i}$ (6) $M (2 - r_{ijkl} - r_{{ijk}^{'} l}) + \tilde{S_{{jk}^{'}}} ⩾ \tilde{P_{jk}} + \tilde{S_{jk}}$ $\forall i, k < k^{'}, l, O_{jk} \in U_{i}, O_{{jk}^{'}} \in U_{i}$ (7) $\tilde{E_{jk}} = \tilde{S_{jk}} + \tilde{P_{jk}}, \tilde{S_{jk}} ⩾ (0 00) \forall j, k$ (8) $\tilde{C_{j}} = \sum_{i = 1}^{s} \sum_{l = 1}^{m_{i}} r_{{ijN}_{j} l} (\tilde{S_{{jN}_{j}}} + \tilde{P_{{jN}_{j}}}) \forall j$ (9) $\tilde{C_{j}} ⩽ \tilde{C_{\max}} \forall_{j}$ (10) $0 ⩽ {AI}_{j} ⩽ 1 \forall j$ (11)

In which, Formulas (1) and (2) denote the two objective functions; Constraint (4) assures that the start of operation O_jk+1 does not occur before the completion of operation O_jk; Constraint (5) ensures that each operation can only be processed by one machine on the corresponding statge; Constraints (6), (7), and (8) guarantee that each machine performs no more than one operation concurrently; Constraint (9) establishes the start and end times of operation O_jk; the maximum completion time is described by Constraints (10) and (11); Constraint (12) restricts the value range of each job’s agreement index.

In bi-objective optimization, solution X₁ dominates X₂(denotes as X₁ ≺ X₂), if and only if ∀i ∈ {1, 2} , f_i (X₁) ⩽ f_i (X₂) ∧ ∃ i ∈ {1, 2} , f_i (X₁) < f_i (X₂). A solution X is the non-dominant solution when there is no solution that can dominate it.

3 The HNSGA-II for the FRHFSP

The NSGA-II [15] is a well-known multi-objective evolutionary algorithm that has been extensively used in engineering domains, such as route planning [16, 17], site selection [18, 19], scheduling [20, 21], and parameter optimization [22].

The study proposes a hybrid algorithm (HNSGA-II) based on NSGA-II. To enhance the algorithm’s performance, a double-layer coding method based on operation and machine, a hybrid population initialization method based on greedy machine selection and complete random methods, crossover and mutation operators, and five neighborhood search operators are designed. Finally, the simulation experiment verifies the superiority of HNSGA-II in solving FRHFSP. The flowchart of HNSGA-II algorithm is shown in Fig. 4.

Fig.4

Flowchart of the improved HNSGA-II.

3.1 Encoding and decoding

Since FRHFSP mainly consists of two subproblems, machine assignment and process ordering, this paper adopts a two-layer encoding method based on machines and operations to maximize the search of the algorithm in the entire solution space. The individual’s length is equal to the total of all jobs’ operations. The OS part indicates the sequence of all operations, in which the number represents the job index, and the number of occurrences represents the corresponding operation. The machines used in each operation are listed in the MS part, and the number in the MS component corresponds to the machine number. FRHFSP with three tasks and two stages (two parallel machines at each stage) is an example. Table 1 shows the fuzzy processing and delivery times for all operations.

Table 1
Example involving two stages and three jobs (hour)

Fuzzy processing First pass Re-entrant 1 Re-entrant 2 Fuzzy delivery

time ( $\tilde{P_{jk}}$ ) Stage 1 Stage 2 Stage 1 Stage 2 Stage 1 Stage 2 time ( $\tilde{d_{j}}$ )

Job 1 1, 2, 3 0.5, 1, 2 2, 3, 4 1, 2, 3 0, 0, 0 0, 0, 0 7.5, 8.6

Job 2 1, 2, 3 1, 2, 3 1, 2, 3 1, 2, 3 1, 2, 3 1, 2, 3 11.5, 13.2

Job 3 1, 2, 3 2, 3, 5 1, 2, 3 1, 2, 3 0, 0, 0 0, 0, 0 16, 18.4

Fuzzy processing	First pass	Re-entrant 1	Re-entrant 2	Fuzzy delivery
Job 1	1, 2, 3	0.5, 1, 2	2, 3, 4	1, 2, 3	0, 0, 0	0, 0, 0	7.5, 8.6
Job 2	1, 2, 3	1, 2, 3	1, 2, 3	1, 2, 3	1, 2, 3	1, 2, 3	11.5, 13.2
Job 3	1, 2, 3	2, 3, 5	1, 2, 3	1, 2, 3	0, 0, 0	0, 0, 0	16, 18.4

The processing time $\tilde{P_{jk}}$ =(0,0,0) indicates that the job of this pass is not processed at some stage. According to Table 1, all jobs are re-entrant twice. The two-layer coding process based on machine and operation is shown in Fig. 5, among them, the operation with processing time of (0,0,0) is not considered in the chromosome.

Fig.5

Two-layer encoding chromosome.

The primary goal of decoding is to establish the start and finish time of each operation. Detailed instructions for decoding are as follows.

Step 1: Select job j from OS and assume that the corresponding operation is O_jk.

Step 2: Find the machine q corresponding to operation O_jk from MS.

Step 3: Calculate the start time and completion time of operation O_jk according to Formulas (13) and (14).

$\tilde{S_{jk}} = \tilde{C} j (k - 1) \lor C_{q}$ (12)

$\tilde{C_{jk}} = \tilde{S_{jk}} + \tilde{P_{jk}}$ (13) where, C_q denotes the end time of the last operation on machine q in the present condition.

Step 4: Step 1- Step 3 should be repeated until all jobs in the OS have been traversed.

Step 5: Calculate the two objectives.

Taking the individual in Fig. 5 as an example, under various constraints, the Gantt chart of the scheduling scheme obtained after decoding is shown in Fig. 6, and the two objective functions are f₁=(7 12 18) hours and f₂=0.53, respectively. As an illustration, consider the individual shown in Fig. 5. As illustrated in Fig. 6, under different constraints, the Gantt chart of the scheduling scheme after decoding is shown. The two objective functions are f₁=(7 12 18) hours and f₂=0.53, respectively. As shown in Fig. 6, the operation with the processing time (0,0,0) is not displayed in the Gantt chart, and O31 denotes the first operation of the job 3 with non (0,0,0) processing time, and so on.

Fig. 6

Scheduling scheme of all jobs.

3.2 Population initialization

According to the two-layer coding strategy, the solution space is large enough, and using the completely random method to initialize the population will seriously affect the solution effect of HNSGA-II. Population initialization is a key part of the HNSGA-II algorithm. This work employs greedy machine selection and entirely random approaches to produce the initial population to increase the quality and variety of the initial population solution. In Algorithm 1, the pseudocode is presented.

The detailed process of the greedy machine selection strategy is as follows.

Step 1: Randomly generate the OS part. Select the z-th gene j from the OS and select a suitable machine from the available machines set randomly according to its corresponding operation, z = 1.

Step 2: Select the (z + 1)-th gene j′ from the OS and suppose the corresponding operation is O_j′k. Select the machine for the operation from the available machines set MS that can finish it earliest. The specific process is as follows.

Step 3: Select machine q from MS, get its fuzzy idle time periods $\tilde{MStart}, \tilde{MEnd}$ , then traverse them. Calculate the earliest fuzzy start time $\tilde{t_{i^{'} j}}$ of operation O_i′j according to Formula (15). $\tilde{t_{ij}} = \tilde{C_{i^{'} j - 1}} \lor \tilde{MStart}$ (14)

Step 4: Determine an appropriate insertion position for O_i′j in accordance with Formula (16). If no idle time period meets the requirement, set the start time of operation O_i′j as $\tilde{t_{i^{'} j}} = \tilde{{LM}_{q}}$ , where $\tilde{{LM}_{q}}$ is the completion time of the last operation of machine q. $\tilde{t_{i^{'} j}} + \tilde{P_{i^{'} j}} ⩽ \tilde{MEnd}$ (15)

Step 5: Traverse all of the machines in MS, then repeat Steps 3 - Step 4 to find the smallest $\tilde{t_{i^{'} j}}$ .

Step 6: Calculate the completion time of operation O_i′j, as shown in Formula (17).

Step 7: Step 2-Step 6 should be repeated until all of the jobs in the individual have been processed. $\tilde{C_{i^{'} j}} = \tilde{t_{i^{'} j}} + \tilde{P_{i^{'} j}}$ (16)

Step 8: Individual based on the two-layer encoding strategy is generated according to the above scheduling scheme.

Algorithm 1: Population_initialization()
Input: Population size N
Output: Initial population POP
1: for p = 1: N
2: ifrand1 < 0.5 % rand1 is a random variable between [0,1]
3: Greedy machine selection strategy.
4: else
5: Randomly generate the OS part and select a suitable
machine from the available machines set randomly
according to its corresponding operation.
6: end if
7: Adding p-th individual to the population POP.
8: end for
9: Obtain the initial population.

3.3 Crossover and mutation operators

According to the characteristics and various constraints of FRHFSP, not every operation can be processed by all machines. In addition, a significant number of infeasible solutions will be constructed if the jobs and the machines are crossed directly. To assure the feasibility of the solution, the JBX (job based crossover) crossover technique is used in both the OS and the MS parts of the solution. Firstly, the jobs are divided into two subsets set1 and set2 randomly, and the number of jobs in set2 is greater than 1. Then, the genes belonging to the jobs in set1 in parent PO1 and PO2 are copied into offspring O1 and O2 at the same position respectively. Finally, the genes belonging to the jobs in set2 in parent PO2 and PO1 were added to offspring O1 and O2 in the original order. The cross process of OS part is shown in Fig. 7, where set1 = [1] and set2 = [2, 3].

Fig.7

Crossover operator.

Mutation operation improves the diversity of the population by randomly changing some genes of the chromosome. To assure the solution’s feasibility after mutation, this research employs two-point exchange mutation. After the jobs in the OS part are exchanged, the MS part needs to be repaired. The schematic diagram of mutation operator is shown in Fig. 8, where r₁ = 2 and r₂ = 5.

Fig.8

Mutation operator.

Step 1: Select an individual from the population and mark two positions r₁ and r₂.

Step 2: Exchange the jobs at r₁ and r₂ positions in OS, and adjust the MS part.

Step 3: Repair the operations between r₁ and r₂, and randomly select an available machine for each operation.

Step 4: Get new individual X′.

3.4 Neighborhood search operator

As a result of randomness, it is difficult to assure that the quality of the population evolves in a positive direction when using crossover and mutation operators. In this paper, five kinds of neighborhood search operators are designed. Randomly select a neighborhood search operator and if the updated individual dominates the original individual, the original individual is replaced. The pseudo code is shown in Algorithm 2.

Algorithm 2: Neighborhoodsearch()
Input: Individual X
Output: Individual X after update
1: Rand←randperm(5,1) % Generate a number between [1,5, 1,5]
at random.
2: switch (Rand)
3: case 1: Execute Best_remove_ns(X), get new individual X
4: case 2: Execute Best_insert_ns(X), get new in dividual X
5: case 3: Execute Best_swap_ns(X), get new in dividual X
6: case 4: Execute Best_swap_amongs_machines_ns (X), get
new individual X
7: case 5: Execute Best_remove_based_makespan(X), get
new individual X
8: end switch

Best_remove_ns refers to moving a job on the machine with the largest load to other machines at the same stage. The following is a list of the steps involved.

Step 1: Randomly select an individual X, and find the machine M^maxload with the largest load according to the scheduling scheme generated by the decoding strategy.

Step 2: Randomly select a job j on the machine M^maxload.

Step 3: Insert job j tentatively into all possible insertion points on machine m_gk at the same stage to obtain a new individual X′, and calculate its objective function value.