OPEN ACCESS
The purpose of this study is to solve the multiobjective flexible job shop scheduling problem (FJSP). An improved bacterial foraging optimization algorithm (IBFOA) based on adaptive step is proposed, which sets maximum makespan, the total goods as the optimization objectives. The results obtained in this study include the algorithm encodes based on the operation to make IBFOA be applicable to FJSP. A chemotaxis based on the crowding distance selection and adaptive step is put forward to improve the local search ability of BFOA. The impacts of the obtained results are the optimal bacterial individuals can preserve curing position to additional turning and make the common ones swim to the direction of them to absorb location information.
multiobjective flexible scheduling, bacteria foraging optimization algorithm, additional turning, multiattribute grey target decision
There are two sub problems in multiobjective FJSP such as machine assignment and the process sorting. The solution of the problem consists of two stages: the stage of optimal scheduling scheme and the decision stage of the scheduling scheme. It is known that the genetic algorithm (GA) does not rely on the specific area of the problems. Its coding and evolution process is so simple that it can search the parallel solution in the global solution space. For the above reasons, it has become the powerful tool for the job shop scheduling combinatorial optimization problems. However, this algorithm also has some shortcomings such as premature convergence and low searching efficiency in later. Ju and Zhu (2007) proposed a hybrid genetic algorithm combining the particle swarm optimization, which acted the production cycle and cost as the aim. Wu et al. (2006) (Vijaychakaravarthy et al., 2014) proposed a hybrid genetic algorithm integrating the weight coefficient and niche technique. However, this method can’t guarantee the optimality of nondominated solution. The particle swarm optimization (PSO) is based on the information sharing of single particle and excellent individual. In which, the excellent individual can guide the evolution direction of the next generation. It has several advantages such as small population, simple calculation, high efficiency and strong robustness, and has achieved good application effect on solving job shop scheduling problem and multiobjective optimization Hao et al. (2013) proposed a machine selection approach to select the shorter working hour considering the load balance of machines Liu et al. (2015) proposed the double chains quantum coding, however, this approach is lack of considering the influence on process sequence because of the machine selection Geyik and Dosdoğru (2013) presented an optimization via simulation approach to solve dynamic flexible job shop scheduling problem (Teekeng and Thammano, 2012). The study deals with both determining the best process plan for each part and then finding the best machine for each operation in a dynamic flexible job shop scheduling environment. In this respect, a genetic algorithm approach is adapted to determine best part processing plan for each part and then select appropriate machines for each operation of each part according to the determined part processing plan. W. Teekeng proposed a modified version of the genetic algorithm for flexible jobshop scheduling problems (Ning et al., 2016) J. Peng proposed a cloud model evolution algorithm for FJSP based on nondominated sorting by introducing the cloud evolutionary strategy (Mahmood et al., 2017). Literature (Moslehi and Mahnam, 2011; Demir and İşleyen, 2014; Ning et al., 2016) expressed the particle as the priority level of the available machines and combined the Particle Swarm Optimization (PSO) with simulated annealing (SA) to solve the FJSP. But it adopted the weighted coefficient method to convert three objectives of FJSP into one, and can only get one optimal solution once not reflect the practical multiobjective problems. Literature (Prakash and Vidyarthi, 2014) used the equipment allocation rules and process scheduling strategy based on the priority to obtain the best local guidance with PSO.
At present, it is still in the exploratory stage of using BFOA to solve FJSP. Therefore, this paper proposes the IBFOA for multiobjective FJSP. The remaining section of the manuscript is explained as follows: the related work is delineated in Section 2. Section 3 described the System investigated and the Result. Section 4 explains about the Discussion and Conclusion.
2.1. Description for FJSP
N: the total number of workpieces to be processed, $M$ the total number of machines,$i :$ the index of workpieces, $i \in\{1,2, \ldots, N\} ; O_{i}$ : $O_{i}$ : the workpiece, $n_{i}$ the index ofprocess, $R_{i j} :$ the $j$ th process of workpiece $O_{i}, M_{i j} :$ the machine set for $R_{i j} \subseteq\{1,$ $2, \ldots, M\}, m :$ the index of machine, $m \in\left\{1,2, \ldots, M_{i j}\right\}, S_{i j m}$ can be processed on the machine m or not (1 or 0), t_{ijm}: the spent time for R_{ij} to be processed on the machine m, b_{ijm}: the start time for R_{ij} to be processed on the machine m, C_{ijm}: the completion time for R_{ij.}
2.2. Description of problem
The FJSP can be described as follow: there are $N$ workpieces to be processed on $M$ machines in the workshop, and each workpiece $O_{i}(i \in\{1,2, \ldots, N\})$ consists of a sequence of $n_{i}\left(n_{i} \geq 1\right)$ working procedures, which should be processed in a certain $\left.\text { route. } R_{i j} \text { is the } j \text { th }\left(j \in\left\{1,2, \ldots, n_{i}\right\}\right) \text { procedure of workpiece } O_{i}, M_{i j} \subseteq\{1,2, \ldots, M\}\right)$ is the machine set which can process the above working procedures, and R_{ij} can be processed by any machine $m\left(m \in\left\{1,2, \ldots, M_{i j}\right\}\right)$ with processing capability, besides the machine m has the ability to process $\mathrm{q} \geq 1$ working procedures which belong to different workpiece .
2.3. Objective function
The primary goal for the production enterprises is to complete the production tasks timely and efficiently, therefore the primary scheduling goal for FJSP is to minimize makespan through selecting suitable machine for each process and arranging the optimal processing sequence. In this paper and several new workpieces are added after the initial scheduling, and the objective function is established as follows:
(1) Minimize the makespan f1
$f 1=\min (C)=\min \left\{\max \left(C_{i}  i=1,2, \cdots, N\right)\right\}$
$C_{i j m}=S_{i j m} b_{i j m}+S_{i j m} t_{i j m}$ (1)
In equation (1), C_{i} is the completion time of workpiece O_{i}, C_{iim} is the completion time for R_{ij} processed on machine m, b_{ijm} is the initial moment for R_{ij} to be processed on machine m, b_{ij}: is the start time for R_{ij}.
(2) Minimize the total load of all the machines f2
$f 2=\min \left(\sum_{i=1}^{N} \sum_{j=1}^{n_{i}} \sum_{m=1}^{M} t_{j i m} S_{i j m}\right)$ (2)
(3) Minimize the maximum load of single machine f3
$f 3=\min \left[\max \sum_{i=1}^{N} \sum_{j=1}^{n_{i}} t_{i j m} S_{i j m}\right]$ $m=1,2, \cdots, M$ (3)
2.4. Constraint conditions
(1) Constraint of sequence
Each process R_{ij} should start after the last one R_{i}_{(j1)} has been completed, and the mathematical description is as follow:
$\sum_{m=1}^{M} b_{i j m} S_{i j m} \geq \sum_{m=1}^{M}\left[\left(b_{i(j1) m} t_{i(j1) m}\right)\right] S_{i(j1) m}$ (4)
In equation (4), S_{ijm}=S_{i}_{(j1)m}=1.
(2) Constraint of machine
Only one process can be processed on the same machine at the same moment, that is there is R_{ij} at moment t (t>0), if $\exists S_{i j m}=1$ , then S_{xym}=1will not set up ( $i=x, j \neq y$ ).
(3) Constraint of continuity
R_{ij} cannot be interrupted after being processed:
$C_{i j m}=\left\{\begin{array}{ll}{\max \left\{C_{i(j1) m}, b_{i j m}\right\}+t_{i j m},} & {j>1} \\ {b_{i j m}+t_{j m},} & {j=1}\end{array}\right.$ (5)
2.5. The improved algorithm of IBFOA
FJSP is one kind of strong NP hard combinatorial optimization problems. The high dimension variables and complex constraints expand the solution space. According to the characteristics of FJSP, this paper proposes an improved differential evolution algorithm based on bacterial foraging optimization.
(1) IBFOA
$\theta^{i}(k, j, l) :$ the position of the $i^{\text {th }}$ bacteria in the $k^{\text {th }}$ chemokine, the $j^{\text {th }}$ replication and the $l^{\text {th }}$ elimination $\lambda(i)$ the step of chemotaxis, $\varphi(i) :$ the direction vector of unit length, $\Delta(i) :$ the random vector, $\delta \in(0,1) :$ the crowding distance factor, $f_{\lambda} f_{\lambda} f_{\lambda} :$ the step adjustment factor, N_{c }:the number of chemotaxis, P_{s}: population size, d: the crowding distance, d=( N_{c }/P_{s}), I: the length of the search interval.
The innovation of IBFOA in this paper is as follows: (1) In order to avoid limiting the convergence, the variable step length strategy based on crowding distance is proposed in IBFOA. (2) In order to find out the local optimal position fully the multiple chemotaxis is implemented, that is, on the basis of the common individual turn, the optimal individual will carry out additional tumbling. (3) Normal individuals swim to the direction of the optimal ones to improve the search efficiency of the algorithm. The specific steps of the improved algorithm are as follows:
1) Initialization
Determine the parameter of individual bacteria, such as position, position size, the number of chemotaxis, reproductive and elimination. Build the mapping relationship between FJSP and IBFOA and use the encoding way based on working procedure. The problem of 3 workpiece $\times 4$ machine is shown in Table 1, and the number is t_{ijm}.
Table 1. Example for 3 $\times 4$
workpiece 
process 
machine 

