Disruption Management of Flexible Job Shop Scheduling Considering Behavior Perception and Machine Fault Based on Improved NSGA-II Algorithm

In the multispecies and middle and small batch customized production mode, the balance between production plan and operation plan is easy to be disturbed, and the original production scheduling plan cannot be implemented normally [1]. Flexible job shop scheduling problem (FJSP) is an extension of job shop scheduling problem (JSP), which reduces machine constraints, makes the search for feasible solutions more difficult [2], and is more in line with the scheduling practice of advanced manufacturing enterprises under the JIT thought. However, the flexible job shop scheduling is a typical human-machine synergy system, which combines the participants of the scheduling with the resource scheduling in the traditional operation management. The factors of people mainly include customers, manufacturers and workers in workshops, which have been paid more and more attention in reality [3]. At the same time, the production process is more susceptible to some interference events, such as machine failure, order production adjustment, process delay, raw material supply interruption, and so on, so that the initial scheduling plan cannot be implemented smoothly [4, 5].

The research on the problem of workshop scheduling interference is mainly focused on single machine, parallel machine, flow shop, job shop and open workshop environment. The classical job shop scheduling methods mainly include rescheduling [6], robust scheduling [7, 8], rightward shift scheduling [9] and AOR rescheduling [10, 11]. These methods can adjust the scheduling plan and enrich the job shop scheduling method. The interference management is not to optimize the state of the disturbance after the occurrence of the disturbance. By optimizing the initial scheme, the disruption management scheduling scheme is quickly generated which has the minimum disturbance effect on the system. Ding [12] used local rescheduling to deal with the interruption of all machine processing in the initial scheduling of JSP environment. Jiang [13] and Liu [6] dealt with interference events in single machine shop environment using lexicographical order multi-objective programming and rescheduling. Ayten et al. [14] realized disturbance measurement using integer programming method in parallel machine environment. Louis and Xu [15] dealt with the problem of machine fault interference and update interference in an open workshop using the rescheduling strategy of genetic algorithm. Aiming at the new workpiece arrival interference in job shop scheduling, Wang [16] and Wang [17] adopted the hybrid evolutionary algorithm of rescheduling and meta heuristic to deal with the interference.

The modeling method of job shop scheduling interference considering behavior is mainly based on the prospect theory and fuzzy mathematics. On the basis of prospect theory and fuzzy mathematics, the “limited rationality” of human is extracted. Ding [12] and Jiang [13] set up a lexicographical order multi-objective interference management model. Wang [17] established an interference management model considering the initial cost target and the disturbance target.

The solution of FJSP is mainly sought using the genetic algorithm and the non-dominated sorting algorithm. Chen et al. [18] proposed a hybrid genetic algorithm with bottlenecks, Chen [19] proposed a NSGA- II algorithm based on the variation of close relatives, and Wu [20], Wei [21] used the improved genetic algorithm to solve the flexible job shop scheduling problem.

At present, different types of job shop scheduling interference problems have been preliminarily studied, but researches on more complex job shop interference problems have not started yet. The measurement of the behavior perception of behavioral agent are mainly conducted using fuzzy mathematics and the diversified dissatisfaction measurement tools are lacking. Although NSGA-II is the mainstream algorithm for solving multi-objective optimization problems, it is easy to fall into local convergence.

Based on the above analysis, in this paper, under the flexible job shop environment, the single machine fault interference occurs during the initial scheduling execution process, and multi-agent behavior perception is considered. The unascertained theory is used to measure the dissatisfaction of different stakeholders, and the model of interference management is set up. The improved NSGA-II algorithm based on close relative crossover and mutation is applied to enhance the local search ability of the algorithm, and the elitist strategy is adopted to accelerate the optimization speed and finally the Pareto optimal solution set is obtained. Then, according to the importance of different stakeholders, the optimal solution of single machine fault FJSP is found.

Rescheduling after disturbances in flexible job shop scheduling will inevitably change the original scheduling plan, resulting in the tardiness of workpiece and the change of workpiece processing sequence and dissatisfaction of customers, manufacturers and workshop workers. People are in an irrational state [22], and the dissatisfaction of these agents in the job shop scheduling system will restrict the operation efficiency of the supply chain, or even lead to the breakdown of the cooperative relationship, which is also the key to the effective implementation of the shop scheduling theory in the actual production.

The prospect theory, based on the limited rationality of human, can describe the people’s behavior preference under different circumstances. The value function of the subject of behavior can be expressed as Eq. (1):

