温州专业建站,晋江市住房建设局网站,wordpress xrea,建网站的公司首选智投未来先做一个声明#xff1a;文章是由我的个人公众号中的推送直接复制粘贴而来#xff0c;因此对智能优化算法感兴趣的朋友#xff0c;可关注我的个人公众号#xff1a;启发式算法讨论。我会不定期在公众号里分享不同的智能优化算法#xff0c;经典的#xff0c;或者是近几年…先做一个声明文章是由我的个人公众号中的推送直接复制粘贴而来因此对智能优化算法感兴趣的朋友可关注我的个人公众号启发式算法讨论。我会不定期在公众号里分享不同的智能优化算法经典的或者是近几年提出的新型智能优化算法并附MATLAB代码。 主要参考资料
[1] 潘全科, 高亮, 李新宇. 流水车间调度及其优化算法[M]. 武汉: 华中科技大学出版社, 2013. 加工对象一旦进入加工就不能中断直到完成其所有操作这就是零等待。例如在钢铁生产的炼钢-连铸生产过程中为实现热送热装的生产方式减少钢液在空气中的温降希望钢液在加工过程中零等待。图1(a)所示为一个3×3的零等待流水车间调度问题甘特图。由于工件加工零等待要求当第一台机器加工完第一个工件时不能立即加工第二个工件同理第一台机器加工完第二个工件时也不能立即加工第三个工件。与图1(b)所示的置换流水车间调度相比工件2和工件3的开工时间有所滞后。因此零等待流水车间调度问题不同于一般的置换流水车间调度问题。 图1
这里讨论一下零等待流水车间调度问题(NWFSP)和零空闲流水车间调度问题(NIFSP)的区别NIFSP主要是针对机器而言机器一旦加工就不能空闲NWFSP主要是针对工件而言工件一旦开始被加工就不能等待。
01 问题描述 这里主要讨论以最大完工时间为优化目标的零等待流水车间调度问题(no-wait flow-shop scheduling problem, NWFSP)记为Fm|perm, no-wait|Cmax。研究表明m≥3时这类调度问题即为NP-Hard 问题。
NWFSP可描述为n个工件在m台机器上加工所有工件在各机器上的加工路线均相同。同时约定某一时刻一个工件只能在一台机器上加工一台机器在某一时刻只能加工一个工件同一工件在相邻两道工序之间没有等待时间。每个工件在每,道工序的加工时间已知问题是如何安排各工件的生产次序使得调度指标最小。 02 数学模型 以下内容截自推文开头提到的参考书籍潘老师的那本书。 03 加工性能指标计算 最大完成时间(Cmax)是研究零等待流水车间调度问题最常用的加工性能指标。这里只介绍Cmax的一种计算方法计算相邻工件之间的开工时间差其时间复杂度为O(nm)。以下内容截自推文开头提到的参考书籍潘老师的那本书。Cmax的其他计算方法也可以在这本书籍里查阅。 04 智能算法(GA、DBO等)编码方法 对于遗传算法(GA)因为其算法本身是离散的通过选择、交叉、变异产生下一代。因此一条染色体就代表一种调度方案。即工件的排序即是它的个体编码。例如10个工件的排序方案用MATLAB初始化GA的一个个体(一条染色体)就是
xrandperm(10);
效果如下所示 但是对于粒子群优化(PSO)、麻雀搜索算法(SSA)、蜣螂优化(DBO)等它们本身是针对连续优化问题提出的所以在编码时需要经过进一步的处理。与GA一样一个调度方案(工件排序)表示一个个体可以采用SPV规则将实数编码转成整数编码。例如10个工件的排序方案用MATLAB初始化DBO的一个个体(一条染色体)就是
jobNum10; % 工件数xunifrnd(0,1,[1 jobNum]); % 产生10个[0,1]之间随机数os 1:1:jobNum; % 产生从1到10的数列[~, up_index] sort(x); % 对x进行降序排序, 得到位置序列x os(up_index); % 按照位置序列排序工件, 得到一个调度方案
效果如下 此外与SPV规则相反Li等提出最大排序值法(Largest rank value, LRV)也是将连续值映射成离散排列常用的方法之一。如图2所示LRV将代表种群个体的一组连续值按降序排列生成一组工件排序。(参考文献[2] LI X, YIN M. An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure [J]. Advances in Engineering Software, 2013, 55(8): 10-31.) 图2 最大排序值法的表示方法
05 数值实验
这里对DBO求解NWFSP的效果进行简单测试调度问题算例选用Rec(21个)。最大迭代次数T设置为2000种群规模NP设为60。下面展示的结果都是算法随机运行一次得到的结果。
首先以Rec05(20工件×5机器为例)展示DBO随机运行一次的求解结果。图3绘制了种群每代的最优适宜度收敛曲线和平均适宜度收敛曲线 图3 DBO-NWFSP对于Rec05的收敛曲线
图4绘制了调度结果的甘特图 图4 DBO-NWFSP对于Rec05的甘特图
其次以Rec11(20工件×10机器为例)展示DBO随机运行一次的求解结果如图5和图6所示。 图5 DBO-NWFSP对于Rec11的收敛曲线 图6 DBO-NWFSP对于Rec11的甘特图
最后以Rec41(75工件×20机器为例)展示DBO随机运行一次的求解结果如图7和图8所示。 图7 DBO-NWFSP对于Rec41的收敛曲线 图8 DBO-NWFSP对于Rec41的甘特图 06 MATLAB代码 智能算法(GA、PSO、DE、GWO、SSA、DBO等)求解零等待流水车间调度问题(no-wait flow-shop scheduling problem, NWFSP)的MATLAB代码其中main.m是主函数直接运行即可以算法简称命名的.m算法代码gantt_chart.m用来绘制甘特图objective.m是目标函数即计算Makespanmethod.pdf用来说明Makespan的计算方法代码采用的是计算相邻工件之间开工时间差的方法Car.xlsx和Rec.xlsx是流水车间调度的两个经典测试集。 输出结果包括Makespan、工件排序、计算时间、最优适宜度收敛曲线、平均适宜度收敛曲线、甘特图。 这里选择了十种算法来求解NWFSP。主要是几种经典算法和几个近几年的高引算法。对应的MATLAB代码链接如下
遗传算法(GA)求解NWFSP关注公众号里面有链接差分进化(DE)求解NWFSP关注公众号里面有链接粒子群优化(PSO)求解NWFSP关注公众号里面有链接灰狼优化(GWO)求解NWFSP关注公众号里面有链接鲸鱼优化算法(WOA)求解NWFSP关注公众号里面有链接哈里斯鹰优化(HHO)求解NWFSP关注公众号里面有链接麻雀搜索算法(SSA)求解NWFSP关注公众号里面有链接非洲秃鹫优化算法(AVOA)求解NWFSP关注公众号里面有链接蜣螂优化(DBO)求解NWFSP关注公众号里面有链接星鸦优化算法(NOA)求解NWFSP关注公众号里面有链接以上十种智能优化算法(GA、DE、PSO、GWO、WOA、HHO、SSA、AVOA、DBO、NOA)求解NWFSP的全家桶关注公众号里面有链接 可通过下方链接下载代码清单在里面寻找需要的算法代码然后去对应的链接获取。清单会同步更新一旦有新的代码就可以在清单里找到。清单里面有部分代码是开源获取的。可随时免费下载。
链接https://pan.baidu.com/s/1SFDMplrL7tiqGZlrpOSGYg
提取码8023 此外欢迎添加算法交流群进行交流912369858
