Sage Journals: Discover world-class research

Abstract

This article proposes a novel fuzzy model for solving fuzzy multi-objective permutation flow shop scheduling problem with fuzzy processing time. Specifically, two fuzzy objectives, that is, the fuzzy makespan and the fuzzy total flow time, are taken into account in this model simultaneously. In addition, to solve fuzzy multi-objective permutation flow shop scheduling problem, an efficient algorithm called fuzzy multi-objective local search-based decomposition is proposed. In order to generate a high quality and diverse set of initial solutions, a problem-specific Nawaz–Enscore–Ham heuristic approach is incorporated into the framework as an initialization. Then, two perturbation strategies with different strength are adopted to find better solutions and to avoid local optimum as well. Besides, a ranking concept based on fuzzy number centroid is provided to compare with fuzzy solutions. After that, a restart strategy is employed to change the searching space when the best solution has not been improved for a certain number of iterations. Finally, we conduct an extensive computational study on Taillard benchmarks to compare the proposed fuzzy multi-objective local search-based decomposition with the fuzzy NSGAII. Experimental results demonstrate that the fuzzy multi-objective local search-based decomposition algorithm is both effective and efficient in solving the fuzzy multi-objective permutation flow shop scheduling problem.

Keywords

Fuzzy permutation flow shop scheduling fuzzy total flow time fuzzy makespan decomposition-based fuzzy multi-objective local search

Introduction

In recent years, scheduling problems have played an important role in both manufacturing system and traffic arrangement. Among them, the permutation flow shop scheduling problem (PFSSP) has received growing attentions for its fundamentally theoretical value, and the widespread applications in production and living of our daily life.^1–4 As for the objectives of PFSSP, a variety of criterions have been presented according to different considerations, such as performance-oriented optimizations¹ (makespan, flow time, tardiness, earliness, idle time, etc.), energy-related optimizations⁵ (energy consumption, peak power load), and environment-aware optimizations⁶ (carbon footprint reduction). Since most real-world scheduling problems are naturally formulated as multi-objective problems, it is of great significance to settle the multi-objective permutation flow shop scheduling problem (MOPFSSP) within a reasonable time. Also note that the classical MOPFSSP cannot model some practical conditions owing to the fact that they are incapable of depicting the uncertain processing time. Thus, we focus on modeling and solving the MOPFSSP with fuzzy processing time in this article, which makes the model more suitable for real scenarios.

As is known to all, numerous of researchers have proposed exact methods, heuristic and metaheuristics for solving MOPFSSP.^7–19 Recently, the multi-objective local search algorithm based on decomposition (MOLSD)²⁰ was proved to be an efficient one for solving such a problem. After that, a novel general multi-objective decomposition-based estimation of distribution algorithm using Kernels of Mallows models was introduced by Zangari et al.²¹ In 2018, Ruiz et al.²² first used a metaphor-inspired method called iterated greedy algorithm to gain better results. We can see that the researches on MOPFSSP are sustained, illustrating the importance of this problem.

When considering the model of MOPFSSP in a real scenario, it is easy to find that the concepts of imprecision and fuzziness exist in real manufacturing system due to the uncertain processing time. Thus, the certain model is inappropriate to represent such problems. For instance, the certain progress time in a real factory could hardly be obtained if it has multiple functions. In this situation, it is reasonable to use fuzziness concept such as the fuzzy process time to depict the model.²³ Fortunately, a lot of achievements have been provided^24–38 for solving the fuzzy multi-objective permutation flow shop scheduling problem (FMOPFSSP). Over the past few years, an increasing number of researchers focused on the FMOPFSSP. Javadi et al.³⁹ proposed a fuzzy multi-objective linear programming model to solve the multi-objective flow shop scheduling problem with no-wait constraints in a fuzzy environment. In this article, the author attempts to minimize two objectives simultaneously, that is, the weighted mean completion time and weighted mean earliness. Wu⁴⁰ paid attention to the fuzzy flow shop scheduling problem in which the processing time and due date are uncertain. Nakhaeinejad and Nahavandi⁴¹ proposed an interactive method for solving the multi-objective fuzzy flow shop scheduling problem with the aim to minimize makespan, mean flow time, and machine idle time simultaneously. Later, Behnamian and Fatemi Ghomi⁴² performed a bi-level algorithm, including random key genetic algorithm and particle swarm optimization algorithm, for the bi-objective hybrid flow shop scheduling problems with fuzzy processing time, sequence-dependent setup times, and due dates.