$V_{r}(x)=\left\{\begin{array}{c}{x^{\alpha_{r}}, x \geq 0} \\ {-\lambda_{r}(-x)^{\beta_{r}}, x<0}\end{array}\right.$           (1)

where, $x=\frac{x_{i}-x_{0}}{l}$, l is the maximum perturbation value, $l_{r}=\max \left(x_{i}-x_{0}\right), i=1,2, \ldots, n, x_{0}$, is the reference point, that is the minimum value of the behavior subject affected by the interference factor. $\alpha, \beta$ are the risk attitude coefficients, $a_{r}>0,0<\beta_{r}<1 . \lambda$ is the loss aversion coefficient, $\lambda>1$.

If the interference of machine failure occurs in the processing of the workshops, the losses to the manufacturers, customers and workshops are mainly reflected in the part of $x_{i}<O_{i}$. The value function can be transformed into Eq. (2) through deformation.

$\mu\left(x_{i}\right)=-V(-x)=\lambda_{r}\left(\frac{x_{i}-x_{0}}{l_{r}}\right)^{\beta_{r}}$           (2)

The unascertained theory is different from the theory of random and fuzzy [23, 24], which can judge and quantify items [25] in the case of incomplete information according to the prior knowledge. Unascertained mathematical theory has been widely used in economy, engineering, enterprise management, environmental evaluation and so on. Using unascertained mathematics to measure the dissatisfaction of the behavior subject, we can get the membership function of the dissatisfaction measure of the behavior subject.

3.1 Subordination function of dissatisfaction measure of different behavior subjects

According to the unascertained mathematics, the degree of dissatisfaction of behavioral subjects in the sense of unstrict measurement are measured, and the unascertained measure function $\mu_{r}$ of different behavior subjects based on prospect theory is constructed. The disturbance loss of different behavior subjects is transformed into the number between 0-1 by using the unascertained degree of membership. It shows the dissatisfaction of different agents. 1 indicates that the behavior subject is not satisfied, 0 indicates that the subject is satisfied. The dissatisfaction of the behavioral subject r to the evaluation object i is $\mu_{r}\left(x_{i}\right)$, and the subjection function of the dissatisfaction measure of the behavior subject is as follows Eq. (3), $R_{i}^{r}=t_{0}+l\left(\frac{1}{\lambda_{r}}\right)^{\frac{1}{\beta_{r}}}$. The measure function of the dissatisfaction of the behavior subject is shown in Figure 1.

$\mu_{r}(x)=\lambda_{r}\left(\frac{x_{i}-x_{0}}{l_{r}}\right)^{\beta_{r}}, x_{0} \leq x_{i} \leq R_{i}^{r}$         (3)

1.jpg

Figure 1. The subjection function of the dissatisfaction measure of the behavior subject

(1) The customer’s dissatisfaction is mainly determined by the tardiness of the work piece. The maximum tardiness time of the work-piece $l=\max \left(t_{i}-t_{i}^{0}\right), i=1,2, \ldots, n$. The completion time of the workpiece is $t_{i}$. $t_{i}^{0}$ is the original scheduling completion time of the workpiece i. Customer’s dissatisfaction with the scheduling is $\mu_{1}$. The measure of the customer’s dissatisfaction with the workpiece i is as follows:

$\mu_{1}^{\prime}\left(t_{i}\right)=\left\{\begin{array}{c}{1, \quad t_{i} \geq R_{i}^{1}} \\ {\lambda_{1}\left(\frac{t_{i}-t_{i}^{0}}{l}\right)^{\beta_{1}}, \quad t_{i}^{0} \leq t_{i}<R_{i}^{1}} \\ {0, \quad t_{i}<t_{i}^{0}}\end{array}\right.$        (4)

where, $R_{i}^{1}=t_{i}^{0}+l\left(\frac{1}{\lambda_{1}}\right)^{\frac{1}{\beta_{1}}}, \mu_{1}(t)=\frac{\sum_{i=1}^{n} \mu_{1}^{\prime}\left(x_{i}\right)}{n}$.

(2) The dissatisfaction of manufacturer is mainly influenced by the completion time of the work piece. The completion time of the original scheduling is $t_{0}$, and the average tardiness time of the new scheduling is $\Delta t=\frac{\sum_{i=1}^{n}\left(t_{i}-t_{i}^{0}\right)}{n}$. The manufacturer’s dissatisfaction measure is as follows:

$\mu_{2}(t)=\left\{\begin{array}{c}{1, \Delta t \geq R_{i}^{2}} \\ {\lambda_{2}\left(\frac{\Delta t}{l}\right)^{\beta_{2}}, \quad 0 \leq \Delta t<R_{i}^{2}}\end{array}\right.$     (5)

where, $R_{i}^{2}=l\left(\frac{1}{\lambda_{2}}\right)^{\frac{1}{\beta_{2}}}$.

(3) The dissatisfaction of the working workers in the workshop is mainly caused by the complex workshops. Employees are most concerned about the changes in the number of work-pieces on each machine in the new and old scheduling, that is, the number of disturbance processes. For example, the original machine 1, the need to carry 3 pieces of jobs, after the rescheduling of the need to carry 4 pieces of jobs, the number of disturbances on this machine is 1. The sum of the disturbances on all machines is the total number of perturbations $n_{a f f c e t e d}, n_{s u m}$ is the total number of processes.

$\mu_{3}\left(n_{a f f c e t e d}\right)=\left\{\begin{array}{c}{1, n_{a f f c e t e d} \geq R_{i}^{3}} \\ {\lambda_{3}\left(\frac{n_{a f f c e t e d}}{n_{s u m}}\right)^{\beta_{3}}, 0 \leq n_{a f f c e t e d}<R_{i}^{3}}\end{array}\right.$  (6)

where, $R_{i}^{3}=n_{\operatorname{sum}}\left(\frac{1}{\lambda_{3}}\right)^{\frac{1}{\beta_{3}}}$.

3.2 Construction of interference management model

(1) Parameter and Variable Description

n: Total number of pieces;

m: Total number of machines;

i: Machine serial number, $i=1,2,3, \dots, m$;

j,k: Work-piece sequence number, $j, k=1,2,3, \dots n$;

$h_{j}$: The total number of processes for the jth work piece, $h=1,2,3, \ldots, h_{j}$;

l: Working procedure serial number, $l=1,2,3, \ldots, h_{j}$;

$m_{j h}$: The number of optional processing machines in the hth process of the jth work piece;

$O_{j h}$: The hth process of the jth workpiece;

$M_{i j h}$: The hth process of the jth work-piece is processed on the machine i;

$p_{i j k}$: The processing time of the hth working procedure of the jth workpiece on the machine i;

$S_{j h}$: The time for the starting process of the hth process of the jth work piece;

$C_{j h}$: The processing completion time of the hth process of the jth work piece;

L: A enough large number;

$C_{j}$: The completion time of the workpiece j;

$C_{\max }$: The maximum completion time;

(2) Interference Management Model

$\min f_{1}=\mu_{1}(t)$        (7)

$\min f_{2}=\mu_{2}(t)$         (8)

$\min f_{3}=\mu_{3}\left(n_{a f f e c t e d}\right)$         (9)

s.t. $\quad s_{j h}+x_{i j h} p_{i j k} \leq c_{j h}$      (10)

$s_{j k}+x_{i j h} p_{i j h} \leq c_{j h},$ where $h=1,2,3, \dots, h_{j-1}$     (11)

$c_{j h} \leq S_{j(h+1)}$    (12)

$s_{j h}+p_{i j h} \leq s_{k l}+L\left(1-y_{i j h k l}\right)$             (13)

$c_{j h} \leq s_{j(h+1)}+L\left(1-y_{i k l j(h+1)}\right)$       (14)

$\sum_{i=1}^{m_{i h}} x_{i j h}=1$    (15)

$\sum_{j=1}^{n} \sum_{h=1}^{h_{j}} y_{i j h k l}=x_{i k l}$      (16)

$\sum_{k=1}^{n} \sum_{l=1}^{h_{k}} y_{i j h k l}=x_{i j h}$     (17)

$s_{i h} \geq 0, c_{j h} \geq 0$       (18)

where, $x_{i j h}=1$, if the procedure $O_{j h}$ is finished on machine i; otherwise, $x_{i j h}=0$. $y_{i j h k l}=1$, if the procedure $O_{i j h}$ is finished before the procedure $O_{i k l}$_, otherwise it is 0.

Eq. (7), (8) and (9) are the objective functions to express the dissatisfaction of the customers, the manufacturers and the labour workers of the workshops. Eq. (10) and (11) represent the process constraints to the workpiece. Eq. (12) indicates that a work procedure cannot be processed until the last work procedure is completed. Eq. (13) and (14) indicate that one machine can only process one workpiece at the same time. Eq. (15), (16) and (17) represent a machine repeatedly operates each working procedure. Eq. (18) indicates that the processing cannot be started until the workpiece arrives.

5.jpg

Figure 5. Initial Scheduling Scheme

Since there is no standard example for FJSP interference management, this paper takes 10×10 FJSP scheduling in literature [30] as an example. There are 10 workpieces and 10 machines, and the work process number for each workpiece is not necessarily equal. Each procedure can be implemented on multiple machines (the initial scheduling is as Figure 5). Process 201 represents the first process of workpiece 2, and 202 represents the second process of workpiece 2. After the initial execution of the original scheduling, machine 3 has a sudden failure at the timepoint of 1, and the fault processing requires 2 units of time. The occurrence of machine failure has a worsening effect on the processing of the subsequent process in the whole scheduling plan. The interference processing method is used to adjust the earliest available time of each workpiece, and the earliest available time of each machine is adjusted according to the interference management model. The risk attitude coefficient $\beta$ and the loss aversion coefficient λ of customers, manufacturers and workers used the typical values in literature [31], respectively. The algorithm is programmed on Matlab2015a, and the computer environment is the win10 system PC of Intel Core (TM) i5-2450 CPU2.50GHz with a Memory of 4GB. The size of the population is 100, and the maximum crossover probability of the evolutionary algebra 100 is 1. The minimum crossover probability is 0.3, the maximum mutation probability is 0.5, the minimum mutation probability is 0.01, and the mating pool size is 20.

5.1 Experimental result

In the process of evolution, the target value is constantly optimized. Figure 6 is the optimization of the dissatisfaction target value of workers, manufacturer and workshop workers. The table 1 is optimal solution to the final generation of Pareto.

6a.jpg

(a)The evolutionary process of the optimal value of the customer’s dissatisfaction

6b.jpg

(b)The evolutionary process of the optimal value of the manufacturer’s dissatisfaction

6c.jpg

(c)The evolutionary process of the optimal value of the workers’ dissatisfaction in the workshop

Figure 6. The evolutionary process of the best value of each objective function

Table 1. The optimal solution set to the final generation of Pareto

The algorithm finally gets the optimal solution set. According to the actual situation in production, the weight [19] of each target can be determined by AHP (analytic hierarchy process). This paper assumes that the target weights ω of $f_{1}$, $f_{2}$ and $f_{3}$ are 0.4, 0.4, and 0.2 respectively. Because the target value dimension has been unified, the comprehensive dissatisfaction $V_{i}$ is calculated directly as follow Eq. (21).

$V_{i}=\omega_{1} f_{1}+\omega_{2} f_{2}+\omega_{3} f_{3}$       (21)

According to the results of the calculation of $V_{i}$, the optimal solution is finally obtained. The Gantt diagram is shown in Figure 7 (a) below. The results are compared with the results of  rescheduling (Figure 7 (b)), right shift scheduling [6, 10] (Figure 7 (c)), and AOR rescheduling (Figure 7(d)). Table 2 is the comparison of the work completion time of the different scheduling methods (the italic and overstriking value is a tardiness piece). Table 3 is a contrast of dissatisfaction for different scheduling methods.

7a.jpg

(a) Optimal scheduling scheme for interference management

7b.jpg

(b) Rescheduling scheme

7c.jpg

(c) Complete right shift scheduling scheme

7d.jpg

(d) AOR rescheduling scheme

Figure 7. Comparison of scheduling schemes

Table 2. Comparison of work-pieces completion time under different scheduling methods

Table 3. Comparison of the results of different scheduling methods

5.2 Result analysis

For the scheduling results of rescheduling, fully right shift scheduling and AOR rescheduling, interference management scheduling can effectively reduce the comprehensive dissatisfaction of interference events to the whole manufacturing system. The reduction of disturbance to the manufacturing system by the disturbance management is mainly reflected in two aspects: the decrease of the number of the tardiness workpieces and the decrease of the total tardiness time.

(1) The number of the tardy work-pieces is reduced, so the customer’s dissatisfaction is reduced. As shown in Figure 7 (a), since the interference management method takes into account the interest demand of customers, there are only two delayed workpieces (workpiece 9 and workpiece 10) and parts of workpieces (workpieces 3) are completed ahead of schedule, which greatly reduces customer’s dissatisfaction. As in Figure 7 (b), rescheduling can minimize makespan, thus reducing the dissatisfaction of customers, manufacturers and workshop labors to a certain extent. But 3 work-pieces are delayed, and the overall dissatisfaction is high. As shown in Figure 7 (c), for the complete right shift scheduling, 10 workpieces are all delayed. The dissatisfaction of the customers and the manufacturers is the highest, which results in a greater degree of comprehensive dissatisfaction, while the dissatisfaction of the workers is the smallest. As in Figure 7 (d), AOR rescheduling has not delayed the completion time of partial workpieces because it pruned the unaffected process. There are 7 work-piece tardiness, and the manufacturers have the greatest degree of dissatisfaction, the customers’ dissatisfaction is reduced, and the workers’ dissatisfaction is the lowest.

(2) The total tardiness time is reduced, and the manufacturer’s dissatisfaction is reduced. The manufacturer’s benefit is determined by the total tardiness of the work piece, and the interference management takes into account the manufacturer’s requirements for different work periods. As a result, the total tardiness time is 8, and the total tardiness time of rescheduling, fully right shift scheduling and AOR rescheduling are 9, 20 and 14 respectively (Table 2).

In this paper, interference scheduling is based on the overall interests of the manufacturing system, and at the expense of the smaller interests of the laboring workers in the workshop, it achieves a significant decrease in the dissatisfaction of the customers and manufacturers, and balances the interests of the parties to the greatest extent, which is conducive to reducing the disturbance of the production system and improving the agility of the supply chain.