The following is an example of the job-shop scheduling problem, where each process is marked with a pair of values (m, P), where M means that the current process must be processed on the MTH machine, and P means the processing time required by the MTH machine to process the current process. (Note: Machine and job numbers start from 0)

Jop0 = [(0, 3), (1, 2), (2)]

Jop1 = [(0, 2), (2, 1), (1, 4)]

Jop2 = [(1, 4), (2, 3)]

In this example, job JOP0 has three processes: its first process is labeled (0,3), which means that the first process must be processed on machine 0 and requires 3 units of processing time; Its second process is marked with (1,2), which means that the second process must be processed on the first machine, and requires 2 units of processing time; Same thing with the rest. In total, there are eight processes in this example.

A feasible solution of the problem is that L= a permutation of 8 process start times, which satisfies the constraints of the problem. Here is an example of a possible solution (note: this solution is not optimal) :

NSGA: Non-dominated Sorting Genetic Algorithm

Population stratification:

Tips: There is a double comparison here, where X1 and X2 are compared twice

Virtual fitness: objective function value

Shared niche technology:

The fitness of populations within the same small population decreased each other. The population with high similarity and many individuals in small population had a greater degree of fitness reduction.

In this way it is possible to ensure that each individual in the non-dominant layer has a different fitness value. (This does not understand)

Nsga-ii: Non-dominated sorting genetic algorithm with elite strategy

Fast non-dominated sorting algorithm:

Pseudo code:

As shown in the figure, point D is dominated by points A and C, so np of point D is 2, and point A dominates D and E, so Sp of point A ={D, E}.

The classification of the sorting algorithm is different from the results in NSGA

Crowding degree and crowding degree comparison operator

Density estimation: Calculate the average distance between two points on either side of the point according to each objective function. This value is used as the estimate of the cuboid circumference with the nearest neighbor as the vertex (as the crowding factor). In the figure below, the crowding coefficient of the ith solution is the length of the cuboid around it (dotted line).

Computing the crowding factor requires ordering each objective function.

The crowding of individuals on the boundary of each non-dominant layer is infinite.

Congestion can be calculated in several ways

1. Directly calculate the edge length of cuboid

2. Divide by….

Crowding comparison operator:

The main program:

Elite strategy:

Nsga-ii program flow chart

The variables to be entered are size N and number of iterations

Clear all; clc; pop = 200; % population gen = 10; Pop_f =100; % Number of parent population data_mac; % Load workshop equipment information data_pro; Pro_matrix =[]; Mac_matrix =[]; % Decision matrix containing device chromosome information for I =1: POP_f % generates 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 the mating pool size tour = 2; % Number of contestants in tournament [p_matrix,m_matrix]= non_domination_sort_mod(pro_matrix,mac_matrix); Clear Pro_matrix was used to calculate undominated quicksort and crowding degree. clear mac_matrix; [p_parent_chromosome,m_parent_chromosome] = tournament_selection(p_matrix,m_matrix,pool,tour); % selection of suitable reproductive parent % cross mutation to generate offspring population [P_child_matrix,m_child_matrix]=genetic_operator(J,p_parent_chromosome,m_parent_chromosome); % 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 chromosome to 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,:); Select the first one as the optimal solution, AHP and entropy weight method or fuzzy decision method can be selected according to the requirements, and 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);Copy the code

Complete code added QQ1575304183