Different from those papers mentioned above, in this article, a novel fuzzy model of the FMOPFSSP with two fuzzy objectives, that is, the fuzzy makespan and the fuzzy total flow time, is proposed. As is known to all, fuzzy makespan and fuzzy total flow time are classical conflicting objectives as traditional FMOPFSSP suggests. Therefore, we cannot optimize them simultaneously. For solving the FMOPFSSP, an efficient algorithm called fuzzy multi-objective local search-based decomposition (FMOLSD) is proposed. In the algorithm, at first a problem-specific Nawaz–Enscore-Ham (NEH) heuristic approach is incorporated into the search framework to improve some individuals. Then, two perturbation strategies are adopted to find better solutions and to avoid local optimum as well. Besides, to compare with fuzzy solutions, a ranking concept based on fuzzy number centroid is provided. After that, a restart strategy is employed to change the search space when the best solution is not improved after a certain search number of iterations. Finally, the influence of some parameters of this algorithm is investigated by some numerical experiment results, and the comparisons on some benchmark instances are proposed with FNSGAII which can be viewed as a fuzzy version of NSGAII. The results demonstrate that the FMOLSD algorithm is effective and efficient in FMOPFSSP.

The rest of this article is organized as follows. Some concepts of fuzzy number and multi-objective optimization problems are given in the “FMOPFSSPs” section. In the “FMOLSD Algorithm” section, the details of the algorithm FMOLSD would be described. In the “Computational Experiments and Results” section, the results of the computational experiments are displayed. At last, a conclusion will be given in the “Conclusion and Future Work” section.

FMOPFSSPs

In this section, some concepts and operators of fuzzy numbers will be introduced, together with the definition of the FMOPFSSP. To make the definition easily understood, a simple yet intuitional example will be given as well.

Operations on fuzzy numbers

In fuzzy context, fuzzy numbers can describe the extent to which people feel shocked when an event happened. The larger a fuzzy number is, the less extent to which people are shocked. On the contrary, a small fuzzy number indicates that people feel much shocked by the event that is happening. Thus, it is appropriate to represent an uncertain problem with fuzzy numbers. First, the definition of the fuzzy set is given as follows.⁴³

Definition 1

If a function denotes $U_{\tilde{A}}$ , which maps a real number set X to [0, 1] for each element denoted as x in X, then $\tilde{A}$ is said as a fuzzy set of X.

In Definition 1, $U_{\tilde{A}}$ is named as “membership function.” It can map each element in X into [0, 1]. The number mapped into [0, 1] is the “grade of membership” of x in X under the function $U_{\tilde{A}}$ . A fuzzy set is a fuzzy number if it meets the conditions as follows:

There exists a number x in real set R, that makes $U_{\tilde{A}} (x) = 1$ for $x \in R$ ;

$x, x_{1}, x_{2} \in R$ , and $U_{\tilde{A}} (x) = 1$

if $x_{1} < x_{2} < x$ , then $U_{\tilde{A}} (x_{1}) \leq U_{\tilde{A}} (x_{2}) \leq U_{\tilde{A}} (x)$ ;

if $x_{1} \geq x_{2} \geq x$ then $U_{\tilde{A}} (x_{1}) \geq U_{\tilde{A}} (x_{2}) \geq U_{\tilde{A}} (x)$ ;

If $x_{1} < x < x_{2}$ , then $U_{\tilde{A}} (x) \geq \min {U_{\tilde{A}} (x_{1}), U_{\tilde{A}} (x_{2})}$ .

After introducing the definition of fuzzy number, the form of fuzzy number used in this article will be presented next.

The fuzzy number has various forms such as triangular fuzzy number and trapezoidal fuzzy number. To understand the fuzzy number form, the triangular fuzzy number and the trapezoidal fuzzy number are displayed in Figure 1. A triangular fuzzy number is denoted as $f (a, b, d), 0 \leq a \leq b \leq d$ and a trapezoidal fuzzy number is denoted as $f (a, b, c, d), 0 \leq a \leq b \leq c \leq d$ . Comparing to the two forms of the fuzzy number, it is easy to find that a triangular fuzzy number is a special case of a trapezoid fuzzy number if b and c are equal in the trapezoidal fuzzy number. Thus, the trapezoidal form is chosen in this article without loss of generality.

Figure 1.

A triangular and trapezoidal fuzzy number.

In addition, several operators of the fuzzy number is adopted in this article, named the addition operation, the max/min operation. An operator “⊕” in this article is similar to the addition operation in Hu et al.⁴⁴ Two fuzzy numbers are denoted as $f (a_{1}, b_{1}, c_{1}, d_{1})$ and $f (a_{2}, b_{2}, c_{2}, d_{2})$ , respectively, and the fuzzy addition is shown by the following formula

\begin{matrix} f (a_{1}, b_{1}, c_{1}, d_{1}) \oplus f (a_{2}, b_{2}, c_{2}, d_{2}) \\ = f (a_{1} + a_{2}, b_{1} + b_{2}, c_{1} + c_{2}, d_{1} + d_{2}) \end{matrix}

(1)