M_{1} 
M_{2} 
M_{3} 
M_{4} 

O_{1} 
R_{11} 
4 
 
3 
3 
R_{12} 
5 
4 
 
6 

R_{13} 
3 
4 
3 
5 

O_{2} 
R_{21} 
 
8 
8 
9 
R_{22} 
3 
3 
 
 

O_{3} 
R_{31} 
4 
 
3 
3 
R_{32} 
5 
8 
8 
6 

R_{33} 
9 
8 
 
26 
2) Chemotaxis
a. Firstly, the unit vector is generated and the individual bacteria start to turn and swim according to the step size. In which, the position of the i^{th} bacteria is updated as Equation (6):
$\theta^{i}(k+1, j, l)=\theta^{i}(k, j, l)+\lambda(i) \varphi(i)$ (6)
$\varphi(i)=\frac{\Delta(i)}{\sqrt{\Delta^{T}(i) \Delta(i)}}$ (7)
The notations in equation (6) and equation (7) are as mentioned above.
In this paper, $\lambda(i)$ is improved adaptively. The equation of adjustable step is as follow:
$\lambda(i)=f_{\lambda}\left[\frac{\delta(\delta+1)}{\delta+d}\delta\right] I$ (8)
In equation (8), if d is smaller, the individual will optimize in larger step; otherwise, the individual will optimize in a smaller step. That can ensure the algorithm has strong global search ability in early and strong local search ability in the latter.
b. Next, the bacterial community turns to update its position using approach of local searching. If the bacterial individual mapping to the multiobjective FJSP in Table 1 is “3 1 3 2 1 1 2 3” and select two point of p1 and p2 randomly, then the region between p1 and p2 of “3 2 1 1” will be stable and the information out of it will generate randomly, that is “2 3 3 2 1 1 3 1”. Compare the adaptive value of bacterial individuals before and after turning, if the fitness value appears to be backward, it is a non rational behavior.
After turning, the bacterial individuals with high adaptive value will obtain additional turning opportunities to search for more solutions in the neighborhood. The additional turning of the optimal individual is as follow: if the processing sequence is “3 1 2” before turning, the sequence will be retained as “3 1 2”.
After the local search of the optimal individual is completed, the common one may swim in the direction of the optimal one to absorb its positional information. If its value is “1”, the corresponding position will become “1”, and the original information of “3” will replace to the first position of “1”.
Offspring is selected through nondominated sorting based on Pareto and crowding distance.
The nondominated sorting achieves the classification through calculating the parameter X_{N} and X_{n} of population P_{s}, the specific steps are as follows:
Step 1: Initialize the parameter X_{N} as Ø;
Step 2: Initialize the variable X_{n}, where X_{n }is the number of individuals to dominate X;
Step 3: Calculate the dominance relationship between $X$ and $Y, X, Y \in P_{s} .$ If $Y$ is dominated by $X,$ then $X_{N}=X_{N} \cup\{Y\},$ otherwise, $X_{n}=X_{n}+1 .$ When $X_{n}=0, X$ is considered to be nondominated individuals, it is marked as $X_{k}=1,$ then $R_{1}=R_{1} U\{X\}$
Step 4: If $R_{i} \neq \emptyset$ then Q=Ø and set i=1. If $Y \in X_{N}$ , set y_{n}= y_{n} 1 until y_{n} =0, then set Y_{r}=i+1, $Q=Q \cup\{Y\}$ , R_{i}=Q;
Step 5: Calculation will stop if R_{i} is empty, otherwise, turn to Step 4.
3) Reproduction
If one bacterial individual absorbs enough nutrients to reproduce in the process of swimming, it will reach reproduction threshold. On the contrary, if the bacterial individual does not absorb enough nutrients, it will reach death threshold. Then the nutrient absorbed by the bacterial individual is calculated, and the excellent individuals in reproduction threshold will be copied until it reaches the predetermined times, go to (4), otherwise go to (2). Then the bacteria may be sequenced according to its adaptive value, which maps to the objective function in FJSP.
4) Elimination
Stop the algorithm if the bacteria colony has reach the predetermined times for elimination,
3.1. Testing on kacem instance
Table 2. The result of Kacem instance with three algorithms
workpiece $\times$ machine 
objective value 
BFOA 
HBCA 
IBFOA 

