[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

本文一共[544]字,预计阅读时长:1分钟~
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 :
 Insert picture description here
NSGA: Non dominated sorting genetic algorithm (Non-dominated Sorting Genetic Algorithm)

 Insert picture description here

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 :
 Insert picture description here
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 :
 Insert picture description here
Pseudo code :
 Insert picture description here
 Insert picture description here
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 .
 Insert picture description here
Congestion can be calculated in many ways

1. Directly calculate the side length of the box
 Insert picture description here
2. It needs to be divided by …
 Insert picture description here
Congestion comparison operator :
 Insert picture description here
The main program :
 Insert picture description here
Elite strategy :
 Insert picture description here
 Insert picture description here
NSGA-II Program flow chart
 Insert picture description here
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_mac;% Load workshop equipment information
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_load=cal_equ_load(part_t);
t_cons=cal_ene_consu(Mac,mac_t,P,M,c_time);
pro_matrix(i,:)=[P,c_time,d_time,t_load,t_cons];
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_load=cal_equ_load(part_t);
t_cons=cal_ene_consu(Mac,mac_t,P,M,c_time);
pro_matrix(j,:)=[P,c_time,d_time,t_load,t_cons];
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.

3、 ... and 、 Running results

 Insert picture description here

Four 、 remarks

edition :2014a

版权声明:本文为[Matlab scientific research]所创,转载请带上原文链接,感谢。 https://car.inotgo.com/2021/08/20210810091259263s.html