【车间调度】基于matlab nsgaII算法求解车间调度问题【含Matlab源码 071期】

Matlab科研 2021-08-10 09:13:18 阅读数:393

本文一共[544]字,预计阅读时长:1分钟~
MATLAB 快速排序 排序算法 迭代 最优解

一、简介

作业车间调度问题描述
作业车间调度问题(Job Shop Scheduling, JSP)是最经典的几个NP-hard问题之一。其应用领域极其广泛,涉及航母调度,机场飞机调度,港口码头货船调度,汽车加工流水线等。

JSP问题描述:一个加工系统有M台机器,要求加工N个作业,其中,作业i包含工序数为Li。令,则L为任务集的总工序数。其中,各工序的加工时间已确定,并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序,约束条件被满足的同时,使性能指标得到优化。

作业车间调度需要考虑如下约束:

Cons1:每道工序在指定的机器上加工,且必须在其前一道工序加工完成后才能开始加工;

Cons2:某一时刻1台机器只能加工1个作业;

Cons3:每个作业只能在1台机器上加工1次;

Cons4:各作业的工序顺序和加工时间已知,不随加工排序的改变而改变。

问题实例
下面给出作业车间调度问题的一个实例,其中每个工序上标注有一对数值(m,p),其中,m表示当前工序必须在第m台机器上进行加工,p表示第m台机器加工当前工序所需要的加工时间。(注:机器和作业的编号从0开始)
jop0=[(0,3),(1,2),(2,2)]
jop1=[(0,2),(2,1),(1,4)]
jop2=[(1,4),(2,3)]
在这个例子中,作业jop0有3道工序:它的第1道工序上标注有(0,3),其表示第1道工序必须在第0台机器上进行加工,且需要3个单位的加工时间;它的第2道工序上标注有(1,2),其表示第2道工序必须在第1台机器上进行加工,且需要2个单位的加工时间;余下的同理。总的来说,这个实例中共有8道工序。
该问题的一个可行解是L=8道工序开始时间的一个排列,且满足问题的约束。下图给出了一个可行解(注:该解不是最优解)的示例:
在这里插入图片描述
NSGA:非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm)

在这里插入图片描述

种群分层:

Tips:此处存在重复对比情况,即X1 与 X2 进行了两次对比

虚拟适应度:目标函数值

共享小生境技术:
在这里插入图片描述
同一小生境内的种群,适应度互相减小。相似度高的、小生境内个体多的种群适应度减少程度更大。

通过这样的方式可以保证非支配层的每个个体拥有不同的适应度值。(这个没有懂)

NSGA-II:带精英策略的非支配排序遗传算法

快速非支配排序算法:
在这里插入图片描述
伪代码:
在这里插入图片描述
在这里插入图片描述
如图,D点被A和C点支配,所以D点的np为2,A点支配D和E,所以A点的Sp={D,E}。

该排序算法分级与NSGA中的结果不一样

拥挤度和拥挤度比较算子

密度估计:根据每一目标函数计算该点两侧的两个点的平均距离,该值作为以最近邻居作为顶点的长方体周长的估计(作为拥挤系数)。如下图,第i个解的拥挤系数为他周围长方体的长度(虚线表示)。

计算拥挤系数需要对每一目标函数进行排序。

每个非支配层的边界的个体拥挤度为无穷。
在这里插入图片描述
拥挤度有多种计算方式

1.直接计算长方体边长
在这里插入图片描述
2.需要除以…
在这里插入图片描述
拥挤度比较算子:
在这里插入图片描述
主程序:
在这里插入图片描述
精英策略:
在这里插入图片描述
在这里插入图片描述
NSGA-II 程序流程图
在这里插入图片描述
需要输入的变量是:规模N、迭代次数

二、源代码

%主函数
clear all;
clc;
pop = 200; %种群数量
gen = 10; %迭代次数
pop_f=100;%父代种群数量
data_mac;%载入车间设备信息
data_pro;%载入待加工工件信息
pro_matrix=[];%包含工序及目标函数值得决策矩阵
mac_matrix=[];%包含设备染色体信息的决策矩阵
for i=1:pop_f%生成初始种群
[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() 四舍五入取整 交配池大小
tour = 2;%竞标赛 参赛选手个数
[p_matrix,m_matrix]= non_domination_sort_mod(pro_matrix,mac_matrix);%种群进行非支配快速排序和拥挤度计算
clear pro_matrix;
clear mac_matrix;
[p_parent_chromosome,m_parent_chromosome] = tournament_selection(p_matrix,m_matrix,pool,tour);%竞标赛选择适合繁殖的父代
%交叉变异生成子代种群
[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));%保留精英染色体到子代种群中
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,:);%选取第一个作为最优解,可根据需求,选择AHP和熵权法或模糊决策法,选出最优解
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.

三、运行结果

在这里插入图片描述

四、备注

版本:2014a

版权声明:本文为[Matlab科研]所创,转载请带上原文链接,感谢。 https://blog.51cto.com/u_15324424/3328553