Self-adaptive multi-objective evolutionary algorithm for flexible job shop scheduling with fuzzy pro

article

R. Li, W. Gong (corresponding author), C. Lu(corresponding author), Self-adaptive multi-objective evolutionary algorithm for flexible job shop scheduling with fuzzy processing time, Computers & Industrial Enginering. 2022, 168, 108099 .( The division of the Chinese Academy of Sciences T2,IF 5.431).
DOI
The article links
Matalb sourcecode

Research background

Mainly in the current intelligent manufacturing , Energy efficiency has become the focus of research a few years ago . And flexible workshop is a classic academic branch . In addition, in the manufacturing process , Uncertainty of processing time , One direction is to use fuzzy flexible machining time to predict time constraints .

Research questions

This paper studies the multi-objective fuzzy flexible job shop scheduling problem , Processing time is expressed by triangular fuzzy numbers , Then optimize the maximum and minimum completion time and the maximum machine load at the same time . Because I think energy consumption is related to machine load . But in fact, there are more mature expressions . It was the first semester of Graduate School , Lack of thinking .

The fuzzy flexible job shop scheduling problem consists of two subproblems ： Determine the processing sequence of a process and select a processing machine for each process . In addition, it has the following characteristics ： Altogether N Pieces , Each workpiece has Ni A process , All in all M Taiwan machine , Each process can be in M Subset M‘ Choose a processing machine , Each process Oij On the machine Mk The processing time of is a triangular fuzzy number .

Membership function of triangular fuzzy numbers .

Processing time is expressed by upper and lower bounds and center (t1,t2,t3).

Research motivation

In the multi-objective fuzzy flexible job shop scheduling problem , I found that the predecessors lack an effective distribution strategy for multi-objective optimization problems . There is also little research on multi-objective fuzzy flexible job shop scheduling problem . So I use multi-objective evolutionary algorithm based on decomposition (MOEA/D) solve . But during the experiment , It is found that the optimal parameters of different test sets are different . So I hope to make a parameter adaptive strategy , Let the algorithm automatically select neighborhoods of different sizes , To adapt to different test problems .

Research methods

Algorithm framework

First of all, population initialization . Secondly, calculate the fitness , Then initialize the reference line size and population size to Np, Then the roulette method is used to assign a neighborhood size to each individual in the population T, Then the population adoption MOEA/D The framework of cross variation and environmental selection , Finally, perform variable neighborhood search for each individual , And then according to section 6 Each step T Parameter the number of successful population updates , Come for each T Parameter reallocation roulette selection probability .

Encoding and decoding

The code is so long , The process sequence is $O_{3,1},O_{2,1},O_{1,1},O_{2,2},O_{1,2},O_{3,2},O_{1,3},O_{3,3},O_{2,3}.$ The machine selection is $M_1,M_3,M_2,M_2,M_2,M_3,M_2,M_2,M_1$. Finally, the process and machine selection are shown A corresponding . But in fact, when programming , The machine code is arranged according to the process $O_{1,1},O_{1,2},...,O_{1,N1},O_{2,1},O_{2,2},...,O_{2,N2},...,O_{N,1},...,O_{N,NN}.$ In order . It can be understood as a fixed table , But the data in each solution is different , So no matter in cross mutation , How the machine code value changes , And processes can correspond . There will be no infeasible solution .

Mixed initialization strategy

Two dispatch rules are adopted ：
Local processing time minimum rule (LS)： Each process chooses to be its own minimum processing time machine
Global machine workload minimum rule (GW)： Select the machine with the smallest machine load in the current scheduling environment for each operation

Hybrid strategy ： use LS and GW Produce separately Np/3 Sub populations of size （ Rounding down ）, The rest is filled with random initialization .

Cross variation and environmental selection

(a) It is the intersection of processes .(b) It's machine crossover .

Process variation ： Randomly select two gene exchanges on the process code .
Machine variation ： Select two processes randomly , They choose a new processing machine .

Environmental choice ： use MOEA/D Aggregate function of , This can balance convergence and distribution .

The aggregate function value is , Currently assigned reference vector , Multiply each dimension by , The absolute value of the difference between the current objective function value and the reference point . Each dimension of the reference point is the minimum value of each objective function . Then select the direction with the largest descent space in each one-dimensional projection as the aggregation function value .

Variable neighborhood local search

Five local search operators are designed to improve the convergence .
LS1： Find... In the current sequence , The last process to be processed , Replace its machine .
LS2： Select a process randomly , Then change its machine .
LS3： Find the machine with the largest load on the current machine , Move a randomly selected process on this machine to another machine .
LS4： Select two processes randomly , Exchange its position .
LS5： Select two processes randomly , Insert the next process in front of the previous process .

For each process , Perform variable neighborhood search , If LS1 If you succeed, jump out , Otherwise execution LS2, If LS2 If you succeed, you will jump out , Otherwise execution LS3, And so on , Until five LS It's all over .

Parameter adaptive selection

MOEA/D The performance of is affected by the neighborhood size T influence . So a parameter pool is set T = {T1, T2, …, Tn}.

Use roulette to assign one to each individual Ti. Then after this round of iteration , The number of successes and failures of the current parameter are accumulated and stored in a length of LP In the archive of . Set as 45.

At first LP Rounds , The selection probability of all parameters is 1/n, When evolutionary algebra exceeds LP, Then start counting the past LP The number of successes and failures of each parameter in the round . Get tired by column , Then the success rate of each parameter is the sum of success times divided by the sum of success times plus the sum of failure times . Finally, the success rate of all parameters is normalized . As the selection probability of each parameter in the next round . Then insert the statistics of the success times of the current round into the success memory , The statistics of failure times are inserted into the failure memory . And delete the first row of the two matrices .

experimental result

Experimental test sets and indicators

Selected from two classical fuzzy flexible job shop scheduling problems . You can download it on my homepage .
In addition, there are too few test problems , I choose the classic test example of flexible job shop scheduling problem Mk Test set , And use a certain strategy to make it fuzzy processing time . The specific method is mentioned in the text . Finally, the total is 23 A test question .

The experimental index is HV and GD also Spread.

Comparative experiments

Just post it Frideman test Result . I'm too tired to write. I'm lazy .
stay HV and GD On rank First of all , stay Spread On rank second .

HV Index convergence diagram

PF Front comparison chart .

stay Lei The fourth test set
Finally, the Gantt chart of the minimum completion time is drawn

summary

in general , The article is not well written , The quality still needs to be improved . Continue to refuel and make progress , Subsequently, relevant contents of workshop scheduling will be continuously updated . Will attach the code . Other codes can be downloaded on my personal homepage .