Su_{1} 
Su_{2} 
Su_{1} 
Su_{2} 
Su_{ 3} 
Su_{ 1} 
Su_{ 2} 
Su_{ 3} 
Su _{4} 

4 $\times$ 5 
T_{x} 
11 

11 
12 
13 
11 
11 
12 
11 

M_{t} 
31 

31 
31 
32 
31 
30 
31 
31 

M_{x} 
9 

10 
8 
7 
9 
8 
8 
8 
8 $\times$ 8 
T_{x} 
15 
15 
14 
15 
15 
14 
15 
14 
14 

M_{t} 
76 
75 
76 
75 
73 
75 
75 
73 
74 

M_{x} 
12 
12 
12 
12 
13 
12 
12 
12 
11 
10 $\times$ 7 
T_{x} 


12 
11 
12 
12 
11 
11 


M_{t} 


61 
62 
60 
60 
61 
60 


M_{x} 


11 
11 
12 
11 
10 
12 

10 $\times$ 10 
T_{x} 
7 

7 
6 
7 
7 
6 
7 
6 

M_{t} 
43 

41 
42 
41 
41 
42 
41 
41 

M_{x} 
6 

6 
5 
5 
6 
5 
5 
6 
In order to verify the efficiency of the proposed method, this paper solved the classic four standard problems of Kacem (4 workpieces $\times$ 5 machines, 8 workpieces $\times$ 8 machines, 10 workpieces $\times$ 7 machines, 10 workpieces $\times$ 10 machines) by IBFOA, in which the objective was f_{1}, f_{2} and f_{3}. The comparison with BFOA, Hybrid bee colony algorithm (HBCA) is shown in Table 2. It can be seen that IBFOA can not only obtain more nondominated solutions but obtain the current optimal solution in Table 2. For case 10 $x$ 7, although both HBCA and IBFOA have obtained three nondominated solutions, the solution (12, 61, 11) obtained by HBCA is dominated by both (12, 60, 11) and (11, 61, 10) obtained by IBFOA, the solution (12, 60, 12) obtained by HBCA is dominated by (11, 61, 10) obtained by IBFOA, the solution (12, 60, 12) obtained by HBCA is dominated by both (12, 60, 11) and (11, 60, 12) obtained by IBFOA. The above can indicate that IBFOA is more effective than the existing algorithms.
In Table 2, Su_{n }(n=1, 2, 3, 4) is the different solution; T_{x} is the makespan of a certain process; M_{t} is the total load of machines; M_{x} is the maximum load of single machine.
3.2. Testing on benchmark
Table 3. The comparison of different algorithms for Benchmark
example 
workpiece $\times$ machine 
Sol_{b} 
IBFOA 
HBCA 
BBEA 
MSIM 


