### [workshop scheduling] solve the workshop scheduling problem based on MATLAB nsgaii algorithm [including Matlab source code phase 071]

Matlab scientific research 2021-08-10 09:14:15 阅读数:931

workshop scheduling solve workshop scheduling

## One 、 brief introduction

Job shop scheduling problem description
Job shop scheduling problem （Job Shop Scheduling, JSP） Are some of the most classic NP-hard One of the problems . Its application fields are extremely wide , Involving aircraft carrier scheduling , Airport aircraft dispatch , Port terminal cargo ship dispatching , Automobile processing line, etc .

JSP Problem description ： A processing system has M Taiwan machine , Required processing N Homework , among , Homework i The number of operations included is Li. Make , be L Is the total work ordinal number of the task set . among , The processing time of each process has been determined , And each operation must be processed according to the sequence of processes . The task of scheduling is to arrange the processing scheduling and sorting of all jobs , While the constraints are met , Optimize the performance index .

Job shop scheduling needs to consider the following constraints :

Cons1： Each process is processed on the designated machine , And the processing can only be started after the previous process is completed ;

Cons2： At some point 1 This machine can only process 1 Homework ;

Cons3： Each job can only be in 1 On this machine 1 Time ;

Cons4： The process sequence and processing time of each operation are known , It does not change with the change of machining order .

Problem instance
An example of job shop scheduling problem is given below , Each process is marked with a pair of values （m,p）, among ,m Indicates that the current operation must be performed on the m Processing on a machine ,p It means the first one m The processing time required for this machine to process the current operation .（ notes ： The machine and job numbers are from 0 Start ）
jop0=[(0,3),(1,2),(2,2)]
jop1=[(0,2),(2,1),(1,4)]
jop2=[(1,4),(2,3)]
In this case , Homework jop0 Yes 3 Process ： It's the first 1 The process is marked with (0,3), It means the second 1 The next process must be in the 0 Processing on a machine , And we need 3 Unit processing time ; It's the first 2 The process is marked with (1,2), It means the second 2 The next process must be in the 1 Processing on a machine , And we need 2 Unit processing time ; The rest is the same . in general , In this case, there are 8 Process .
A feasible solution to this problem is L=8 An arrangement of the start time of a process , And satisfy the constraints of the problem . The following figure shows a feasible solution （ notes ： The solution is not the optimal solution ） An example of ：

NSGA： Non dominated sorting genetic algorithm (Non-dominated Sorting Genetic Algorithm)

Population stratification ：

Tips: There are repeated comparisons here , namely X1 And X2 Two comparisons were made

Virtual Fitness ： The value of the objective function

Shared niche technology ：

Populations within the same niche , Fitness decreases with each other . High similarity 、 The fitness of the population with more individuals in the niche decreases more .

In this way, we can ensure that each individual in the non dominated layer has different fitness values .（ I don't understand ）

NSGA-II： Non dominated sorting genetic algorithm with elite strategy

Fast non dominated sorting algorithm ：

Pseudo code ：

Pictured ,D Point quilt A and C Point domination , therefore D Dot np by 2,A Point domination D and E, therefore A Dot Sp={D,E}.

The sorting algorithm is hierarchical and NSGA The results are different

Crowding degree and crowding degree comparison operator

Density estimation ： Calculate the average distance between two points on both sides of the point according to each objective function , This value is used as an estimate of the perimeter of the box with the nearest neighbor as the vertex （ As the congestion factor ）. Here's the picture , The first i The crowding coefficient of a solution is the length of the cuboid around it （ The dotted line shows ）.

To calculate the congestion coefficient, each objective function needs to be sorted .

The individual crowding degree of the boundary of each non dominated layer is infinite .

Congestion can be calculated in many ways

1. Directly calculate the side length of the box

2. It needs to be divided by …

Congestion comparison operator ：

The main program ：

Elite strategy ：

NSGA-II Program flow chart

The variables to be entered are ： scale N、 The number of iterations

## Two 、 Source code

``````% The main function
clear all;
clc;
pop = 200; % Population number
gen = 10; % The number of iterations
pop_f=100;% Number of parent populations
data_pro;% Load workpiece information to be processed
pro_matrix=[];% Decision matrix including process and objective function value
mac_matrix=[];% Decision matrix containing equipment chromosome information
for i=1:pop_f% Generation of initial population
[P,M,N]=initPop(J);
[part_t,mac_t]=decode(J,P,M,N);
c_time=cal_comp_time(part_t);
d_time=cal_def_time(J,part_t);
t_cons=cal_ene_consu(Mac,mac_t,P,M,c_time);
mac_matrix(i,:)=M;
end
for i = 1 : gen
pool = round(pop/2);%round() Round to the nearest whole Mating pool size
tour = 2;% Bidding competition Number of contestants
[p_matrix,m_matrix]= non_domination_sort_mod(pro_matrix,mac_matrix);% The population is non dominated and the crowding degree is calculated
clear pro_matrix;
clear mac_matrix;
[p_parent_chromosome,m_parent_chromosome] = tournament_selection(p_matrix,m_matrix,pool,tour);% The competition selects suitable parents
% Cross mutation generates offspring population
[p_child_matrix,m_child_matrix]=genetic_operator(J,p_parent_chromosome,m_parent_chromosome);
% According to the total population of parent and child classes , Perform non dominated quick sort , Select the parent population of the next generation
for j=1:size(p_child_matrix,1)
P=p_child_matrix(j,:);
M=m_child_matrix(j,:);
N=machine_index(J,P,M);
[part_t,mac_t]=decode(J,P,M,N);
c_time=cal_comp_time(part_t);
d_time=cal_def_time(J,part_t);
t_cons=cal_ene_consu(Mac,mac_t,P,M,c_time);
mac_matrix(j,:)=M;
end
n_p_m=size(pro_matrix,1);
pro_matrix(n_p_m+1:n_p_m+10,:)=p_matrix(1:10,1:size(pro_matrix,2));% Retain elite chromosomes in offspring populations
mac_matrix(n_p_m+1:n_p_m+10,:)=m_matrix(1:10,:);
end
[p_matrix,m_matrix]= non_domination_sort_mod(pro_matrix,mac_matrix);
num_of_level_1=length(find(p_matrix(:,size(p_matrix,2)-1)==1));
target_p_matrix=p_matrix(1:num_of_level_1,:);
target_m_matrix=m_matrix(1:num_of_level_1,:);
best_p=target_p_matrix(1,:);% Choose the first as the optimal solution , According to the demand , choice AHP And entropy weight method or fuzzy decision method , Choose the optimal solution
best_m=target_m_matrix(1,:);
P=best_p(1:length(best_p)-6);
M=best_m;
N=machine_index(J,P,M);
[~,mac_t]=decode(J,P,M,N);
ganttChart1(J,best_p,M,mac_t);
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
```

edition ：2014a