Due to the definition, equation (1) can maintain the fuzzy number property.⁴⁴ In order to compare two fuzzy numbers, two operators are adopted in this article, defined as $fuzzyMax (f (a_{1}, b_{1}, c_{1}, d_{1}) f (a_{2}, b_{2}, c_{2}, d_{2}))$ , which takes the larger fuzzy number between the two ones. We propose the function, which is defined as $fuzzyMin (f (a_{1}, b_{1}, c_{1}, d_{1}) f (a_{2}, b_{2}, c_{2}, d_{2})$ , to fetch the smaller fuzzy number between the two ones.

Ranking fuzzy numbers have been wildly concerned due to the difficulty of comparing two fuzzy numbers. Recently, there have been lots of academic papers focusing on this problem. Among them, a useful and easy approach based on the centroid of fuzzy number is adopted to compare two fuzzy numbers.⁴⁵

In Wang et al.,⁴⁵ the formula of calculating the centroid of a trapezoidal fuzzy number is denoted as follows

x (\tilde{A}) = \frac{1}{3} [a + b + c + d - \frac{d * c - a * b}{(d + c) - (a + b)}]

(2)

y (\tilde{A}) = \frac{1}{3} [1 + \frac{c - b}{(d + c) - (a + b)}]

(3)

where $\tilde{A (} a, b, c, d)$ is a trapezoidal fuzzy number, $x (\tilde{A})$ is the horizontal coordinate, and $y (\tilde{A})$ is the vertical coordinate.

The FMOPFSSP with fuzzy processing time

An optimization problem with multi-objectives can be described as follows

\begin{matrix} Min (Max) F (x) = (f_{1} (x), f_{2} (x), \dots, f_{k} (x)) \\ subject to x \in Ω \end{matrix}

(4)

where $Ω$ is the variable space, F is a map function from $Ω$ to $R^{k}$ , and k objectives are represented by $f_{1} (x), f_{2} (x), \dots, f_{k} (x)$ , respectively.

Based on these, the FMOPFSSP can be stated as follows: there are n jobs and a set of m machines. Each job will be processed on each machine. The uncertain processing time of the job i on the machine j is denoted by $t_{i, j}$ . A feasible job scheduling sequence is denoted as $P = (P_{1}, P_{2}, \dots, P_{n})$ . $C (P_{i}, j)$ is the completion time of $P_{i}$ on machine j. The computational formulas are described as follows

C (P_{1}, 1) = t_{p 1_{1}}

(5)

C (P_{i}, 1) = C (P_{i - 1}, 1) \oplus t_{p_{i}, 1} i = 2, 3 \dots, n

(6)

C (P_{1}, j) = C (P_{1}, j - 1) \oplus t_{p_{1, j}}, j = 2, 3, \dots, m

(7)

\begin{matrix} C (P_{i}, j) = fuzzyMAX (C (P_{i - 1}, j), C (P_{i}, j - 1)) \\ + t_{p_{i}, j}, i = 2, 3, \dots, n and j = 2, 3, \dots, n \end{matrix}

(8)

Then the two objectives, that is, fuzzy makespan and fuzzy total flow time, can be defined as

\min C_{MAX} (P) = C (P_{n}, m)

(9)

min TFT (P) = \sum_{i = 1}^{n} C (P_{i}, m)

(10)

Now take the FMOPFSSP with two jobs and two machines as an example. The description is below in order to make the mechanism clear:

Job 1: machine 1 (3, 4, 5, 7), machine 2 (2, 4, 7, 10),

Job 2: machine 1 (2, 4, 6, 9), machine 2 (6, 7, 9, 11).

All the processing time in this example is trapezoidal fuzzy number. If the job scheduling is {job 1, job 2}, the start time of job 1 on machine 1 is (0, 0, 0, 0). The start time plus the processing time of job 1 on machine 1, which is (0, 0, 0, 0) ⊕ (3, 4, 5, 7), is (3, 4, 5, 7). It is the finish time of job 1 on machine 1. As no setup time constraints are required, so (3, 4, 5, 7) is the start time of job 1 on machine 2. Therefore, the finish time of job 1 on machine 2 is (3, 4, 5, 7) ⊕ (2, 4, 7, 10) which equals (5, 8, 12, 17). The start time of job 2 on machine 1 must be executed after the finish time of job 1 on machine 1. So the result is (5, 8, 11, 16). As formula (8) says, the start time is the larger one between (5, 8, 12, 17) and (5, 8, 11, 16). According to formula (2), the horizontal coordinate of the centroid of (5, 8, 12, 17) is 10.58. The horizontal coordinate of the centroid of (5, 8, 11, 16) is 10.09. Therefore, the start time of job 2 on machine 2 is (5, 8, 12, 17) because it is larger. Afterward, the finish time of job 2 on machine 2 is (5, 8, 12, 17) ⊕ (6, 7, 9, 11) = (11, 15, 21, 28). Finally, we get the results: the makespan equals (11, 15, 21, 28) and the total flow time is (16, 23, 33, 45).

FMOLSD algorithm

Decomposition technique

The decomposition technique in this article refers to multi-objective evolutionary algorithm based on decomposition,⁴⁶ which has been proved efficient in solving multi-objective scheduling problems. To deal with fuzzy problems, some operators are adopted in the decomposition technique. First, the weighted sum approach makes the multi-objective problem into a single objective problem. In addition, the weighted vectors are denoted as $λ = (λ_{1}, λ_{2}, \dots, λ_{N})$ , and the objective vectors are defined as $f_{1} (x), f_{2} (x), \dots, f_{k} (x)$ . Furthermore, the ideal point is denoted as $z^{*} = (z_{1}^{*}, z_{2}^{*}, \dots, z_{k}^{*})$ . After that, the sub-problem with the vector $λ$ is

\begin{matrix} \min g (x | λ) = \sum_{i = 1}^{k} λ_{i} \frac{f_{i} (x)}{z_{i}^{*}} \\ subject to x \in Ω \end{matrix}

(11)

where $\sum_{i = 1}^{k} λ_{i} = 1$ and $λ_{i} \geq 0$ for all $i = 1, 2, \dots, k$ , $z_{i}^{*} = fuzzyMin (f_{i} (x))$ is the reference vector, in which for i = 1, . . ., k, each $λ$ in equation (11) has a pareto optimal to equation (4).

Main algorithm framework

The FMOLSD framework is given in Algorithm 1, called FMOLSD.

Algorithm 1: FMOLSD
k: the number of fuzzy objectives. n:the number of jobs to be scheduled x:represent a solution N: the population size n_ls: the max number of further local search $p_{L}$ : the current population $p_{E}$ :the external population $p_{p}$ :used in FuzzyParetoLoaclSearch 1. Initialize Population and weight vectors 2. Improve some individuals by NEH heuristic. 3. Let $P_{E}$ be the non-dominated solutions found in $P_{L}$ 4. While the stopping criterion is not met do 5. $P_{p} = P_{E}$ ; 6. FuzzyParetoLoaclSearch(); 7. Find Elitist Individuals; 8. For each individual x in $P_{L}$ do 9. Select a position r randomly; 10. x’ = LocalSearch_insert(x,r); 11. If g(x’)<g(x) then 12. x = x’; isReplacement=true; 13. else 14. if isElitist then 15. W = 0; 16. While w < n_ls do 17. Select a position r randomly; 18. x’ = LocalSearch_insert(x,r); 19. If g(x’)<g(x) then 20. x = x’; 21. endif 22. w++; 23. end while 24. endif 25. End if 26. If isReplacement = false than 27. If isElitist then 28. x’=heavy_perturbation (x); 29. Else 30. x’=light_ perturbation (x); 31. Endif 32. Noimproved++; 33. else 34. NoImproved = 0; 35. endif 36. If NoImproved > RestartIterationNum then 37. Restart(); 38. Endif 39. UpdatePL( $P_{L}$ ,x); 40. UpdatePE( $P_{E}$ ,x); 41. End for 42. End for

Algorithm 1: FMOLSD

k: the number of fuzzy objectives.
n:the number of jobs to be scheduled
x:represent a solution
N: the population size
n_ls: the max number of further local search

p_{L}

: the current population

p_{E}

:the external population

p_{p}

:used in FuzzyParetoLoaclSearch
1. Initialize Population and weight vectors
2. Improve some individuals by NEH heuristic.
3. Let

P_{E}

be the non-dominated solutions found in

P_{L}

4. While the stopping criterion is not met do
5.

P_{p} = P_{E}

;
6. FuzzyParetoLoaclSearch();
7. Find Elitist Individuals;
8. For each individual x in

P_{L}

do
9. Select a position r randomly;
10. x’ = LocalSearch_insert(x,r);
11. If g(x’)<g(x) then
12. x = x’; isReplacement=true;
13. else
14. if isElitist then
15. W = 0;
16. While w < n_ls do
17. Select a position r randomly;
18. x’ = LocalSearch_insert(x,r);
19. If g(x’)<g(x) then
20. x = x’;
21. endif
22. w++;
23. end while
24. endif
25. End if
26. If isReplacement = false than
27. If isElitist then
28. x’=heavy_perturbation (x);
29. Else
30. x’=light_ perturbation (x);
31. Endif
32. Noimproved++;
33. else
34. NoImproved = 0;
35. endif
36. If NoImproved > RestartIterationNum then
37. Restart();
38. Endif
39. UpdatePL(

P_{L}

,x);
40. UpdatePE(

P_{E}

,x);
41. End for
42. End for

In line 1, the population is initialized where each individual is a feasible solution and each individual has a weight vector. The weight vectors transforms the multi-objective optimization problem to a single objective optimization problem.

In line 2, the NEH heuristic approach²⁰ is employed to make more outstanding individual. It is not used for each individual because the quality and diversity of the population should be maintained.

In lines 5–7, the set $p_{p}$ is used to store some information. Then, the function of FuzzyParetoLoaclSearch() in Algorithm 2 is applied to each individual in $P_{E}$ so as to exploit some neighborhoods of the current solution for a better improvement. At last, the elite set is found.

Algorithm 2: FuzzyParetoLocalSearch(FPLS)
MP: the rate of perturbation n: the number of jobs 1. i=0,j=0; 2. While i<PLS_MAX do 3. For each individual x in $P_{p}$ do 4. While j<MPn do 5. x’* = heavy_perturbation(x); 6. Update( $P_{L}$ ,x’); 7. If g(x’) < g(x) then 8. x=x’; Update( $P_{E}$ , $P_{P}$ ); 9. End if 10. j++; 11. End while 12. End for 13. $P_{p}$ = $P_{E}$ ; i++; 14. End while

Lines 8–41 describes the main work of FMOSLD. In line 10, the LocalSearch_insert is a function to get the best new individual among all the neighborhoods when a randomly selected job r is moved to the far left position. The neighborhood structure of one individual is defined as exchanging two adjacent jobs on it. From lines 11 to 25, if the new individual is not better than the old one, a further local search will be performed to get a better individual. In lines 26–35, if the new individual is better, we seek for higher quality solutions based on it. To be specific, the new individual will be operated by two levels of perturbations. If the individual is in $P_{E}$ , a heavy perturbation is applied. Otherwise, a light perturbation is adopted. It is easy to understand that the individuals in $P_{L}$ can hardly find better results in a small range. However, a better individual will be missed if a heavy perturbation operation acts on a normal individual. Therefore, in line 37, the restart operation is taken that a new individual will be reformed by the heavy perturbation on an individual which is randomly selected from $P_{E}$ . In lines 39 and 40, x is added to $P_{L}$ and $P_{E}$ , respectively, according to the non-dominating relationship. At last, the pareto front is recorded in the elite population $P_{E}$ .

In heavy perturbation process, two random segments of individuals are chosen and swapped to get a new individual. The function of heavy_perturbation is shown in Algorithm 3. When talking to the light perturbation, a random job is chosen and then inserted into another random position. The function of light_perturbation is given in Algorithm 4.

Algorithm 3: heavy_perturbation
Input: Individual x Output: new individual x’ 1. Randomly select three positions $P_{1}, P_{2}, P_{3}$ make sure $P_{1} < P_{2} < P_{3}$ ; 2. Segment A is all jobs between $P_{1}$ and $P_{2}$ 3. Segment B is all jobs between $P_{2} + 1$ and $P_{3}$ 4. Swap A and B to reform a new individual 5. Compute Objective Value; 6. Return new individual

Algorithm 4: light_ perturbation
Input: Individual x Output: new individual x’ 1. Randomly select two positions $P_{1}, P_{2}$ , make sure $P_{1} < P_{2}$ 2. Insert the job in the position $P_{1}$ to the position $P_{2}$ ; 3. Compute Objective Value; 4. Return new individual;

Computational experiments and results

In this section, the parameter tuning and the efficiency verification experiments are conducted on a well-known data set. Then, detailed experimental results and discussion will be given.

Data set and performance evaluation

As shown in Table 1, the data set used in this article is obtained from Taillard,⁴⁷ which is generally employed in MOPFSSP. It has 90 instances with different sizes so that a full test on the performance of one algorithm can be achieved. However, the original data set does not consider the characteristics of fuzzy processing time. Therefore, they are modified by changing the exact time to fuzzy time randomly in a small range. Due to the characteristic of fuzzy processing time, the execution time should not be exact. Moreover, the randomization of instances is the most popular way to verify the performance and robustness of newly proposed algorithms.

Table 1.

The detail of data set.

	Number of job	Number of machine
fuzzyTa001-fuzzyTa010	20	5
fuzzyTa011-fuzzyTa020	20	10
fuzzyTa021-fuzzyTa030	20	20
fuzzyTa031-fuzzyTa040	50	5
fuzzyTa041-fuzzyTa050	50	10
fuzzyTa051-fuzzyTa060	50	20
fuzzyTa061-fuzzyTa070	100	5
fuzzyTa071-fuzzyTa080	100	10
fuzzyTa081-fuzzyTa090	100	20

Two commonly used indicators, named Hypervolume indicator and set coverage (C-metric) indicator,²⁰ are adopted in this article to measure the distribution and quality of the pareto set.

Hypervolume Indicator (I_H): This metric calculates the hypervolume in the objective space that is dominated by at least one solution of the non-dominated set. It should be noted that all the objective values need to be normalized into [0, 1] so that each objective has a similar impact on I_H.

Set Coverage (C(X, Y)): Suppose X and Y are two pareto fronts of a problem, then C(X, Y) is defined as the percentage of the solutions in Y that are dominated by at least one solution in X as follows

C (X, Y) = \frac{| {y \in Y | \exists x \in X : x dominates y} |}{| Y |}

(12)

Experimental environment and parameter settings

All programs are coded in C++, and the running environment is a PC with an Intel 3.30 GHz CPU, 4GB RAM. The limit time of running is 1000 s. The parameters are stable in the whole process once it is deterministic. The population size N is set to 75 and the maximum number of local search n_ls is 250 according to the experiments. Other parameters are chosen as the same as Li and Li²⁰ does. The weight vector set is $λ = {λ_{1}, λ_{2}, \dots, λ_{N}}$ and $λ_{i}$ is the weight vector of the $i th$ individual, denoted as $λ_{i} = (λ_{i}^{1}, λ_{i}^{2}) = (\frac{i - 1}{N - 1}, \frac{N - i}{N - 1}), i = 1, 2, \dots, N$ .

To determine the most appropriate population size, N is set as 50, 75, 100, and 150, respectively. In order to avoid the over-fitting phenomenon, only fuzzyTa051 to fuzzyTa060 are used as the test instances. The results are displayed in Table 2. It shows that when N = 75, the best average hypervolume value can be obtained. When the population size is too large, the convergence of the population needs more time, while a smaller population size will bring deficient searching on the whole space. Therefore, setting N to 75 is the best choice for FMOLSD in a certain running time.

Table 2.

Hypervolume values of FMOLSD with different N.

Hypervolume	50	75	100	150
1	0.2552	0.2304	0.2263	0.2372
2	0.7243	0.7083	0.6835	0.6483
3	0.8940	0.8880	0.8488	0.8760
4	0.5935	0.6322	0.5935	0.6324
5	0.8095	0.8452	0.7759	0.8070
6	0.6360	0.5830	0.6080	0.6329
7	0.4697	0.4641	0.4395	0.4173
8	0.5224	0.5869	0.5388	0.5295
9	0.4942	0.5259	0.4993	0.4994
10	0.3837	0.3968	0.3892	0.3608
Average	0.5783	0.5861	0.5603	0.5641

FMOLSD: fuzzy multi-objective local search-based decomposition.

Note: Bold value shows best result.

Another important parameter is n_ls. The larger n_ls is the better results it can produce. But a large value of n_ls often needs more computational time. So we test n_ls as 50, 100, 150, 200, 250, respectively. Table 3 shows the consequence that FMOLSD gets the best result when n_ls is set 250. Note that there is no need to examine larger n_ls because of the time limit of the whole framework.

Table 3.

Hypervolume values of FMOLSD with different n_ls.

Hypervolume	50	100	150	200	250
1	0.1561	0.2014	0.2123	0.2169	0.2205
2	0.6473	0.6289	0.6790	0.6819	0.6976
3	0.8450	0.9111	0.9413	0.9647	0.9778
4	0.5486	0.5497	0.5666	0.6231	0.6313
5	0.7601	0.8226	0.8405	0.8530	0.8747
6	0.5669	0.5847	0.6052	0.6178	0.6227
7	0.3788	0.4232	0.4374	0.4425	0.4524
8	0.4938	0.4934	0.5166	0.5444	0.5539
9	0.4464	0.4534	0.4753	0.4953	0.5204
10	0.3264	0.3571	0.3802	0.3873	0.3963
Average	0.5169	0.5425	0.5654	0.5827	0.5948

FMOLSD: fuzzy multi-objective local search-based decomposition.

Comparison results

This subsection will demonstrate the comparison experiments between FNSGAII and the proposed FMOLSD. FNSGAII is short for Fuzzy NSGAII, which is slightly modified for fuzzy problems.⁴⁸ In this way, we can compare our proposed algorithm with the classical NSGAII fairly. In Figure 2, it is clearly seen that the FMOLSD shows dominating superiorities to FNSGAII on the quality of solutions. FMOLSD generates the pareto front in the range of (525,000, 555,000) for total flow time, and (6725, 6900) for makespan on fuzzyTa090, while FNSGAII only attains solutions within the scope of (1,660,000, 1,670,000) and (25,150, 25,375). As for the other benchmark fuzzyTa010, the two objectives of FMOLSD are ranging between (13,200, 14,300) and (1140, 1210), while they are (49,000, 52,100) and (4200, 4425) for FNSGAII. Therefore, FMOLSD dominates FNSGAII on all instances. The values of C-metric of each data set also inflect the same conclusion as Figure 2 does, which are outlined in Table 4.

Figure 2.

Distribution of result on fuzzyTa010 and fuzzyTa090 by FMOLSD and FNSGAII.

Table 4.

Coverage values between FMOLSD and FNSGAII.

Data set name	C(FMOLSD, FNSGAII)	C(FNSGAII, FMOLSD)
fuzzyTa001-fuzzyTa010	1	0
fuzzyTa011-fuzzyTa020	1	0
fuzzyTa021-fuzzyTa030	1	0
fuzzyTa031-fuzzyTa040	1	0
fuzzyTa041-fuzzyTa050	1	0
fuzzyTa051-fuzzyTa060	1	0
fuzzyTa061-fuzzyTa070	1	0
fuzzyTa071-fuzzyTa080	1	0
fuzzyTa081-fuzzyTa090	1	0

FMOLSD: fuzzy multi-objective local search-based decomposition.

In summary, all of the results mentioned above show that our algorithm is able to produce more widely distributed solutions as well as higher quality of the pareto set than FNSGAII.

Conclusion and future work

In this article, a novel fuzzy model of FMOPFSSP is addressed with two fuzzy objectives, that is, fuzzy total flow shop time and fuzzy makespan. To solve this problem, a new framework FMOLSD is developed using three efficient strategies, that is, the insert-based local search, two-level perturbation methods, and the restart technique. Comparative experiments are carried out on well-known benchmark instances against the FNSGAII, to verify the performance of FMOLSD. The results in the experiment have pointed out that FMOLSD gains a significant edge in terms of the approximation and distribution of the pareto front.

As for future work, one concern is to solve large-scale FMOLSD problems, where more efficient methods should be designed. For example, reduction rules, sampling techniques, or effective heuristics. Another interesting topic may be the practical extension of FMOLSD, such as fuzzy hybrid flow shop scheduling problems and fuzzy blocking flow shop scheduling problems.

Footnotes

Handling Editor: Wanli Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Xin Xu

References

Yenisey

Yagmahan

Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends. Omega 2014; 45: 119–135.

Wang

Fang

et al . A Pareto-archived estimation of distribution algorithm for multiobjective resource-constrained project scheduling problem. IEEE Trans Eng Manage 2013; 60: 617–626.

Bezerra

LCT

López-Ibáñez

Stützle

. Deconstructing multi-objective evolutionary algorithms: an iterative analysis on the permutation flow-shop problem. In: Learning and intelligent optimization, Gainesville, FL, 16–21 February 2014. New York: Springer.

Leisten

Rajendran

Variability of completion time differences in permutation flow shop scheduling. Comput Oper Res 2015; 54: 155–167.

Gao

et al . Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm. J Clean Prod 2017; 144: 228–238.

Fang

Uhan

Zhao

et al . A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. J Manuf Syst 2011; 30: 234–240.

Rajendran

Heuristics for scheduling in flowshop with multiple objectives. Eur J Oper Res 1995; 83: 540–555.

Cavalieri

Gaiardelli

Hybrid genetic algorithms for a multiple objective scheduling problem. J Intell Manuf 1998; 9: 361–367.

Neppalli

Chen

C-L

Gupta

JND

. Genetic algorithms for the two-stage bicriteria flowshop problem. Eur J Oper Res 1996; 95: 353–373.

10.

Gupta

JND

Hennig

Werner

Local search heuristics for two-stage flow shop problems with secondary criterion. Comput Oper Res 2002; 29: 123–149.

11.

Ishibuchi

Yoshida

Murata

Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 2003; 7: 204–223.

12.

Chang

Hsieh

Lin

SG.

The development of gradual priority weighting approach for the multi-objective flowshop scheduling problem. Int J Prod Eco 2002; 79: 171–183.

13.

Chang

Chen

Liu

CH.

Sub-population genetic algorithm with mining gene structures for multiobjective flowshop scheduling problems. Expert Syst Appl 2007; 33: 762–771.

14.

Wang

A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling. IEEE Trans Syst Man Cybern B 2007; 37: 576–591.

15.

Tamura

A new multiobjective genetic algorithm with heterogeneous population for solving flowshop scheduling problems. Int J Comput Integr Manuf 2007; 20: 465–477.

16.

Sha

Lin

HH.

A particle swarm optimization for multi-objective flowshop scheduling. Int J Adv Manuf Technol 2009; 45: 749–758.

17.

Minella

Ruiz

Ciavotta

A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS J Comput 2008; 20: 451–471.

18.

Chiang

Cheng

LC.

NNMA: an effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems. Expert Syst Appl 2011; 38: 5986–5999.

19.

Ciavotta

Minella

Ruiz

Multi-objective sequence dependent setup times permutation flowshop: a new algorithm and a comprehensive study. Eur J Oper Res 2013; 227: 301–313.

20.

Multiobjective local search algorithm-based decomposition for multiobjective permutation flow shop scheduling problem. IEEE Trans Eng Manage 2015; 62: 1–14.

21.

Zangari

Mendiburu

Santana

et al . Multiobjective decomposition-based Mallows Models estimation of distribution algorithm. A case of study for permutation flowshop scheduling problem. Inform Sci 2017; 397: 137–154.

22.

Ruiz

Pan

Naderi

Iterated Greedy methods for the distributed permutation flowshop scheduling problem. Omega 2018; 83: 213–222.

23.

Slowinski

Hapke

Scheduling under fuzziness. Heidelberg: Physica Verlag, 2000.

24.

Mccahon

Lee

ES.

Job sequencing with fuzzy processing times. Comput Math Appl 1990; 19: 31–41.

25.

Mccahon

Lee

ES.

Fuzzy job sequencing for a flow shop. Eur J Oper Res 1992; 62: 294–301.

26.

Ishibuchi

Murata

Flowshop scheduling with fuzzy duedate and fuzzy processing time. In: Slowinski

Hapke

(eds) Scheduling under fuzziness. Heidelberg: Physica Verlag, 2000, pp.113–143.

27.

Cheng

Kise

Matsumoto

A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem. Eur J Oper Res 1997; 96: 578–590.

28.

Murata

Gen

Ishibuchi

Multi-objective scheduling with fuzzy due-date. Comput Ind Eng 1998; 35: 439–442.

29.

Okabe

Maeda

Murakami

. On the fuzzy scheduling for flow shop jobs by using genetic algorithm. In: International conference on systems, man, and cybernetics, Tokyo, Japan, 12–15 October 1999, vol. 4, pp.528–539. New York: IEEE.

30.

Yao

Lin

FT.

Constructing a fuzzy flow-shop sequencing model based on statistical data. Int J Approx Reason 2002; 29: 215–234.

31.

Temİz

Erol

. Fuzzy branch-and-bound algorithm for flow shop scheduling. J Intell Manuf 2004; 15: 449–454.

32.

. A hybrid algorithm for scheduling problems of flow shop with uncertain processing time. In: Proceedings of the 6th world congress on intelligent control and automation (WCICA), Dalian, China, 21–23 June 2006, pp.3466–3470. New York: IEEE.

33.

Petrovic

Song

. A new approach to two-machine flow shop problem with uncertain processing time. In: International symposium on uncertainty modeling and analysis, College Park, MD, 21–24 September 2003, pp.110–115. New York: IEEE.

34.

Lai

Shu

. Tardiness in fuzzy flow shop scheduling problems based on possibility and necessity measures. In: Proceedings of the 8th international conference on intelligent systems design and applications (ISDA), Kaohsiung, Taiwan, 26–28 November 2008, vol. 3, pp.437–441. New York: IEEE.

35.

Bozejko

Hejducki

Wodecki

. Fuzzy blocks in genetic algorithm for the flow shop problem. In: Conference on human system interactions, Krakow, 25–27 May 2008, pp.820–824. New York: IEEE.

36.

Nezhad

Assadi

RG.

Preference ratio-based maximum operator approximation and its application in fuzzy flow shop scheduling. Appl Soft Comput 2008; 8: 759–766.

37.

Zhou

. Research on no-wait flow shop scheduling problem with fuzzy due date based on evolution games. In: International conference on computer science and information technology, Beijing, China, 8–11 August 2009, pp.495–499. New York: IEEE.

38.

Gupta

Sharma

Aggarwal

Flow shop scheduling on 2-machines with setup time and single transport facility under fuzzy environment. Opsearch 2013; 50: 14–24.

39.

Javadi

Saidi-Mehrabad

Haji

et al . No-wait flow shop scheduling using fuzzy multi-objective linear programming. J Franklin Inst 2008; 345: 452–467.

40.

HC.

Solving the fuzzy earliness and tardiness in scheduling problems by using genetic algorithms. Expert Syst Appl 2010; 37: 4860–4866.

41.

Nakhaeinejad

Nahavandi

An interactive algorithm for multi-objective flow shop scheduling with fuzzy processing time through resolution method and TOPSIS. Int J Adv Manuf Technol 2013; 66: 1047–1064.

42.

Behnamian

Ghomi

SMTF

. Multi-objective fuzzy multiprocessor flowshop scheduling. Appl Soft Comp 2014; 21: 139–148.

43.

Zadeh

LA.

Fuzzy sets. Inform Contr 1965; 8: 338–353.

44.

Yin

A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date using differential evolution algorithm. Int J Adv Manuf Technol 2011; 56: 1125–1138.

45.

Wang

Yang

et al . On the centroids of fuzzy numbers. Fuzzy Sets Syst 2006; 157: 919–926.

46.

Zhang

MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 2007; 11: 712–731.

47.

Taillard

Benchmarks for basic scheduling problems. Eur J Oper Res 1993; 64: 278–285.

48.

Palacios

González-Rodríguez

Vela

et al . Robust multiobjective optimisation for fuzzy job shop problems. Appl Soft Comput 2017; 56: 604–616.

A novel fuzzy model for multi-objective permutation flow shop scheduling problem with fuzzy processing time

Abstract

Keywords

Introduction

FMOPFSSPs

Operations on fuzzy numbers

Definition 1

The FMOPFSSP with fuzzy processing time

FMOLSD algorithm

Decomposition technique

Main algorithm framework

Computational experiments and results

Data set and performance evaluation

Experimental environment and parameter settings

Comparison results

Conclusion and future work

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References