An improved bacterial foraging optimization for multi-objective flexible job-shop scheduling problem

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(j-1) 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(j-1) m} t_{i(j-1) m}\right)\right] S_{i(j-1) m}$          (4)

In equation (4), S_ijm=S_i(j-1)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(j-1) 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$

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 multi-objective 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 non-dominated sorting based on Pareto and crowding distance.

The non-dominated 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 non-dominated 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,

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 non-dominated 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.