Solving multi-objective fuzzy flexible job shop scheduling problem using MABC algorithm

Abstract

A new artificial bee colony algorithm called modified artificial bee colony algorithm (MABC) is presented to solve the multi-objective fuzzy flexible job-shop scheduling problem (MFFJSP) in this paper. The objectives of MFFJSP are to minimize the maximum fuzzy completion time (fuzzy makespan), maximize the weighted agreement index and minimize the maximum fuzzy machine workload. The three-point satisfaction-degree model is adopted to calculate the agreement index and this model can indicate the degree of satisfaction between the due date and the processing time. An effective local search operator based on variable neighborhood search (VNS) and crossover operator are embedded in this algorithm for obtaining good searching performance. In order to make the novel algorithm valid, we texted it, five benchmark instances and a practical case for the sake of effectiveness. Then, the performance of the proposed MABC has been compared with other existing algorithms to prove the superiority of this algorithm. In the end, the Taguchi method is used to investigate the impact of three key parameters from the MABC.

Keywords

Artificial bee colony algorithm agreement index variable neighborhood search multi-objective fuzzy flexible job-shop scheduling problem

1 Introduction

Recently, more and more researchers devoted to themselves to analyzing Job-shop scheduling problem (JSP). In JSP, n different jobs can be processed on m diverse machines and each job consists of several operations. The processing of each job has been pre-defined, all the operations have a fixed processing time and processing machine. In general, flexible job shop scheduling problem (FJSP) is an expansion of the JSP [1]. The difference of FJSP is that this problem allows operations for each job to be processed on a series of capable machines. And FJSP includes two sub-problems: (1) assign each operation of different jobs to available machines called routing sub-problem; (2) determine all the operations of each job called scheduling sub-problem. For the sake of optimizing the objectives of the manufacturing system, two sub-problems are applied for obtaining the feasible solution of FJSP [2]. Bruker and Schlie [3] first proposed a polynomial algorithm to analyze the FJSP. Along with the deepening study analysis, many intelligent algorithms such as genetic algorithms (GA) [4], particle swarm optimization (PSO) [5], tabu search (TS) [6] and artificial bee colony [7] have been applied to solve the FJSP.

Because the operation’s processing time is usually uncertain in the real manufacturing situation, the FJSP having fuzzy processing time (FFJSP) has attracted researchers’ attention greatly during the past few years. Lei [8, 9] proposed an efficient decomposition-integration genetic algorithm (DIGA) to solve FFJSP. An effective estimation of distribution algorithm (EDA) presented by Wang et al. [10], in this paper, a left-shift scheme was adopted to enhance the schedule when machines have idle time. Huang et al. [11] addressed the FFJSP by using an improved version of discrete particle swarm optimization (IDPSO). In the IDPSO, some useful discrete operators were embedded for updating particle’s position and obtaining new particles. To minimize fuzzy makespan, Lin [12] developed a hybrid biogeography-based optimization (HBBO), which introduced insertion-based local search heuristic to improve the mutation operator. In this algorithm, a new solution was generated by adopting the path relinking algorithm. Liu et al. [13] considered dynamic FJSP with fuzzy processing time (DfFJSP) for the sake of minimizing the fuzzy makespan. A fast estimation of distribution algorithm (fEDA) is presented to solve DfFJSP.

Recently, FFJSP has been developed many multi-objective scheduling problems to adapt to the manufacturing flexibility, lean production and so on. About multi-objective FFJSP (MFFJSP), Wang et al. [14, 15] proposed two multi-objective genetic algorithms (MOGAs) depended on immune and entropy principle to tackle MFFJSP. The objectives of this paper are to minimize the maximal completion time, maximize the average agreement index and maximize the minimal agreement index and they are all conflict with each typically. Zheng et al. [16] designed the multi-objective swarm-based neighborhood search (MOSNS) to settle the MFFJSP. According to MOSNS, the ordered operation-based doublet string and three-dimensional array were employed to represent the feasible solution. Wang et al. [17] presented an effective memetic algorithm (MA) to solve MFFJSP. In this paper, a four machines assignment method and four operations sequencing were introduced to improve the algorithm performance.

The Artificial bee colony (ABC) algorithm was presented by Karaboga [18 –20] to analyze multidimensional and multi-modal optimization problems, which describes the behavior of honeybee swarm intelligence. ABC algorithm is developed later than other meta-heuristic algorithms and has the capability of parallel execution. Moreover, ABC is a generalized neighborhood search algorithm which has local search ability and global search capability. Since the advantages of ABC to settle continuous optimization problems, some improved ABC have been developed to apply to the FFJSP. Wang et al. [21] proposed the hybrid artificial bee colony algorithm (HABC), which contained local search based on the variable neighborhood search (VNS) and left-shift decoding method. To minimize the maximum machine workload and the makespan, Gao et al. [22] proposed an artificial bee colony (IABC) algorithm. In IABC, a concise and effective heuristic method was developed to initialize the population.

Existing ABC algorithms for FFJSP do not solve the objective of weighted agreement index, but it is an important factor for scheduling problem. Moreover, it is necessary to improve the efficiency of ABC algorithm and find a better method of discretization. Building on the successful application of ABC for solving FFJSP, we propose a modified artificial bee colony (MABC) algorithm to settle this problem. The objectives being optimized are minimizing the maximum fuzzy makespan, maximizing the weighted agreement index and minimizing the maximum fuzzy machine workload. For the sake of describing agreement index in detail and reduce the computing complexity, we introduce the three-point satisfaction-degree model to calculate the agreement index. The basic ABC is easy to trap in local optimal solution. In order to improve searching capability of the MABC, a local search operator based on VNS and crossover operator are embedded in this algorithm. Moreover, we propose some efficient initializing methods about fuzzy processing time. According to some numerical testing results and comparisons, we can fully demonstrate the effectiveness and efficiency of the presented MABC. The effect of parameter setting was investigated based on the DOE.

This paper is organized as below. In Section 2, the model description for the MFFJSP is proposed. And in Section 3, the basic ABC algorithm is described. The MABC to solve the MFFJSP is proposed in Section 4. In Section 5, we introduce and analyze a practical MFFJSP and several computational experiments on five benchmark instances and the parameter sensitivity analysis is also investigated. In the end, the conclusions are given in the final section.

2 Multi-objective fuzzy flexible job-shop scheduling problem

2.1 Problem description

The Fuzzy Flexible Job-shop Scheduling Problem (FFJSP) is described as follows. It involves n different jobs and m different machines. M indicates a set of machines that can process operations. One job consists of n_i operations and one operation O_i,j (i = 1, 2, …, n ; j = 1, 2, …, n_i) is to be processed one machine M_k (M_k ∈ M_i,j), selected from the machines set M_i,j (M_i,j ⊆ M). The processing time of operation O_i,j on machine M_k is denoted by triangular fuzzy number (TFN) $t_{i, j, k} = (t_{i, j, k}^{1}, t_{i, j, k}^{2}, t_{i, j, k}^{3})$ , with $t_{i, j, k}^{1}$ and $t_{i, j, k}^{3}$ are the minimum and maximum processing time, $t_{i, j, k}^{2}$ as the most probable processing time. Likewise, the fuzzy completion time of O_i,j is denoted by a TFN $C_{i, j} = (C_{i, j}^{1}, C_{i, j}^{2}, C_{i, j}^{3})$ , with $C_{i, j}^{1}$ and $C_{i, j}^{2}$ as the minimum and maximum makespan, $C_{i, j}^{2}$ as the most probable makespan.

