基于混合离散人工蜂群算法的...零等待柔性流水车间优化研究_轩华.pdf
《基于混合离散人工蜂群算法的...零等待柔性流水车间优化研究_轩华.pdf》由会员分享,可在线阅读,更多相关《基于混合离散人工蜂群算法的...零等待柔性流水车间优化研究_轩华.pdf(11页珍藏版)》请在文库网上搜索。
1、第 28 卷 第 1 期2023 年 2 月工业工程与管理Industrial Engineering and ManagementVol.28 No.1Feb.2023基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究轩华,付鑫博,李冰(郑州大学 管理学院,河南 郑州 450000)摘要:从钢铁业等流程工业提炼出一类混合零等待柔性流水车间问题,其中一些加工阶段要求工件连续不断地经过这些工序,对该问题建立了整数规划模型,提出了一种混合离散人工蜂群算法以最小化最大完工时间。采用二维矩阵编码表述染色体以及工件右移调整策略进行解码以获取调度解,改进NEH启发式规则用于生成初始种群。在雇佣蜂阶段
2、,引入了修正粒子群优化算法产生新解;在跟随蜂阶段,设计了迭代贪婪算法中的破坏和构造算子,进一步增强算法的搜索能力;在侦查蜂阶段,利用变邻域搜索算子以替换最差解。对不同规模问题进行了仿真测试并与现有算法进行对比,结果表明所提算法在求解混合零等待柔性流水车间问题方面更加有效。关键词:混合零等待;柔性流水车间;混合离散人工蜂群算法;最小化最大完工时间中图分类号:TB 49 文献标识码:AResearch on Optimization of Mixed Zero-Wait Flexible Flowshop Based on Hybrid Discrete Artificial Bee Colony
3、 AlgorithmXUAN Hua,FU Xinbo,LI Bing(School of Management,Zhengzhou University,Zhengzhou,Henan 450001,China)Abstract:A mixed zero-wait flexible flowshop problem was abstracted from process industry such as steel industry,where some processing stages required the jobs to visit these operations continu
4、ously.An integer programming model was formulated for this problem and a hybrid discrete artificial bee colony algorithm was presented to minimize maximum completion time.Two-dimensional matrix coding was applied to describe chromosomes and job right-shift adjustment strategy was used for decoding t
5、o achieve scheduling solutions.The NEH heuristic rule was modified to generate the initial population.In the employed bee stage,a modified particle swarm optimization algorithm was introduced to yield new solutions.In the onlooker bee stage,the destruction and construction operators from iterated gr
6、eedy algorithm were designed to further enhance search ability.In the scouter bee stage,the variable neighborhood search operator was used to replace the worst solution.Simulation tests were carried out for different scale problems and the comparison was performed with some current algorithms.The re
7、sults show that the proposed algorithm is more effective in solving mixed zero-wait flexible flowshop problems.Key words:mixed zero-wait;flexible flowshop;hybrid discrete artificial bee colony algorithm;文章编号:1007-5429(2023)01-0170-11DOI:10.19495/ki.1007-5429.2023.01.018收稿日期:2021-09-01基金项目:国家自然科学基金资助
8、项目(U1804151,U1604150);河南省科技攻关计划项目(202102310310)作者简介:轩华(1979),河南睢县人,博士,教授,主要研究方向为生产计划与调度、物流优化与控制等。E-mail:.-170第 1期工 业 工 程 与 管 理minimization of makespan1 引言 柔性流水车间问题(flexible flowshop problem,FFP)在流程工业普遍存在,它包含多个加工阶段,每个阶段由多台并行机构成。经典FFP常假设相邻加工阶段间有无限中间缓冲区,即工件在阶段之间可以停留。但实际生产中,部分工序由于工艺要求需要工件连续不断地经过这些加工阶段进行
9、加工,因此形成了混合零等待柔性流水车间问题(mixed zero-wait flexible flowshop problem,MZWFFP),这类问题已广泛应用于钢铁业、食品生产和化工业等1。例如,在钢铁业的炼钢-连铸-直轧生产过程中,经电弧炉或转炉生成的钢水进入连铸机进行浇铸,形成的高温板坯不经加热炉而直接送上轧线,该过程的每个阶段又有多台并行机组成,因此可归结为MZWFFP。在食品工业也存在类似情况,罐头加工中,采购、清洁和去除果皮过程无零等待要求,但加入糖液之后的密封、灭菌等过程则一经开始就不能中断 2。由于完成同一工序的并行机器结构不同(如前述的电弧炉或转炉)或机器不同程度的磨损,都
10、会导致同一工件在不同并行机器上的加工时间各有不同。因此,本文研究含不相关并行机的混合零等待 柔 性 流 水 车 间 问 题(mixed zero-wait flexible flowshop problem with unrelated parallel machines,MZWFFP-UPM),目标是最小化最大完工时间。零等待柔性流水车间问题(zero-wait flexible flowshop problem,ZWFFP)已被证明是NP-hard问题 3,故更为复杂的MZWFFP-UPM也是NP-hard问题。有限等待时间FFP可视为零等待FFP的扩展,它要求工件在相邻加工阶段间的等待时
11、间不能超过一定上限。一些学者运用精确算法对含有限等待时间约束的FFP进行了求解。在等同并行机环境下,常晓坤和董明4建立了不确定环境下的两阶段随机规划模型,提出了L型切面的求解算法以最小化期望成本和。随着问题规模和复杂度的增加,更多的学者运用近似算法进行求解。针对含等同并行机和有限等待时间的FFP,丁小丽等5提出一种基于工件分解策略的拉格朗日松弛算法以最小化总加权完成时间;BEHNAMIAN和ZANHDIEH6考虑顺序相关调整时间,提出了一种离散殖民竞争算法以最小化线性提前和二次拖期之和;SANTOSA等7考虑忽略工序,提出了离散粒子群优化以同时最小化 makespan、总延迟时间和总机器空闲时
12、间。针对含不相关并行机和有限等待时间的 FFP,ATTAR等8假定每个工件跳过一些阶段,将工件在这些忽略阶段的加工时间视为零,提出了基于生物地理学的优化算法以最小化makespan。零等待FFP为有限等待时间FFP的特例,它意味着工件在相邻工序间的有限等待时间为零,这对节能和缩短生产周期等有着重要的价值。在精确算法求解方面,WANG等1研究了第一阶段包含一台机器且第二阶段包含m台等同并行机的情况,提出了分支定界法以最小化 makespan;李岩和李铁克9考虑等同并行机,提出约束规划法以最小化makespan。为近似求解 ZWFFP,在等同并行机环境下,轩华等10考虑工件释放时间,提出了基于代理
13、次梯度法的改进拉格朗日松弛算法以最小化总加权完成时间;HUANG等11考虑调整时间和交货时间窗,提出了改进蚁群优化算法以最小化总加权提前和拖期;PENG等12针对从炼钢-精炼-连铸过程提炼的带机器故障的FFP重调度问题,设计了结合炉次左移策略的向后解码方式,提出了混合变邻域搜索(variable neighborhood search,VNS)的离散人工蜂群(discrete artificial bee colony,DABC)算法以最小化平均滞留时间、未开工浇次开工提前/拖期、浇铸中断、初始调度和新调度的工序开工时间差之和,以及初始调度和新调度的不同机器上加工的工序数的加权和;ASEFI等
14、13考虑序列相关调整时间,提出了一种融合非支配排序遗传算法和VNS的混合算法以同时最小化makespan和平均拖期;薄洪光等14以总加权完成时间为初始调度目标、总加权完工滞后时间为扰动修复目标,建立了干扰管理调度模型,提出了混合粒子群优化算法。在不相关并行机环境下,JAFARZADEH等15考虑返工时间,提出了调整离散多目标杂草优化算法以同时最小化makespan和平均延误时间;RABIEE等16考虑机器合格性和序列相关调整时间,提出了基于生物地理学的优化算法以最小化平均拖期;XUAN等17提出-171第 28 卷 轩华,等:基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究了一种遗传模
15、拟退火算法以最小化总流程时间。围绕混合零等待问题,为求解流水车间调度,孙厚权和张其亮18假设同时存在阻塞和零等待约束,提出了DABC算法以最小化makespan;WANG等2、CHENG 等19考虑无零等待和零等待的混合约束,提出了改进的迭代贪婪(iterated greedy,IG)算法以最小化 makespan。为求解 FFP,GICQUEL等20考虑等同并行机、多处理器任务、混合零等待和有限等待时间约束,提出了一种基于离散时间表述和混合整数线性规划模型的精确求解方法以最小化总加权拖期;张其亮和陈永生21考虑了不相关并行机环境下零等待和阻塞的混合约束,提出了一种结合 IG 算法的离散粒于群
16、优化算法(particle swam optimization,PSO)以最小化makespan。从目前所查阅的文献来看,已有的混合零等待问题的研究主要以流水车间环境为主,较少探讨更复杂的柔性流水车间环境,而不相关并行机结构进一步增加了MZWFFP的求解难度。考虑到PSO求解混合零等待约束的能力 21,鉴于人工蜂群(artificial bee colony,ABC)算法在求解车间调度(尤其是FFP)时有较好表现,本文为解决MZWFFP-UPM,引入IG算法、修正PSO和VNS,提出基于DABC算法的混合算法(hybrid discrete artificial bee colony,HDAB
17、C),以获得makespan问题的近优解。2 问题建模 2.1问题描述所研究的MZWFFP-UPM可描述为:n个工件按照相同的加工顺序,经过m个加工阶段进行处理。每阶段i有ui台不相关并行机,且至少有一个阶段ui1。在阶段i,每个工件可在并行机中的任一台进行加工,其加工时间取决于选定的机器。每台机器一次只能加工一个工件,每个工件一次也只能在一台机器上进行加工。为了满足工件部分工序的零等待要求,工件需在这些工序之间连续不断地加工,中间不允许停留,而工件在其余工序之间则允许等待。定义无零等待约束的阶段集为,有零等待约束的阶段集为。以包含 6道工序的 MZWFFP 为例,若=3,6 ,则=1,2,4
18、,5 ,据此可得到零等待阶段子集1=1,2 ,2=4,5 。调度的目标是找到最佳工件处理序列以及最佳机器分配序列,使最大完工时间Cmax最小。应用三域表示法,可将所研究问题表示为FFm(u1,um)|mixed,zero-wait|Cmax。2.2符号定义数学符号定义如下。n:待加工工件总数;m:阶段总数;j,j:工件编号,j,j=0,1,2,n;i:阶段编号,i=0,1,2,m;ui:阶段i的不相关并行机数,i=0,1,2,m;k:机器编号,k=1,2,ui;Pjik:工件j在阶段i的机器k上的加工时间,i=0,1,2,m;j=0,1,2,n;k=1,2,ui;:无零等待约束的阶段集;:零等
19、待阶段集;d:零等待阶段集的第d个子集;0:零等待阶段子集的第一个阶段的集合;H:足够大的常数;J0:虚拟工件0;U0:虚拟阶段 0,该阶段只有一台机器,Pj01=0(j=0,1,n)且P0i1=0(i=0,1,m);bji:工件j在阶段i进行加工的开始时间,i=0,1,2,m;j=0,1,2,n;b0i=0;cji:工件j在阶段i进行加工的结束时间,i=0,1,2,m;j=0,1,2,n;c0i=0;Vijj:若在阶段i工件j紧随工件j之后加工,Vijj=1;否则,Vijj=0(i=0,1,2,m;j,j=0,1,2,n);Zjik:若工件j在阶段i的机器k上进行加工,Zjik=1;否则,Z
20、jik=0(i=0,1,2,m;j=0,1,2,n;k=1,2,ui)。2.3模型根据以上描述及符号定义,将所研究问题建模为整数规划模型:min Cmax(1)s.t.k=1uiZjik=1,j,i(2)cji=bji+k=1uiPjikZjik,j,i(3)bjibj,i-1+k=1ui-1Pj,i-1,kZj,i-1,k,j;i0(4)-172第 1期工 业 工 程 与 管 理bji=bj,i-1+k=1ui-1Pj,i-1,kZj,i-1,k,j;i-0(5)Vijj+Vijj1,j,j,i(6)bji+H(3-Zjik-Zjik-Vijj)bji+PjikZjik,j,j,i,k(7)
21、Cmax=max Cjm,j(8)Vijj,Zjik 0,1,j,j,i,k(9)b0i=0,c0i=0,i(10)式(1)为问题目标,即最小化最大完工时间。约束式(2)表示每个工件在任一阶段只能由一台机器加工。约束式(3)定义了加工时间。约束式(4)描述了阶段间无零等待约束时工序优先级关系。约束式(5)确保了在有零等待要求的加工阶段间,同一工件的各工序加工的连续性。约束式(6)和式(7)表示对于分配到同一台机器的两个工件,位于序列后面的工件必须在前面工件完工后才能开始。约束式(8)定义了最大完工时间。约束式(9)说明了变量的取值范围。约束式(10)确保了虚拟工件在任一阶段的开/完工时间为零。
22、3 混合离散人工蜂群算法 ABC算法是模仿蜜蜂采蜜行为而产生的一类群体智能优化算法,采蜜蜂与蜜源相对应,而每个蜜源代表一个可行解,其中采蜜蜂由雇佣蜂、跟随蜂和侦查蜂组成。雇佣蜂寻找并记录蜜源;跟随蜂根据雇佣蜂分享的信息寻找新蜜源;最后,若一个蜜源经过多次尝试仍未变化,雇佣蜂成为侦查蜂,进行随机搜索以找到新蜜源。3.1算法基本思想经典ABC算法主要用于求解连续函数优化问题22-24。虽 然 一 些 学 者 改 进 ABC 算 法 解 决 了FFP25-26,但本文所建模型为基于离散时间的整数规划模型,所考虑的并行机环境和中间存储策略有所不同。因此,为有效求解混合零等待问题,针对所研究的FFm(u
23、1,um)|mixed,zero-wait|Cmax提出了HDABC算法。采用同时包含工件排序和机器分配的二维矩阵编码,使用 NEH启发式规则构造初始种群。为避免HDABC算法陷入局部最优,在雇佣蜂阶段引入修正PSO,提高全局寻优能力;在跟随蜂和侦查蜂阶段分别设计IG算子和VNS算子,进一步改善搜索效率。图1给出了HDABC算法的流程,具体过程如下。Step 1:初始化参数。设置种群规模NP以及最大迭代数MC。Step 2:产生初始种群。采用NEH启发式规则产生NP个蜜源构成初始种群。Step 3:初始化全局最优解和局部最优解。通过适应度函数计算每个蜜源的适应度值,适应度值最高的蜜源作为全局最
24、优解,所有蜜源作为局部最优解。Step 4:如果满足终止条件,输出全局最优解;否则,继续Step 5。Step 5:雇佣蜂阶段。设计修正PSO产生新解,计算每个新解的适应度值,应用轮盘赌规则为跟随蜂选择解。Step 6:跟随蜂阶段。使用IG算子搜索所选解的邻域,计算适应度值,记录最佳解。Step 7:侦查蜂阶段。找到最差解worstC,使用VNS算子对其进行改进以替换最差解,计算改进解的适应度值,更新全局最优解和局部最优解,转至步骤Step 4。图1 HDABC算法流程3.2二维矩阵编码MZWFFP-UPM 需同时确定机器分配和工件处理序列,故采用基于机器号的二维矩阵编码表述蜜源,矩阵中每个元
25、素TRji满足 1,ui 的均匀分布,用以表示序列内处于第j个位置的工件(j)在阶段i分配的机器号,图2显示了n个工件的编码方案。-173第 28 卷 轩华,等:基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究3.3基于工件右移调整策略的解码解码即为获得调度解的过程。在阶段1依据工件处理序列将工件分配至相应机器,后续阶段则按照先到先处理规则依次安排各工件。为了满足工件在部分工序的零等待约束,确保同一机器上加工的工件不产生冲突,提出一种工件右移调整策略用以解码。3.3.1工件右移调整策略(1)检验操作。针对零等待阶段子集d,首先检验工件 j 在 d内各阶段之间是否满足零等待约束,即计算工
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 混合 离散 人工 蜂群 算法 等待 柔性 流水 车间 优化 研究 轩华