T 
Tx 
C_{mr}(%) 
Tx 
C_{mr}(%) 
Tx 
C_{mr}(%) 

Mk01 
10 $\times$ 6 
36 
37 
40 
8.1 
39 
5.4 
38 
2.7 
Mk02 
10 $\times$ 6 
24 
24 
26 
8.3 
25 
4.2 
24 
0 
Mk03 
15 $\times$ 8 
204 
204 
204 
0 
204 
0 
204 
0 
Mk04 
15 $\times$ 8 
48 
55 
60 
9.1 
60 
9.1 
54 
1.8 
Mk05 
15 $\times$ 4 
168 
169 
173 
2.4 
172 
1.8 
171 
1.2 
Mk06 
10 $\times$ 15 
33 
50 
63 
26 
58 
16.0 
56 
12.0 
Mk07 
20 $\times$ 5 
133 
133 
140 
5.3 
138 
3.8 
136 
2.3 
Mk08 
20$\times$ 10 
523 
523 
523 
0 
523 
0 
523 
0 
Mk09 
20 $\times$ 10 
299 
306 
312 
2.0 
310 
1.3 
308 
0.65 
Mk10 
20 $\times$ 15 
165 
169 
194 
14.8 
198 
17.2 
175 
3.6 
In order to further verify the performance of IBFOA, this paper applied it to the Benchmark case and complied it with the HBCA algorithm, BBEA (bipopulation based estimation algorithm) and MSIM (machine selection initialization method) [9]. Sol_{b} in Table 3 is the known optimal solution. It can be seen from Table 3 that the optimal solution has been obtained for four times in ten cases with the IBFOA. Except example Mk04, it has obtained a better or equal solution than other three algorithms in the other nine cases. “C_{mr}” is the improvement rate of IBFOA comparing with other algorithms, T and T_{x} are shown in Table 3.
$C_{m r}=\frac{T_{x}T}{T} \times 100 \%$ (11)
The average of C_{mr} is 7.6%, 5.9% and 2.05% respectively.
IBFOA based on differential evolution is proposed in this paper, and the algorithm includes chemotaxis, reproduction and elimination. The MAGTD is introduced when the adaptive variable step adjustment strategy is adopted to select the optimal solution, the following conclusion may be got:
(1) The IBFOA has goodly global and local ability and can obtain more nondominated solutions than other algorithms;
(2) The IBFOA can obtain the optimal solution more quickly than other algorithms and the efficiency of algorithm is improved;
(3) The feasibility of the algorithm and its strong ability of solving can be verified through the benchmark;
(4) The introduction of MAGTD guarantees the selection of the most satisfactory scheduling scheme of FJSP in actual production.
However, the proposed research has not considered the influence of the subjective preference of decision makers on the final scheduling results, which may make the following research have more practical value. Therefore, the future development paths should be adding the analysis of subjective factor with some advanced approach such as cloud computing technology.
This work is financially supported by Dr scientific research fund of Liaoning Province (No. 20170520229, 20180550499), and Social Science planning fund of Liaoning Province (L18BGL018, 2018lslktyb016).
Demir Y., İşleyen S. K. (2014). An effective genetic algorithm for flexible jobshop scheduling with overlapping in operations. International Journal of Production Research, Vol. 52, No. 13, pp. 3905. https://doi.org/10.1080/00207543.2014.889328
Geyik F., Dosdoğru A. T. (2013). Process plan and part routing optimization in a dynamic flexible job shop scheduling environment: An optimization via simulation approach. Neural Computing & Applications, Vol. 23, No. 6, pp. 1631. https://doi.org/10.1007/s0052101211191127
Hao X., Lin L., Gen M., Ohno K. (2013). Effective estimation of distribution algorithm for stochastic job shop scheduling problem. Procedia Computer Science, Vol. 20, No. 1, pp. 102. https://doi.org/10.1016/j.procs.2013.09.246
Ju Q. Y., Zhu J. Y. (2007). Multiobjective flexible Job Shop scheduling of batch production. Chinese Journal of Mechanical Engineering, Vol. 43, No. 8, pp. 148154. https://doi.org/10.21474/IJAR01/6308
Liu X. B., Jiao X., Ning T. (2015). Improved method of flexible job shop scheduling based on double chains quantum genetic algorithm. Computer Integrated Manufacturing Systems, Vol. 21, No. 2, pp. 495502. https://doi.org/10.16356/j.1005 2615.2017.06.004
Mahmood M., Mostafa T., Najafi R. M. (2017). Kinematic analysis and design of a 3DOF translational parallel robot. International Journal of Automation and Computing, Vol. 14, No. 4, pp. 432441. https://doi.org/10.1142/S0217984918401127
Moslehi G., Mahnam M. (2011). A pareto approach to multiobjective flexible jobshop scheduling problem using particle swarm optimization and local search. International Journal of Production Economics, Vol. 129, No. 1, pp. 1422. https://doi.org/10.1016/j.ijpe.2010.08.004
Ning T., An S. Y., Li X. X. (2016). Triaxial models description of the lowlying properties in 192Os. International Journal of Modern Physics E, Vol. 25, pp. 237. https://doi.org/10.1142/S021830131650083X
Ning T., Huang M., Liang X. (2016). A novel dynamic scheduling strategy for solving flexible jobshop problems. Journal of Ambient Intelligence and Humanized Computing, Vol. 7, pp. 721729. https://doi.org/10.1007/s1265201603707
Prakash S., Vidyarthi D. P. (2014). A hybrid GABFO scheduling for optimal makespan in computational grid. International Journal of Applied Evolutionary Computation, Vol. 5, pp. 167174. https://doi.org/10.4018/ijaec.2014070104
Teekeng W., Thammano A. (2012). Modified genetic algorithm for flexible jobshop scheduling problems. Procedia Computer Science, Vol. 12, pp. 122. https://doi.org/10.1016/j.procs.2012.09.041
Vijaychakaravarthy G., Marimuthu S., Naveen S. A. (2014). Comparison of improved sheep flock heredity algorithm and artificial bee colony algorithm for lot streaming in mmachine flow shop scheduling. Arabian Journal for Science and Engineering, Vol. 39, pp. 42854300. https://doi.org/10.1007/s133690140994x
Wu X. L., Sun S. D., Yu J. J. (2006). Research on multiobjective optimization for flexible Job Shop scheduling. Computer Integrated Manufacturing System, Vol. 12, No. 5, pp. 731736. https://doi.org/10.1016/S18722040(06)600297