2.1.1 Problem assumptions

The problem based on assumptions as follows:

One operation is to be processed on one machine;

Operations shall not interrupted once started;

Transfer time between machines including the processing time, and the buffer shall be infinite;

Machines and jobs to be used are independent from each other and available at initial time.

2.1.2 Notations

i: the index of jobs, i = 1, 2, …, n;

j: the index of operation sequence, j = 1, 2, …, n_i;

m: the number of machines;

k: the index of machines, k = 1, 2, …, m;

n: the number of jobs;

n_i: the number of operation of job i;

O_i,j: the jth operation of job i;

$t_{i, j, k} = (t_{i, j, k}^{1}, t_{i, j, k}^{2}, t_{i, j, k}^{3})$ : the fuzzy processing time for O_i,j on machine M_k;

$C_{i, j} = (C_{i, j}^{1}, C_{i, j}^{2}, C_{i, j}^{3})$ : the fuzzy completion time for O_i,j;

M_i,j: the set of available machines for the operation O_i,j;

$W_{k} = (W_{k}^{1}, W_{k}^{2}, W_{k}^{3})$ : the fuzzy machine workload of machine M_k;

W_max: the maximum fuzzy machine workload;

$d_{i} = (e_{i}^{1}, e_{i}^{2}, d_{i}^{1}, d_{i}^{2})$ : fuzzy due-date for job i;

w_i: the weight for job i, w_i ∈ (0, 1), $\sum_{i}^{n} w_{i} = 1$ ;

s_ie: the punished pessimistic agreement index of job i due to earliness;

s_il: the punished pessimistic agreement index of job i due to tardiness;

s_ir: the agreement index of job i on relative position between due date and completion time;

μ_{d
_i} (x): the membership function for due date d_i of job i;

μ_{C
_{i,n_i}} (x): the membership function for the fuzzy completion time of the operation C_{i,n_i}

c_ie, c_il: 1 - μ_{C
_{i,n_i}} (x) is the abscissa of the intersection with [d_i, + ∞) And (- ∞ , d_i], respectively;

C_max: the maximum fuzzy completion time.

2.1.3 Objection functions

2.1.3.1. Minimizing the maximum fuzzy completion time The maximum fuzzy completion time shall be regarded for all the jobs upon all operations being completed. It can be expressed as follows. $Min C_{max} = max_{1 \leq i \leq n} {C_{{in}_{i}}}$ (1) where C_{in
_i} indicates the fuzzy completion time for the last one operation n_i of job i.

2.1.3.2. Minimizing the maximum fuzzy machine workload The maximum fuzzy machine workload shall be regarded as the workload for all the machines. It can be expressed. $Min W_{max} = max_{1 \leq k \leq m} {W_{k}}$ (2) where W_k indicates the fuzzy workload of machine k.

