智能算法(GA、DBO等)求解阻塞流水车间调度问题(BFSP)

发布时间:2023年12月25日

先做一个声明:文章是由我的个人公众号中的推送直接复制粘贴而来,因此对智能优化算法感兴趣的朋友,可关注我的个人公众号:启发式算法讨论。我会不定期在公众号里分享不同的智能优化算法,经典的,或者是近几年提出的新型智能优化算法,并附MATLAB代码。

主要参考资料:

[1] 潘全科, 高亮, 李新宇. 流水车间调度及其优化算法[M]. 武汉: 华中科技大学出版社, 2013.

由于机器中间缓冲区或生产温度的限制,使得工件加工完成后被阻塞在当前机器上,这就是阻塞流水车间调度问题(blocking flow-shop scheduling problem, BFSP)。譬如,在化学制造过程中,由于温度的要求,当药品在上游机器上完成后,为了保持此时的高温,应立即离开当前的机器而转向下游机器。但是如果下游机器处于忙的状态,此时药品只能被阻塞在上游机器上。图1所示为一个3×3的BFSP的甘特图。当工件2在第一台机器上加工完毕时,机器2正在加工工件1。由于没有中间缓冲区,工件2工并不能立刻离开该机器,而是等到工件1加工完毕后才运输到机器2上加工。这样就造成了工件3延迟开工。

图片

图1 阻塞流水车间调度问题

01
问题描述

这里主要讨论以最大完工时间(Cmax)为优化目标的阻塞流水车间调度问题(blocking flow-shop scheduling problem, BFSP),记为Fm|blocking|Cmax。研究表明,m≥3时,这类调度问题也是NP-Hard 问题。

Fm|blocking|Cmax问题可描述为:有n个工件按照相同的工艺路线在m台机器上加工。约定所有机器上工件的加工次序都相同。要求相邻机器之间没有缓冲区。也就是说工件j在机器i上完成后,如果下一台机器i+1正在使用,那么工件j将被阻塞在机器i上,直到第i+1个机器空闲出来。一个工件不能同时由多台机器加工,一台机器也不能同时加工多个工件。已知工件在各机器上的加工时间。问题是如何安排各工件的生产次序,使得最大完成时间最小。

02
数学模型

(以下内容截自推文开头提到的参考书籍,潘老师的那本书。)

图片

图片

03
加工性能指标计算

最大完成时间(Cmax)是研究阻塞流水车间调度问题最常用的加工性能指标。Cmax通常有三种计算方法:前向计算法、反向计算法和双向计算法。

这里主要介绍前向计算法。(以下内容截自推文开头提到的参考书籍,潘老师的那本书。)其他计算方法也可以在这本书籍里查阅。

图片

图片

04
智能算法(GA、DBO等)编码方法

对于遗传算法(GA),因为其算法本身是离散的,通过选择、交叉、变异产生下一代。因此,一条染色体就代表一种调度方案。即工件的排序即是它的个体编码。例如,10个工件的排序方案,用MATLAB初始化GA的一个个体(一条染色体)就是:

x=randperm(10);

效果如下所示:

图片

但是对于粒子群优化(PSO)、麻雀搜索算法(SSA)、蜣螂优化(DBO)等,它们本身是针对连续优化问题提出的,所以在编码时需要经过进一步的处理。与GA一样,一个调度方案(工件排序)表示一个个体,可以采用SPV规则,将实数编码转成整数编码。例如,10个工件的排序方案,用MATLAB初始化DBO的一个个体(一条染色体)就是:

jobNum=10; %?工件数x=unifrnd(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求解BFSP的效果进行简单测试,调度问题算例选用Rec(21个)。最大迭代次数T设置为2000,种群规模NP设为60。下面展示的结果都是算法随机运行一次得到的结果。

首先,以Rec05(20工件×5机器为例),展示DBO随机运行一次的求解结果。图3绘制了种群每代的最优适宜度收敛曲线和平均适宜度收敛曲线:

图片

图3 DBO-BFSP对于Rec05的收敛曲线

图4绘制了调度结果的甘特图:

图片

图4 DBO-BFSP对于Rec05的甘特图

其次,以Rec11(20工件×10机器为例),展示DBO随机运行一次的求解结果,如图5和图6所示。

图片

图5 DBO-BFSP对于Rec11的收敛曲线

图片

图6 DBO-BFSP对于Rec11的甘特图

最后,以Rec41(75工件×20机器为例),展示DBO随机运行一次的求解结果,如图7和图8所示。

图片

图7 DBO-BFSP对于Rec41的收敛曲线

图片

图8 DBO-BFSP对于Rec41的甘特图

06
MATLAB代码

智能算法(GA、PSO、DE、GWO、SSA、DBO等)求解阻塞流水车间调度问题(blocking flow-shop scheduling problem, BFSP)的MATLAB代码,其中:main.m是主函数,直接运行即可;以算法简称命名的.m算法代码;gantt_chart.m用来绘制甘特图;objective.m是目标函数,即计算Makespan;method.pdf用来说明Makespan的计算方法,代码采用的是前向计算方法;Car.xlsx和Rec.xlsx是流水车间调度的两个经典测试集。

输出结果包括Makespan、工件排序、计算时间、最优适宜度收敛曲线、平均适宜度收敛曲线、甘特图。

博主挑选了十种算法来求解BFSP。主要是几种经典算法和几个近几年的高引算法。对应的MATLAB代码链接如下:

遗传算法(GA)求解BFSP关注公众号,里面有链接
差分进化(DE)求解BFSP关注公众号,里面有链接
粒子群优化(PSO)求解BFSP关注公众号,里面有链接
灰狼优化(GWO)求解BFSP关注公众号,里面有链接
鲸鱼优化算法(WOA)求解BFSP关注公众号,里面有链接
哈里斯鹰优化(HHO)求解BFSP关注公众号,里面有链接
麻雀搜索算法(SSA)求解BFSP关注公众号,里面有链接
非洲秃鹫优化算法(AVOA)求解BFSP关注公众号,里面有链接
蜣螂优化(DBO)求解BFSP关注公众号,里面有链接
星鸦优化算法(NOA)求解BFSP关注公众号,里面有链接
以上十种智能优化算法(GA、DE、PSO、GWO、WOA、HHO、SSA、AVOA、DBO、NOA)求解BFSP的全家桶关注公众号,里面有链接

可通过下方链接下载代码清单,在里面寻找需要的算法代码,然后去对应的链接获取。清单会同步更新,一旦有新的代码,就可以在清单里找到。清单里面有部分代码是开源获取的。可随时免费下载。

链接:https://pan.baidu.com/s/1SFDMplrL7tiqGZlrpOSGYg

提取码:8023

此外,欢迎添加算法交流群进行交流:912369858

文章来源:https://blog.csdn.net/jieyanping/article/details/135188509
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。