关键词：
⛄ 一、 遗传算法简介
1 问题描述
假定一个加工系统有m台机器和n件工件，每个工件包含一道或多道工序,工件的加工顺序是确定的,但每个工件可能有几条可行的加工路线,即每道工序可在多台不同的机床上加工,工序的加工时间和加工费用随机床的性能不同而变化。作业调度的任务是确定机器上工序的加工顺序,使得某个性能指标(如最大流程时间)取得最优值。下面是针对该调度模型的假设:
(1)每台机床一次只能加工一个工件。
(2)工序一旦进行不能中断。
(3)假定工件之间具备相同的优先级。
(4)不同工件的工序之间没有先后约束。
(5)工序在某台机床的加工时间是确定的。
(6)在零时刻,所有的工件都可被加工。
2 算法描述
遗传算法（Genetic Algorithms）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密歇根大学的Holland教授为研究自然与人工系统的自适应行为而提出的一种算法。近年来，遗传算法从理论到实际都已取得了许多重要成果。基于遗传算法求解NP问题的研究也相当活跃，对于求解NP问题，遗传算法已显示出了巨大的优势。
传统遗传算法从一组随机产生的初始解(种群)开始搜索。种群中的每个个体是问题的一个解(染色体)，这些染色体在后续迭代中不断进化,称为遗传。在每一代中用“适值”来测量染色体的好坏。生成的下一代染色体,称为子代。后代是由前一代染色体通过交叉或者变异操作形成的，在子代的形成过程中,根据适值的大小选择部分后代,淘汰部分后代,始终保持种群的大小是常数。适值高的染色体被选中的概率较高,体现了“适者生存”的进化机制。这样,经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解。
(1）编码
每个染色体编码为双链，第一条链为优先分配规则的序列，第二条链表示每个工件的每个工序所使用的资源。在第一条链中只记录工件号，其中工件号可以重复，其重复数为此工件的工序数。至于工件的工序号是由工件号在第一条链中相对本工件号的位置决定的。比如工件号2在第一条链中第2次出现，那么它就代表工件2的第2道工序。在第二条链中只记录设备号，如果没有使用设备就记录为0，其记录规则是根据工件号和工件的工序号的先后顺序记录工序所使用的设备号。即，首先记录工件1第1道工序所使用的设备号，接着记录工件1第2道工序所使用的设备号，直到最后记录工件n第m道工序所使用的设备号。因为对于每一道工序染色体都要记录它选择的资源，因此染色体是一个二维数组，它的长度是每个工件工序数之和。
例1：现有3个工件，它们的工序数分别是3,2,4，其中第1个工件的第1,2道工序分别有邀1妖，邀1,2,3妖可利用资源，其中第3道工序不需要资源；第2个工件的第1,2道工序分别具有邀1,2妖，邀2,3妖可利用资源；第3个工件的第1,2,3,4道工序分别具有邀1妖，邀1,2,3妖，邀1,3妖，邀3妖可利用资源。此问题对应的染色体的长度为：3+2+4=9。
它的编码如图1。
图1 染色体1
这里第一条链的编码表示排产过程中优先分配规则进行设备调度的工序顺序：第1个工件的第1道工序、第2个工件的第1道工序、第1个工件的第2道工序、第3个工件的第1道工序、第3个工件的第2道工序、第2个工件的第2道工序、第3个工件的第3道工序、第1个工件的第3道工序、第3个工件的第4道工序。第二条链的编码表示排产过程中每道工序所使用的设备：第1个工件的第1道工序使用第1台设备、第1个工件的第2道工序使用第3台设备、第1个工件的第3道工序不使用设备、第2个工件的第1道工序使用第1台设备、第2个工件的第2道工序使用第3台设备、第3个工件的第1道工序使用第1台设备、第3个工件的第2道工序使用第2台设备、第3个工件的第3道工序使用第1台设备、第3个工件的第4道工序使用第3台设备。
(2）杂交设计
对于一般的染色体的基因由于相互之间不存在影响，具有正交性，所以通常的交叉运算只需在染色体中选定某一个或几个随机的交叉点进行交叉即可。而该文定义的染色体是双链，并且在第一条链中工件号出现的个数与第二条链中设备号的选择都存在约束，因此本算法采用一种改进的单亲演化算法来进行杂交。
此改进的单亲演化算法只对第一条链进行杂交，在杂交过程中第二条链保持不变。对于一个染色体的第一条链(R1、R2、．．．．．．、Rn)，首先随机的产生2个数s和t(0<s<t<n+1），然后把染色体第一条链中的Rs、．．．．．．、Rt片段进行翻转得到一个新的染色体。
⛄ 二、部分源代码
clc, clear, close all
load(‘usborder.mat’,‘x’,‘y’,‘xx’,‘yy’);
cities = 40;
locations = zeros(cities,2);
n = 1;
while (n <= cities)
xp = rand*1.5;
yp = rand;
if inpolygon(xp,yp,xx,yy)
locations(n,1) = xp;
locations(n,2) = yp;
n = n+1;
end
end
plot(locations(:,1),locations(:,2),‘bo’);
xlabel(‘城市的横坐标x’); ylabel(‘城市的纵坐标y’);
grid on
%% 计算城市距离
distances = zeros(cities);
for count1=1:cities
for count2=1:count1
x1 = locations(count1,1);
y1 = locations(count1,2);
x2 = locations(count2,1);
y2 = locations(count2,2);
distances(count1,count2)=sqrt((x1-x2)2+(y1-y2)2);
distances(count2,count1)=distances(count1,count2);
end
end
x1 = x
%% 定义目标函数
FitnessFcn = @(x) traveling_salesman_fitness(x,distances);
my_plot = @(options,state,flag) traveling_salesman_plot(options, …
state,flag,locations);
⛄ 三、运行结果
⛄ 四、 matlab版本及参考文献
1 matlab版本
2014a
2 参考文献
[1]彭翔,戴祝英.关于车间作业调度的组合优化算法[J].现代计算机(专业版). 2004,(05)
3 备注
简介此部分摘自互联网，仅供参考，若侵权，联系删除
优化调度基于matlab遗传算法求解孤岛型微电网（成本最低）调度优化问题含matlab源码1163期(代码片段)
...2遗传算法的特点和应用遗传算法是一类可用于复杂系统优化的具有鲁棒性 查看详情
优化调度基于matlab遗传和模拟退火算法求解码头泊位分配调度优化问题含matlab源码247期
一、遗传算法简介1引言2遗传算法理论2.1遗传算法的生物学基础2.2遗传算法的理论基础 查看详情
优化调度基于matlab遗传算法求解公交车调度排班优化问题含matlab源码2212期
...客流需求的前提下,尽量减少不必要的投入,这是个多目标优化问题。 查看详情
作业调度基于matlabgui遗传算法求解车间作业调度问题（获益最大）含matlab源码2025期
一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加工。... 查看详情
优化调度基于matlab改进的遗传算法求解风电场优化调度问题含matlab源码1245期(代码片段)
...规模MaxGen=1000;%遗传代数ChromLen=10;%编码长度N=16;%优化变量个数LLimits=0;%优化变量的下限HLimits=0.33;%优化变量的上限Chrom=round(rand(PopSize,N*ChromLen));%随机产生初始种群的染色体fork=1:MaxGenfors=1:PopSize%种群产生m=... 查看详情
优化调度基于matlab非支配排序遗传算法求解车辆充电调度优化问题含matlab源码2000期(代码片段)
一、遗传算法简介由于国内外人民的生活方式和电动汽车主要购买人群的不同，国内外关于车辆充电调度问题研究的侧重点也不尽相同。我国地大物博，人口众多，交通复杂。主要从以下方面研究：1、通过经济手... 查看详情
车间调度基于matlab遗传算法求解车间调度问题含matlab源码1396期(代码片段)
一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加... 查看详情
车间调度基于matlab遗传算法求解车间调度问题（含甘特图）含matlab源码2216期(代码片段)
⛄一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上... 查看详情
车间调度基于matlab改进的遗传算法求解车间调度问题含matlab源码h002期(代码片段)
一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加... 查看详情
matlab基于多层编码遗传算法的车间调度算法matlab优化算法十九(代码片段)
...遗传算法具有较强的问题求解能力，能够解决非线性优化问题。遗传算法中的每个染色体表示问题中的一个潜在最优解，对于简单的问题来说，染色体可以方便地表达问题的潜在解，然而，对于较为复杂的优... 查看详情
matlab基于多层编码遗传算法的车间调度算法matlab优化算法十九(代码片段)
...遗传算法具有较强的问题求解能力，能够解决非线性优化问题。遗传算法中的每个染色体表示问题中的一个潜在最优解，对于简单的问题来说，染色体可以方便地表达问题的潜在解，然而，对于较为复杂的优... 查看详情
车间调度基于matlab候鸟算法mbo求解柔性作业车间调度问题含matlab源码2354期
...于一台的机器上加工,其加工时间与所在机器有关.FJSP问题优化的目标是为工序分配适当的机器,排列各机器上工序间的加工顺序并计算其开始/完工时间,最终使系统某个或某些性能达到最优[1].对于这样的系统,存在一些基本的假设... 查看详情
详谈改进的遗传算法求解柔性作业车间调度问题论文
...lland教授于1975年提出的，是一种模拟自然进化过程的一种优化算法.由于传统的遗传算法存在着较大的缺陷，国内外学者已从不同角度对其进行了改进，本文对传统遗传算法的初始种群进行了改进，以提高初始解的质量. 1柔性... 查看详情
指派问题基于matlab遗传算法求解指派优化问题含matlab源码2292期
⛄一、遗传算法求解指派优化问题简介1遗传算法1.1遗传算法简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法,它是一种多学科融合交叉的产物。遗传算法通过合理的编码机制和... 查看详情
指派问题基于matlab遗传算法求解指派优化问题含matlab源码2292期
⛄一、遗传算法求解指派优化问题简介1遗传算法1.1遗传算法简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法,它是一种多学科融合交叉的产物。遗传算法通过合理的编码机制和... 查看详情
车间调度基于matlab帝国企鹅算法求解柔性车间调度问题含matlab源码1991期
一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加工。... 查看详情
优化调度基于matlab粒子群算法求解经济调度优化问题含matlab源码1489期
一、粒子群算法简介1引言自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣所在。生物学家CraigReynolds在1987年提出了一个非常有影响的鸟群聚集模型，在他的仿真中，每一个个体都遵循：避免与邻域个体相撞：匹配邻域... 查看详情
优化调度基于matlab帝国企鹅算法求解航空调度优化问题含matlab源码yxs001期
一、帝企鹅算法简介目前，关于帝企鹅算法在国内外研究较少，在中对该算法进行了分析，并且与常见的粒子群算法、萤火虫算法进行了对比分析.帝企鹅从事各种活动，如狩猎、群体觅食，是群居性动物.每当... 查看详情