2.1.3.3. Maximizing the weighted agreement index In recent years, the agreement index has been determined through calculating the value on intersection between fuzzy due date and fuzzy completion time [23, 24]. However, this method can hardly apply to dealing with the problem. To overcome this problem, we adopt a three-point satisfaction-degree model to determine the agreement index [25]. In this research, we denote the fuzzy completion time of the operation O_{i,n_i} As $C_{i, n_{i}} = (C_{i, n_{i}}^{1}, C_{i, n_{i}}^{2}, C_{i, n_{i}}^{3})$ ; with μ_{C
_{i,n_i}} (x) as its membership function; denote the fuzzy due-date of job i as $d_{i} = (e_{i}^{1}, e_{i}^{2}, d_{i}^{1}, d_{i}^{2})$ ; with μ_{d
_i} (x) as its membership function; With (- ∞ , d_i] representing a TFN less than or equal to d_i, it’s membership function is denoted by $μ_{(- \infty, d_{i}]} (y) = sup_{x \geq y} μ_{d_{i}} (x)$ . With [d_i, + ∞) representing a TFN greater than or equal to d_i, it’s membership function is denoted by $μ_{[d_{i}, + \infty)} (y) = sup_{x \leq y} μ_{d_{i}} (x)$ . A dash-noted line in Fig. 1 illustrates the membership function of μ_(-∞,di] (y) and μ_{[d_i,+∞} (y). (- ∞ , d_i] indicates that the utility of job i get punished due to tardiness. When $C_{i, n_{i}}^{2} \geq d_{i}^{1}$ , the agreement index shall be 1 if the punishment due to tardiness is the only consideration; the agreement index will decrease as $C_{i, n_{i}}^{2}$ increases and will decrease to 0 when $C_{i, n_{i}}^{2} \geq d_{i}^{2}$ . When $C_{i, n_{i}}^{2} \geq e_{i}^{2}$ , the agreement index shall be 1 if the punishment due to earliness is the only consideration; the agreement index will decrease as $C_{i, n_{i}}^{2}$ decrease and will decrease to 0 when $C_{i, n_{i}}^{2} \geq e_{i}^{1}$ .

Fig.1

Three-point satisfaction-degree model on trapezoid due-date.

The pessimistic satisfaction-degree is defined by $s_{i} = inf_{x \in X} max (λ (μ (x)), μ_{d_{i}} (x))$ (3)

Where λ (μ (x)) = 1 - μ (x) represents the reversed sequence function for μ (x) (μ (x) ∈ [0, 1]). The fuzzy pessimistic criterion is focused on the infimum of max(λ (μ (x)) , μ_{d
_i} (x)) i.e. the lowest point in the high reliability area [26]. The pessimistic satisfaction-degree equals to the value on the intersection of λ (μ (x)) and μ_{d
_i} (x). Figure 1 depicts the relations between fuzzy due date and fuzzy completion time in a schedule. It can be seen that s_ie is determined by the value of the intersection between the left part of 1 - μ_{C
_{i,n_i}} (x) and μ_{[d_i,+∞)} (x). This value denotes the possibility of the worst schedule in which the fuzzy completion is earlier than the fuzzy due date. Besides, s_ie is determined by the value on the intersection between the right part of 1 - μ_{C
_{i,n_i}} (x) and μ_{(-∞,d_i]} (x). This value denotes the possibility of the worst schedule in which the fuzzy completion is later than the fuzzy due date. $C_{i, n_{i}}^{2}$ is the fuzzy completion time of the highest reliability, with it’s agreement index represented by s_ir. To sum up, the three-point satisfaction-degree model can be expressed as below: ${AI}_{i} = s_{ie} + s_{il} + s_{ir}$ (4) $s_{ie} = inf_{x} max (1 - μ_{C_{i, n_{i}}} (x), μ_{[d_{i}, + \infty)} (x))$ (5) $s_{il} = inf_{x} max (1 - μ_{C_{i, n_{i}}} (x), μ_{(- \infty, d_{i}]} (x))$ (6) $s_{ir} = μ_{d_{i}} (C_{i, n_{i}}^{2})$ (7) where s_ie and s_il can be calculated with following differential equation. $s_{ie} = {\begin{matrix} s_{ie} = 0 & C_{i, n_{i}}^{2} \leq e_{i}^{1} \\ s_{ie} = 1 & C_{i, n_{i}}^{1} \geq e_{i}^{2} \\ s_{ie} = (C_{i, n_{i}}^{2} - e_{i}^{1}) / - (e_{i}^{2} - e_{i}^{1} + C_{i, n_{i}}^{2} - C_{i, n_{i}}^{1}) & C_{i, n_{i}}^{2} > e_{i}^{1}, C_{i, n_{i}}^{1} < e_{i}^{2} \end{matrix}$ (8) $s_{il} = {\begin{matrix} s_{il} = 0 & C_{i . n_{i}}^{2} \leq d_{i}^{2} \\ s_{il} = 1 & C_{i, n_{i}}^{3} \leq d_{i}^{1} \\ s_{il} = (d_{i}^{2} - C_{i, n_{i}}^{2}) / (C_{i, n_{i}}^{3} - C_{i, n_{i}}^{2} + d_{i}^{2} - d_{i}^{1}) & C_{i, n_{i}}^{3} > d_{i}^{1}, C_{i, n_{i}}^{2} < d_{i}^{2} \end{matrix}$ (9)

From the above equations and figure, the three-point satisfaction-degree model is built the points c_ie, c_il and $C_{i, n_{i}}^{2}$ . As c_ie increases, the punishment will decrease and the utility s_ie will be improved due to tardiness; while as c_il decreases, the punishment will decrease and the utility s_il will be improved due to tardiness. The optimization goal is to improve the agreement index by adjusting the relative position between the fuzzy completion time C_{i,n_i} and the fuzzy due date d_i so as to make the vertex of the membership function can be possibly located in the high agreement index area. As the geometry of the membership function μ_{C
_{i,n_i}} (x) is determined by the point (c_ie, s_ie) and (c_il, s_il). The relative position between μ_{C
_{i,n_i}} (x) and μ_{d
_i} (x) is determined by the point $(C_{i, n_{i}}^{2}, s_{ir})$ . The agreement index can be expressed as following. $Min AI = \sum_{i = 1}^{n} w_{i} {AI}_{i}$ (10) where AI_i refers to the agreement index of job i, w_i refers to weight of job i. In this paper, the weight of all job are identical.

2.2 Multi-objective optimization

Pareto domination: Supposing that X₁ and X₂ are any two of feasible solutions and each has r objective functions. If they can satisfy Equations 11 and 12, than we can say X₁ dominate X₂. $f_{i} (X_{1}) \leq f_{i} (X_{2}), i = 1, 2, \dots, r$ (11) $f_{i} (X_{1}) < f_{i} (X_{2}), \exists i \in {1, 2, \dots, r}$ (12)

Pareto optimal solution: If X₁ dominating X₂ indicates that X₁ is better than X₂ for all objectives. The solution not being dominated by any others shall be considered as Pareto optimal solution.

Pareto archive set: The Pareto archive set is used to save all the Pareto optimal solutions. It can be continuously updated with the iteration of the proposed algorithm, kicking out the solutions being dominated Fig. 2. illustrates the updating procedures.

Fig.2

The Pareto archive set updating procedure.

2.3 Operation on triangular fuzzy number

It is necessary to make some important operation on the triangular fuzzy number denoting the processing time. In this paper, these important operations include additional operation, max operation and rank operation. The additional operation is made to calculate the fuzzy completion time; max operation is to obtain fuzzy starting time of operation and rand operation is to rank the fuzzy completion time of all jobs.

Supposing A = (a₁, a₂, a₃), B = (b₁, b₂, b₃), addition operation can be expressed as below. $A + B = (a_{1} + b_{1}, a_{2} + b_{2}, a_{3} + b_{3})$ (13)

Max operation of two TFNs is made by the following formula [8, 9]:

if A > B, then A ∨ B = A; else A ∨ B = B.

Rank operation is made to compare A = (a₁, a₂, a₃) and B = (b₁, b₂, b₃), by three criteria shown as below: [27] (1)

If (a₁ + 2a₂ + a₃)/4 > (<) (b₁ + 2b₂ + b₃)/4, then A > (<) B;

If (a₁ + 2a₂ + a₃)/4 = (b₁ + 2b₂ + b₃)/4, then A and B are comparable. If a₂ > (<) b₂, then A > (<) B;

If a₂ = b₂, then a₃ - a₁ and b₃ - b₁ are comparable. If a₃ - a₁ > (<) b₃ - b₁, then A > (<) B;

3.3 The basic ABC algorithm

Artificial bee colony (ABC) algorithm is a population-based meta-heuristic inspired by the foraging behavior of a bee colony. It involves three kinds of bees, namely, employed bee, onlooker bee and scout bee. Employed bee exploits a food source; onlooker bee stays in the hive and decides on the food source to be chosen; Scout bee conducts a random search for a new food source. Each solution under consideration is analogous to a food source, and the fitness of the solution corresponds to the nectar abundance of the associated food source. The basic ABC algorithm has main steps as shown below.

3.1 Control parameters

The basic ABC algorithm has three control parameters, the termination criterion, the maximum number of improvement trials (Limit) and the number of food sources (SN).

3.2 Initial population

Initial population can be generated in a random fashion from the basic ABC algorithm. Using X_i = {x_i1, x_i2, …, x_in} to denote the ith food source, where n indicates the number of independent variables of optimization problem. we can calculate the initial population in formula as below: $x_{i}^{j} = x_{min}^{j} + r \times (x_{max}^{j} - x_{min}^{j})$ (14) where $x_{max}^{j}$ and $x_{min}^{j}$ are the lower and upper bounds of the jth variable, respectively, r refers to the uniform random number with in the range [0, 1f].

3.3 Employed bee phase

Employed bee performs local search operator of a previous food source to generate a new one. It can be calculated as follows: $x_{new}^{j} = x_{i}^{j} + r^{'} \times (x_{i}^{j} - x_{k}^{j})$ (15) where j ∈ {1, 2, …, n} and k ∈ {1, 2, …, SN} ∧ k ≠ i, in which j is randomly chosen, k is different from i. r′ refers to a uniform random number with in the range [-1, 1].

3.4 Onlooker bee phase

Onlooker bee aims to choose a food source by the probability value associated with feasible solution, p_i is calculated by this expression: $p_{i} = \frac{{fit}_{i}}{\sum_{i = 1}^{SN} {fit}_{i}}$ (16) where fit_i indicates the fitness value of feasible solution i, p_i indicates probability value that feasible solution i can be selected for to carry out local searching operation. When the local searching operation has been completed, the abundant food source will be obtained.

3.5 Scout bee phase

If a food source cannot be optimized through Limit of local searching operations, it shall be abandoned. At that time, employed bee and onlooker bee will turn into the scout bee. And the new scout bee will start to search for other food source randomly: $x_{i}^{j} = x_{min}^{j} + r \times (x_{max}^{j} - x_{min}^{j})$ (17)

The best solution in each iteration shall be recorded to update the global optimal solution which will be obtained when the algorithm is completed.

4.4 The proposed MABC algorithm

The basic ABC algorithm was originally proposed to optimize the continuous function. It is not applicable to discrete combinatorial optimization problem. In this paper, MFFJSP is solved by the MABC algorithm as detailed below.

4.1 Encoding and decoding

In the encoding scheme, MFFJSP involves machine assignment vector and operation sequence vector. The operation sequence vector adopts operation-based representation method that can meet the constraint and guarantee a feasible solution. The machine assignment vector corresponds to the operation sequence vector. Besides, the dimensions of those two vector shall be equal to the total number of operations [28].

We explain this method by giving an example. Table 1 and Fig. 3 respectively show the fuzzy processing time of each operation and a solution represented by two vectors. In the decoding scheme, each number of the operation sequence vector can be decoded from left to right to denote the operation of each job, with jth refers to the jth operation of the job. For example, the number 2 at the forefront indicates that the first operation of job2 is processed on machine 1, the number 3 in seventh place shows that the third operation of job3 is processed on machine 3. With this decoding scheme, the fuzzy Gantt chart of this solution is obtained, as illustrated in Fig. 4. In the chart, the TFN under the line indicates the fuzzy start time of each operation, and the TFN above the line indicates the completion time.

Fig.3

Solution representation.

Table 1

Fuzzy processing time

Operation	Machines
	M ₁	M ₂	M ₃
O₁1	(1,2,5)	(4,5,6)	(2,3,4)
O₁2	(2,4,5)	(1,2,3)	(3,5,7)
O₂1	(1,3,4)	(4,6,8)	(2,3,4)
O₂2	(2,3,5)	(1,2,4)	(4,5,7)
O₂3	(2,3,4)	(3,5,8)	(3,4,8)
O₃1	(3,4,7)	(1,2,4)	(3,6,7)
O₃2	(4,6,9)	(2,3,5)	(5,7,9)
O₃3	(1,2,5)	(3,5,7)	(4,8,9)

4.2 Variable neighborhood search

The VNS algorithm is adopted primarily is to expand the searching space and to improve the quality of solutions by changing the neighborhood structure [29]. The changing-neighborhood structure could effectively prevent the proposed algorithm from stopping at local optimum and help finally achieve the global optimum. In this research, we employ three effective neighborhood structures to perform the local search operator. The VNS procedure is given in Fig. 5.

Fig.4

Fuzzy Gantt chart.

Fig.5

The VNS procedure.

4.2.1 Neighborhood structure N1

Neighborhood structure N1 introduces the insertion method, including forward and backward insertion [30] into the operation sequence vector to generate a neighborhood solution. A selected operation can be randomly inserted into a feasible position within the maximum moving distance.

D denotes the maximum moving distance, L denotes the total of all operations. p_i,j indicates the initial position of operation O_i,j; $p_{i, j}^{*}$ indicates the new position; the operation O_i,j is inserted by moving; and random(D) denotes a uniform random integer within the range [1, D]. Figure 6 shows how both the forward and backward insertion proceed. Assuming that operation O_3,1 and O_2,3 are selected to perform forward and backward insertion, respectively. D = 3 and D = 4, respectively indicates the maximum moving distance by which the insertion point cannot surpass operation O_3,2 and O_2,2. Forward and backward insertion points for operation O_3,2 and O_2,2 shall be calculated by using $p_{3, 1}^{*} = p_{3, 1} + random (3)$ and $p_{2, 3}^{*} = p_{2, 3} - random (4)$ , respectively.

Fig.6

Forward and backward insertion.

The adoption of neighborhood structure N1 has brought about a new neighborhood solution for the operation sequence vector. A least-completion-time machine approach is introduced to generate the corresponding machine assignment vector. This approach can determine the machine that allows the least fuzzy completion time for current operation O_2,3 from the machine set M_i,j. For example, operation O_2,3 can be processed on machine M₁, M₂ and M₃, and the fuzzy completion time on those three machine are respectively TFNs (8, 14, 21), (8, 14, 20) and (9, 15, 22), thus the lease-completion-time machine for operation O_2,3 is machine M₂.

4.2.2 Neighborhood structure N2

Neighborhood structure N2 is used to randomly select an operation and changes the processing machine of the selected operation [31]. This method is described as follows. Firstly, an operation O_i,j is selected from the operation sequence vector. Secondly, the machine M_k is determined for processing O_i,j. Thirdly, a set of machine M_i,j that can process O_i,j is determined. Finally, selecting a random machine from M_i,j (expect M_k) to process O_i,j. Figure 7 shows an example of neighborhood structure N2.

Fig.7

Neighborhood structure N2.

4.2.3 Neighborhood structure N3

Neighborhood structure N3 adopts the random search-based approach [32]. The whole neighborhood solution is depicted in Fig. 8. This approach includes two main steps. The first step is to select three positions in the operation sequence vector, then generate all neighborhood solutions. And the second step is to select the optimal neighborhood solution as a new current solution.

Fig.8

Neighborhood structure N3.

The adoption of neighborhood structure N3 has brought about a new neighborhood solution for the operation sequence vector. A least-workload machine approach is introduced to generate the corresponding machine assignment vector. This approach can determine the machine that allows the least fuzzy machine workload for current operation O_2,3 from machine set M_i,j. For example, operation O_2,3 can be processed on machine M₁, M₂ and M₃ as in Table 1, and the fuzzy machine workload of current operation O_2,3 on those three machines is respectively TFNs (5, 20, 18), (6, 10, 17) and (9, 15, 22), thus the least-workload machine to process operation O_2,3 is machine M₂.

4.3 Crossover operator

In an ordinary way, the crossover operator is used to select two parent solutions based on crossover probability p_c to generate two children solutions. The fitness value of those two children solutions will be calculated and serve as the basis to determine whether to replace those two parent solutions. This mechanism is obviously an important way to maintain solution diversity. Two crossover operators mentioned in this paper are improved precedence operation crossover (IPOX) and multiple point crossover (MPX), both performed for the machine assignment vector and operation sequence vector. Figure 9 illustrates those two crossover operators.

Fig.9

Crossover operator.

4.4 Employed bee phase

The MABC algorithm embedded VNS algorithm in local search operator to acquire superior neighborhood food source. If the current solution can be dominated by the new solution, it will be substituted by the latter; otherwise, it will be retained. If the new solution and the current solution are incomparable, we shall compare their evaluation values to make the decision. The evaluating function can be expressed as below:

$F_{1} (X_{i}) = \frac{max_{1 \leq j \leq SN} {f_{1} (X_{j})} - f_{1} (X_{i})}{max_{1 \leq j \leq SN} {f_{1} (X_{j})} - min_{1 \leq j \leq SN} {f_{1} (X_{j})}}$ (18)

$F_{2} (X_{j}) = \frac{max_{1 \leq j \leq SN} {f_{2} (X_{j})} - f_{2} (X_{i})}{max_{1 \leq j \leq SN} {f_{2} (X_{j})} - min_{1 \leq j \leq SN} {f_{2} (X_{j})}}$ (19)

$F_{3} (X_{i}) = \frac{f_{3} (X_{i}) - min_{1 \leq j \leq SN} {f_{3} (X_{j})}}{max_{1 \leq j \leq SN} {f_{3} (X_{j})} - min_{1 \leq j \leq SN} {f_{3} (X_{j})}}$ (20)

$F (X_{i}) = F_{1} (X_{i}) + F_{2} (X_{i}) + F_{3} (X_{i})$ (21) where f₁ (x_i), f₂ (x_i) and f₃ (x_i) represent the function values of three objective of the solution X_i, respectively. $max_{1 \leq j \leq SN} {f_{k} (X_{j})}$ and $min_{1 \leq j \leq SN} {f_{k} (X_{j})}$ represent the maximum and minimum values of the kth objective function in population, respectively. The evaluation values of those two solutions will be compared to determine whether to replace the current solution with the new one. Figure 10 shows the optimum selecting procedure.

Fig.10

The optimum selecting procedure.

4.5 Onlooker bee phase

Onlooker bee detects the nectar amount of all food sources and selects the abundant food source to perform local search operator. The basic ABC algorithm is to compare the fitness value to choose food source. But this method cannot meet some demands of MFFJSP. Hence, the proposed MABC algorithm adopts a tournament selection to screen the superior solutions. The tournament selection mechanism is to select three solutions from the population and let the onlooker bee determine which solution is better. If the selected solution meets the requirement for crossover operator, it will perform crossover operator; otherwise, it will perform local search operator. After comparing the new solution with the old one, we will preserve the better.

4.6 Scout bee phase

If a food source cannot be optimized after performing a certain trial limit of local search operator, it shall be abandoned, and the scout bee will search randomly for some new food sources.

4.7 Population initialization

In our proposed MABC algorithm, population initialization plays a significant role in increasing the convergence rate of the algorithm and improving the quality of solutions.

In order to generate initial operation sequences, we adopt the rule of generating the sequence of the operations randomly. When it’s completed, we adopt the least-completion-time machine and least-workload machine rules as well as the random rule to initiate machine assignments

4.8 Procedure of MABC

The following indicates the steps of the presented MABC:

Step 1. Initialize the population and control parameters of MABC.

Step 2. Employed bee applies local search operator to each food source in the population to obtain the better solution; update the external Pareto AS.

Step 3. Onlooker bee selects a food source randomly through a tournament selection mechanism, and the selected food source performs local search operator or crossover operator to obtain the better solution; repeat the above operations SN times and update the external Pareto AS.

Step 4. If a food source cannot be optimized for times of generations limit, it shall be abandoned, and the scout bee will search randomly for some new food sources; update external Pareto AS.

Step 5. Determine whether the termination criterion can be met. If yes, input external Pareto AS; otherwise, go to step2.

5 Computational results

For the sake of validating the performance of the presented algorithm in this paper, we conduct some numerical simulations based on the five instances [8, 9] and a practical MFFJSP. The algorithm was implemented in MATLAB R2010b, running on 3.2-GHz PC with 3-GB RAM. The parameters of the proposed MABC are summarized as follows: the population size is 200, the crossover probability P_c is 0.8, the value of Limit is 20 and the maximal generation number SN is 300.

5.1 Comparative results

Five instances [8, 9] are used for comparing the proposed algorithm with six existing algorithms including IDPSO [11], IABC [22], EDA [10], HABC [21], CGA [9] and DIGA [8]. The results of average, best and worst values in 30 runs are shown in Table 2 and the results of the compared algorithms were directly from paper [11, 22].

Table 2
Computational results of the five instances

Instance Algorithm Average value Best value Worst value

Case 1 MABC (19.23, 28.07, 38.87) (21, 28, 37) (22, 28, 38)

IDPSO (20.6, 29.87, 40.17) (19, 28, 40) (21, 31, 41)

IABC (20.1, 29.4, 40.3) (19, 28, 39) (22, 30, 42)

EDA (20.3, 30.5, 41.6) (20, 28, 40) (22, 32, 43)

HABC (21.0, 32.0, 43.6) (19, 30, 43) (23, 33, 46)

CGA (23.1, 33.1, 43.4) (21, 29, 41) (25, 37, 47)

DIGA (22.5, 32.7, 43.3) (21, 31, 40) (25, 36, 48)

Case 2 MABC (30, 45, 58.03) (30, 45, 58) (30, 45, 59)

IDPSO (32.47, 46.17, 57.53) (30, 46, 58) (35, 47, 57)

IABC (32.3, 46.2, 57.3) (33, 45, 58) (35, 46, 57)

EDA (33.7, 46.9, 57.9) (32, 46, 57) (34, 48, 58)

HABC (33.0, 47.8, 62.2) (33, 46, 58) (36, 48, 65)

CGA (35.0, 47.1, 60.6) (32, 47, 57) (38, 49, 64)

DIGA (35.4, 48.4, 62.3) (33, 48, 57) (37, 50, 65)

Case 3 MABC (30.6, 43.93, 58.57) (29, 44, 58) (30, 45, 59)

IDPSO (32.47, 46.20, 60.90) (33, 45, 60) (35, 49, 64)

IABC (31.8, 45.8, 59.6) (31, 45, 57) (33, 47, 63)

EDA (32.8, 47.2, 62.9) (31, 46, 60) (34, 49, 66)

HABC (33.9, 50.8, 67.3) (33, 47, 64) (36, 54, 70)

CGA (36.4, 50.8, 66.0) (34, 47, 63) (38, 53, 71)

DIGA (37.3, 53.0, 66.9) (37, 49, 64) (41, 58, 75)

Case 4 MABC (23.2, 34.4, 48.43) (22, 34, 48) (24, 35, 49)

IDPSO (24.90, 36.67, 51.00) (23, 35, 49) (27, 38, 51)

IABC (24.1, 36.1, 50.9) (25, 34, 49) (24, 38, 55)

EDA (24.8, 37.2, 51.9) (21, 36, 50) (24, 39, 57)

HABC (25.5, 40.0, 56.3) (23, 38, 53) (25, 44, 59)

CGA (27.4, 40.4, 55.0) (26, 37, 51) (29, 42, 59)

DIGA (29.2, 42.9, 57.5) (29, 41, 56) (29, 46, 60)

Case 5 MABC (37.4, 55.63, 76.37) (35, 55, 74) (37, 58, 77)

IDPSO (40.60, 58.03, 78.97) (35, 56, 81) (43, 60, 82)

IABC (37.8, 55.8, 77.7) (36, 54, 74) (42, 59, 84)

EDA (38.6, 56.9, 78.3) (36, 55, 73) (40, 60, 81)

HABC – – –

CGA (47.0, 65.4, 86.0) (42, 62, 82) (49, 70, 91)

DIGA (45.8, 66.3, 88.7) (42, 63, 84) (49, 71, 92)

Instance	Algorithm	Average value	Best value	Worst value
Case 1	MABC	(19.23, 28.07, 38.87)	(21, 28, 37)	(22, 28, 38)
IDPSO	(20.6, 29.87, 40.17)	(19, 28, 40)	(21, 31, 41)
IABC	(20.1, 29.4, 40.3)	(19, 28, 39)	(22, 30, 42)
EDA	(20.3, 30.5, 41.6)	(20, 28, 40)	(22, 32, 43)
HABC	(21.0, 32.0, 43.6)	(19, 30, 43)	(23, 33, 46)
CGA	(23.1, 33.1, 43.4)	(21, 29, 41)	(25, 37, 47)
DIGA	(22.5, 32.7, 43.3)	(21, 31, 40)	(25, 36, 48)
Case 2	MABC	(30, 45, 58.03)	(30, 45, 58)	(30, 45, 59)
IDPSO	(32.47, 46.17, 57.53)	(30, 46, 58)	(35, 47, 57)
IABC	(32.3, 46.2, 57.3)	(33, 45, 58)	(35, 46, 57)
EDA	(33.7, 46.9, 57.9)	(32, 46, 57)	(34, 48, 58)
HABC	(33.0, 47.8, 62.2)	(33, 46, 58)	(36, 48, 65)
CGA	(35.0, 47.1, 60.6)	(32, 47, 57)	(38, 49, 64)
DIGA	(35.4, 48.4, 62.3)	(33, 48, 57)	(37, 50, 65)
Case 3	MABC	(30.6, 43.93, 58.57)	(29, 44, 58)	(30, 45, 59)
IDPSO	(32.47, 46.20, 60.90)	(33, 45, 60)	(35, 49, 64)
IABC	(31.8, 45.8, 59.6)	(31, 45, 57)	(33, 47, 63)
EDA	(32.8, 47.2, 62.9)	(31, 46, 60)	(34, 49, 66)
HABC	(33.9, 50.8, 67.3)	(33, 47, 64)	(36, 54, 70)
CGA	(36.4, 50.8, 66.0)	(34, 47, 63)	(38, 53, 71)
DIGA	(37.3, 53.0, 66.9)	(37, 49, 64)	(41, 58, 75)
Case 4	MABC	(23.2, 34.4, 48.43)	(22, 34, 48)	(24, 35, 49)
IDPSO	(24.90, 36.67, 51.00)	(23, 35, 49)	(27, 38, 51)
IABC	(24.1, 36.1, 50.9)	(25, 34, 49)	(24, 38, 55)
EDA	(24.8, 37.2, 51.9)	(21, 36, 50)	(24, 39, 57)
HABC	(25.5, 40.0, 56.3)	(23, 38, 53)	(25, 44, 59)
CGA	(27.4, 40.4, 55.0)	(26, 37, 51)	(29, 42, 59)
DIGA	(29.2, 42.9, 57.5)	(29, 41, 56)	(29, 46, 60)
Case 5	MABC	(37.4, 55.63, 76.37)	(35, 55, 74)	(37, 58, 77)
IDPSO	(40.60, 58.03, 78.97)	(35, 56, 81)	(43, 60, 82)
IABC	(37.8, 55.8, 77.7)	(36, 54, 74)	(42, 59, 84)
EDA	(38.6, 56.9, 78.3)	(36, 55, 73)	(40, 60, 81)
HABC	–	–	–
CGA	(47.0, 65.4, 86.0)	(42, 62, 82)	(49, 70, 91)
DIGA	(45.8, 66.3, 88.7)	(42, 63, 84)	(49, 71, 92)

It can be seen from Table 2 that the proposed MABC algorithm performs better than six others algorithms. For five instances, MABC algorithm can obtain better average results than those of the six compared algorithms. Moreover, MABC can find minimum worst values for five instances. Only the best value of the instance 5 cannot obtain the optimal value, but the optimal value which is obtained by the MABC nearly approach to (36, 54, 74). The results of statistical analysis of five instances are listed in Table 3. Assume that C_max is denoted by $(C_{max}^{1}, C_{max}^{2}, C_{max}^{3})$ , AV (C_max) and STD (C_max) denote the average value of $(C_{max}^{1} + 2 C_{max}^{2} + C_{max}^{3}) / 4$ and standard deviation of $(C_{max}^{1} + 2 C_{max}^{2} + C_{max}^{3}) / 4$ , respectively. The AV (C_max) and STD (C_max) of the proposed algorithm are compared with IDPSO [11], EDA [10] and DIGA [8] to test the stability of MABC. From Table 3, it is very obvious that AV (C_max) and STD (C_max) obtained by MABC are better than the compared algorithms. In summary, the proposed MABC is competitive to the existing algorithms to solve FFJSP. In Figs.11–13, the fuzzy Gantt charts for the best solutions obtained by proposed algorithm of five instances are illustrated, respectively.

Fig.11

Fuzzy gantt chart of Instance 1 which best value is MABA(21,28,37)

Fig.12

Fuzzy gantt chart of Instance 3 which best value is MABA(29,44,58).

Fig.13

Fuzzy gantt chart of Instance 5 which best value is MABA(35,55,74).

Table 3

Results of statistical analysis of the five instances

Instance	DIGA		EDA		IDPSO		MABC
	AV(C_max)	STD(C_max)	AV(C_max)	STD(C_max)	AV(C_max)	STD(C_max)	AV(C_max)	STD(C_max)
Case 1	3.441e+01	2.676e+00	3.379e+01	1.114e+00	3.006e+01	6.014e– 01	2.856e+01	1.260e–01
Case 2	4.969e+01	2.232e+00	4.871e+01	1.826e+00	4.577e+01	4.795e–01	4.451e+01	4.564e–02
Case 3	5.353e+01	3.100e+00	5.295e+01	1.966e+00	4.643e+01	9.669e–01	4.426e+01	2.898e–01
Case 4	4.310e+01	2.852e+00	4.097e+01	1.591e+00	3.740e+01	4.281e–01	3.511e+01	3.922e–01
Case 5	6.670e+01	4.395e+00	6.437e+01	1.022e+00	5.882e+01	9.863e–01	5.626e+01	6.711e–01

5.2 Analysis on a practical MFFJSP

Due to the similarity between the hull curved block assembly welding system and the MFFJSP, a practical case which derived from a recently built shipyard is solved to validate the feasibility of proposed algorithm. This case consists of six blocks (jobs), six working groups (machines) and each block needs to complete eight operations. The case is simulated 10 times independently by P-DABC [33] and the proposed MABC under the same experimental environment. The computational results and Pareto solutions set of a practical case are provided in the Table 4. From Table 4, it is can be shown that the presented MABC is superior to P-DABC on the average values of three objective values including the maximum fuzzy completion time C_max, maximum fuzzy machine workload W_max, weighted agreement index AI.

Table 4
Computational results of a practical case

Algorithm Average value (C_max) Average value (W_max) Average value (AI)

P-DABC (177.15, 199.44, 228.37) (81.03, 91.11, 104.03) 1.91

MABC (170.55, 191.30, 217.86) (75.44, 84.62, 96.55) 2.10

Algorithm	Average value (C_max)	Average value (W_max)	Average value (AI)
P-DABC	(177.15, 199.44, 228.37)	(81.03, 91.11, 104.03)	1.91
MABC	(170.55, 191.30, 217.86)	(75.44, 84.62, 96.55)	2.10

For the sake of verifying the performance of the presented algorithm on quality and spread of Pareto solution, the distributions of Pareto solution obtained by P-DABC and MABC are presented in Fig. 14. Compared to the P-DABC, the MABC can obtain a better spread of Pareto solutions, generate higher-quality Pareto solutions and find more Pareto solution.

Fig.14

Distributions of Pareto solution found for the practical case.

A representative solution is selected from the Pareto solution for further explaining the MFFJSP. Three objective values of this selected solution are (173.5, 193.5, 218.5), (64, 71, 80) and 2.25155, respectively. For this selected solution, the relationship between the makespan and due date for each job is shown in Fig. 15 and agreement index of each job is shown in Table 5. Figure 16 shows the fuzzy Gantt chart of the selected solution. From Table 5, it is observed that the agreement index obtained by the MABC is very sufficient and the validity of three-point satisfaction-degree model has been demonstrated. According to above description, it can be concluded that the presented MABC is more effective than P-DABC to solve the MFFJSP.

Fig.15

The relationship between the makespan and due date for each job on the selected solution.

Fig.16

Fuzzy Gantt chart of the selected solution.

Table 5

The agreement index of each job on the selected solution

Job	Job1	Job2	Job3	Job4	Job5	Job6
Agreement Index	2.24314	2.15613	2.29576	2.27857	2.26035	2.27536

5.3 Parameter sensitivity analysis

For the proposed MABC, the three key parameters including the population size SN, the crossover probability P_c, the value of Limit, have great effects on its test results. Thus, we designed an experimental test of the MABC parameters which consist of three factors to determine the best combination of values of the parameters. In the test, the parameters setting for them each in four levels can be presented in Table 6. To decrease the number of experimental test, the Taguchi’s orthogonal array of L₁₆(4³) (see Table 7) is selected as the best test design to perform the experiments.

Table 6
The factor level of parameters

Parameters Value range Factor level

1 2 3 4

SN 50–200 50 100 150 200

P _c 0.5–0.8 0.5 0.6 0.7 0.8

Limit 5–20 5 10 15 20

Parameters	Value range	Factor level
		1	2	3	4
SN	50–200	50	100	150	200
P _c	0.5–0.8	0.5	0.6	0.7	0.8
Limit	5–20	5	10	15	20

Table 7

Orthogonal array and the results of experiment

Test	Parameters			ARV(C_max)	ARV(W_max)	ARV(AI)
	SN	P _c	Limit
1	1	1	1	193.926	92.119	2.054
2	1	2	2	193.739	92.752	2.116
3	1	3	3	196.703	86.125	1.977
4	1	4	4	197.125	91.493	2.088
5	2	1	2	192.366	92.193	2.097
6	2	2	1	196.728	91.103	2.040
7	2	3	4	193.459	93.480	2.090
8	2	4	3	194.399	89.594	2.118
9	3	1	3	193	91.65	2.134
10	3	2	4	193.431	91.143	2.128
11	3	3	1	192.178	94.207	2.106
12	3	4	2	192.943	91.325	2.073
13	4	1	4	193.730	89.417	2.141
14	4	2	3	193.545	91.380	2.098
15	4	3	2	192.353	91.486	2.107
16	4	4	1	192.146	90.582	2.070

According to the orthogonal array, we run the MABC for solving the practical MFFJSP with each parameter combination 10 times independently. For two triangular fuzzy number $C_{max} = (C_{max}^{1}, C_{max}^{2}, C_{max}^{3})$ and $W_{max} = (W_{max}^{1}, W_{max}^{2}, W_{max}^{3})$ , the response variable values (RV) of maximum fuzzy completion time C_max, maximum fuzzy machine workload W_max can be defined as $RV (C_{max}) = (C_{max}^{1} + 2 C_{max}^{2} + C_{max}^{3}) / 4$ and $RV (W_{max}) = (W_{max}^{1} + 2 W_{max}^{2} + W_{max}^{3}) / 4$ , respectively. Consequently, the average response variable (ARV) values of the three optimization objectives which are obtained by the MABC in 20 times are shown in Table 7. The factor level trend regarding different parameters presented in Fig. 17.

Fig.17

The factor level trend regarding AV.

Although Fig. 17 can depict the factor level trend regarding three parameters, but it cannot show the influence of these parameters for MABC. In our paper, Equations (18–21) are employed to calculate the evaluation values. The evaluation values and law of each parameter are presented in Table 8.

Table 8

Table8

Parameters	SN	P _c	Limit
1	0.6094	2.0522	0.8477
2	1.1631	1.3022	1.7952
3	1.9472	1.1971	1.8149
4	2.3820	1.5679	1.6629
Delta	1.7726	0.8551	0.9672
Rank	1	3	2

Evaluation values and law of each parameter

In Table 8, “Delta” represents the maximum evaluation values minus the minimum evaluation values for each parameter and “Rank” represents the rank of “Delta.” “Rank” reflects the importance of each parameter. In Table 8, we can see that the population size SN is most important and the value of Limit and crossover probability P_c ranks second and third, respectively. As the results, the parameter combination with SN = 200, P_c = 0.5 and Limit = 15 can be determined as the best parameter combination.

6 Conclusions

In this paper, a modified artificial bee colony is proposed to settle the multi-objective FFJSP. In order to reduce the complexity in calculating agreement index, the three-point satisfaction-degree model is introduced in MABC. A novel variable neighborhood search which consists of three effective neighborhood structures is designed for the MABC to implement the local search operator. The crossover operator is also performed on the machine assignment vector and the operation sequence vector successively. Due to the quality of initial population having effect on the convergence of the proposed MABC, some initial methods are applied for obtaining a high-performance initial population. Numbers of benchmark problems are solved to prove the superior efficiency of the proposed algorithm. Finally, the parameter sensitivity analysis of three key parameters is investigated based on the Taguchi method of DOE.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China (No. 51275104) and supported in part by the Specialized Research Fund for the Doctoral Program of Higher Education (No. 20132304120021). The authors would like to thank Prof. Qiu Chang-hua of Harbin Engineering University for his discussion, during the course of this study.

References

Pezzella ,

Morganti and

Ciaschetti , A genetic algorithm for the Flexible Job-shop Scheduling Problem, Computers in Operational Research 35(10) (2008), 3202–3212.

Zhang ,

Gao and

Shi , An effective genetic algorithm for the flexible job-shop scheduling problem, Expert Systems with Applications 38(4) (2011), 3563–3573.

Brucker and

Schlie , Job-shop scheduling with multi-purpose machines, Computing 45(4) (1991), 369–375.

Gao ,

Sun and

Gen , A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems, Computers & Operations Research 35(9) (2008), 2892–2907.

Zhang ,

Shao ,

Li and

Gao , An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem, Computers & Industrial Engineering 56(4) (2009), 1309–1318.

Saidi-Mehrabad and

Fattahi , Flexible job shop scheduling with tabu search algorithms, International Journal of Advanced Manufacturing Technology 32(5-6) (2007), 563–570.

Li ,

Xie ,

Pan and

Wang , A hybrid artificial bee colony algorithm for flexible job shop scheduling problems, Computer Integrated Manufacturing Systems 6(2) (2011), 78–83.

Deming , A genetic algorithm for flexible job shop scheduling with fuzzy processing time, International Journal of Production Research 48(10) (2010), 2995–3013.

Lei , Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling, Applied Soft Computing Journal 12(8) (2012), 2237–2245.

10.

Wang ,

Xu and

Min , An effective estimation of distribution algorithm for the flexible job-shop scheduling problem with fuzzy processing time, International Journal of Production Research 51(12) (2013), 3778–3793.

11.

Huang ,

Tian ,

Wang and

Ji , An improved version of discrete particle swarm optimization for flexible job shop scheduling problem with fuzzy processing time, Mathematical Problems in Engineering 2016(1) (2016), 1–13.

12.

Lin , A hybrid biogeography-based optimization for the fuzzy flexible job-shop scheduling problem, Knowledge-Based Systems 78(1) (2015), 59–74.

13.

Liu ,

Fan and

Liu , A fast estimation of distribution algorithm for dynamic fuzzy flexible job-shop scheduling problem, Computers & Industrial Engineering 87 (2015), 193–201.

14.

Wang ,

Gao ,

Zhang and

Li , A multi-objective genetic algorithm for fuzzy flexible job-shop scheduling problem, International Journal of Computer Applications in Technology 45(45) (2012), 115–125.

15.

Wang ,

Li and

Zhang , An improved multi-objective genetic algorithm for fuzzy flexible job-shop scheduling problem, International Journal of Computer Applications in Technology 47(2/3) (2013), 280–288.

16.

Y.L.

Zheng ,

Y.X.

Li and

D.M.

Lei , Multi-objective swarm-based neighborhood search for fuzzy flexible job shop scheduling, International Journal of Advanced Manufacturing Technology 60(9-12) (2012), 1063–1069.

17.

Wang ,

Tian and

Z.C.

Ji , Multi-objective fuzzy flexible job shop scheduling using memetic algorithm, Journal of Statistical Computation and Simulation 87(14) (2017), 2828–2846.

18.

Karaboga , An idea based on honey bee swarm for numerical optimization, Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

19.

Karaboga and

Basturk , On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing 8(1) (2008), 687–697.

20.

Karaboga and

Akay , A comparative study of artificial bee colony algorithm, Applied Mathematics & Computation 214(1) (2009), 108–132.

21.

Wang ,

Zhou ,

Xu and

Min , A hybrid artificial bee colony algorithm for the fuzzy flexible job-shop scheduling problem, International Journal of Production Research 51(12) (2013), 3593–3608.

22.

K.Z.

Gao ,

P.N.

Suganthan ,

Q.K.

Pan ,

T.J.

Chua ,

C.S.

Chong and

T.X.

Cai , An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time, Expert Systems with Applications 65(C) (2016), 52–67.

23.

Lei , Fuzzy job shop scheduling problem with availability constraints, Computers & Industrial Engineering 58(4) (2012), 610–617.

24.

Lei , Solving fuzzy job shop scheduling problems using random key genetic algorithm, International Journal of Advanced Manufacturing Technology 49(1-4) (2010), 253–262.

25.

Wang ,

Q.Y.

Li and

X.F.

Yang , Three-point satisfaction-degree model for fuzzy job-shop scheduling problem, Control & Decision 27(7) (2012), 1082–1085 (in chinese).

26.

Dubois and

Prade , Qualitative possibility theory and its applications to constraint satisfaction and decision under uncertainty, International Journal of Intelligent Systems 14(1) (1999), 45–61.

27.

Sakawa and

Kubota , Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms, European Journal of Operational Research 120(2) (2000), 393–407.

28.

Gen ,

Tsujimura and

Kubota , Solving job-shop scheduling problems by genetic algorithm, IEEE International Conference on Systems, Man and Cybernetics, 1994 Humans, Information and Technology IEEE, Vol. 2, 1994, pp. 1577–1582.

29.

Hansen and

Mladenović , Variable neighborhood search: Principles and applications, European Journal of Operational Research 130(3) (2001), 449–467.

30.

Kaplanoglu , An object-oriented approach for multi-objective flexible job-shop scheduling problem, Knowledge-Based Systems 54(1) (2016), 71–84.

31.

Wang ,

Gao ,

Zhang and

Shao , A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem, International Journal of Advanced Manufacturing Technology 51(5-8) (2010), 757–767.

32.

Li and

Gao , An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem, International Journal of Production Economics 174 (2016), 93–91.

Solving multi-objective fuzzy flexible job shop scheduling problem using MABC algorithm

Abstract

Keywords

1 Introduction

2 Multi-objective fuzzy flexible job-shop scheduling problem

2.1 Problem description

2.1.1 Problem assumptions

2.1.2 Notations

2.1.3 Objection functions

3.1 Control parameters

3.2 Initial population

4.1 Encoding and decoding

4.6 Scout bee phase

4.7 Population initialization

4.8 Procedure of MABC

5 Computational results

5.1 Comparative results

Table 4 Computational results of a practical case Algorithm Average value (Cmax) Average value (Wmax) Average value (AI) P-DABC (177.15, 199.44, 228.37) (81.03, 91.11, 104.03) 1.91 MABC (170.55, 191.30, 217.86) (75.44, 84.62, 96.55) 2.10

Table 6 The factor level of parameters Parameters Value range Factor level 1 2 3 4 SN 50–200 50 100 150 200 P c 0.5–0.8 0.5 0.6 0.7 0.8 Limit 5–20 5 10 15 20

Footnotes

Acknowledgments

References

Table 4
Computational results of a practical case

Algorithm Average value (C_max) Average value (W_max) Average value (AI)

P-DABC (177.15, 199.44, 228.37) (81.03, 91.11, 104.03) 1.91

MABC (170.55, 191.30, 217.86) (75.44, 84.62, 96.55) 2.10

Table 6
The factor level of parameters

Parameters Value range Factor level

1 2 3 4

SN 50–200 50 100 150 200

P _c 0.5–0.8 0.5 0.6 0.7 0.8

Limit 5–20 5 10 15 20