基于混合离散人工蜂群算法的...零等待柔性流水车间优化研究_轩华.pdf

第 28 卷 第 1 期2023 年 2 月工业工程与管理Industrial Engineering and ManagementVol.28 No.1Feb.2023基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究轩华，付鑫博，李冰（郑州大学 管理学院，河南 郑州 450000）摘要:从钢铁业等流程工业提炼出一类混合零等待柔性流水车间问题，其中一些加工阶段要求工件连续不断地经过这些工序，对该问题建立了整数规划模型，提出了一种混合离散人工蜂群算法以最小化最大完工时间。采用二维矩阵编码表述染色体以及工件右移调整策略进行解码以获取调度解，改进NEH启发式规则用于生成初始种群。在雇佣蜂阶段，引入了修正粒子群优化算法产生新解；在跟随蜂阶段，设计了迭代贪婪算法中的破坏和构造算子，进一步增强算法的搜索能力；在侦查蜂阶段，利用变邻域搜索算子以替换最差解。对不同规模问题进行了仿真测试并与现有算法进行对比，结果表明所提算法在求解混合零等待柔性流水车间问题方面更加有效。关键词:混合零等待；柔性流水车间；混合离散人工蜂群算法；最小化最大完工时间中图分类号:TB 49 文献标识码:AResearch on Optimization of Mixed Zero-Wait Flexible Flowshop Based on Hybrid Discrete Artificial Bee Colony 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 continuously.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 to 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 greedy 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 results 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基金项目：国家自然科学基金资助项目（U1804151，U1604150）;河南省科技攻关计划项目（202102310310）作者简介：轩华（1979），河南睢县人，博士，教授，主要研究方向为生产计划与调度、物流优化与控制等。E-mail：.-170第 1期工 业 工 程 与 管 理minimization of makespan1 引言 柔性流水车间问题（flexible flowshop problem，FFP）在流程工业普遍存在，它包含多个加工阶段，每个阶段由多台并行机构成。经典FFP常假设相邻加工阶段间有无限中间缓冲区，即工件在阶段之间可以停留。但实际生产中，部分工序由于工艺要求需要工件连续不断地经过这些加工阶段进行加工，因此形成了混合零等待柔性流水车间问题（mixed zero-wait flexible flowshop problem，MZWFFP），这类问题已广泛应用于钢铁业、食品生产和化工业等1。例如，在钢铁业的炼钢-连铸-直轧生产过程中，经电弧炉或转炉生成的钢水进入连铸机进行浇铸，形成的高温板坯不经加热炉而直接送上轧线，该过程的每个阶段又有多台并行机组成，因此可归结为MZWFFP。在食品工业也存在类似情况，罐头加工中，采购、清洁和去除果皮过程无零等待要求，但加入糖液之后的密封、灭菌等过程则一经开始就不能中断 2。由于完成同一工序的并行机器结构不同（如前述的电弧炉或转炉）或机器不同程度的磨损，都会导致同一工件在不同并行机器上的加工时间各有不同。因此，本文研究含不相关并行机的混合零等待 柔 性 流 水 车 间 问 题（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的扩展，它要求工件在相邻加工阶段间的等待时间不能超过一定上限。一些学者运用精确算法对含有限等待时间约束的FFP进行了求解。在等同并行机环境下，常晓坤和董明4建立了不确定环境下的两阶段随机规划模型，提出了L型切面的求解算法以最小化期望成本和。随着问题规模和复杂度的增加，更多的学者运用近似算法进行求解。针对含等同并行机和有限等待时间的FFP，丁小丽等5提出一种基于工件分解策略的拉格朗日松弛算法以最小化总加权完成时间；BEHNAMIAN和ZANHDIEH6考虑顺序相关调整时间，提出了一种离散殖民竞争算法以最小化线性提前和二次拖期之和；SANTOSA等7考虑忽略工序，提出了离散粒子群优化以同时最小化 makespan、总延迟时间和总机器空闲时间。针对含不相关并行机和有限等待时间的 FFP，ATTAR等8假定每个工件跳过一些阶段，将工件在这些忽略阶段的加工时间视为零，提出了基于生物地理学的优化算法以最小化makespan。零等待FFP为有限等待时间FFP的特例，它意味着工件在相邻工序间的有限等待时间为零，这对节能和缩短生产周期等有着重要的价值。在精确算法求解方面，WANG等1研究了第一阶段包含一台机器且第二阶段包含m台等同并行机的情况，提出了分支定界法以最小化 makespan；李岩和李铁克9考虑等同并行机，提出约束规划法以最小化makespan。为近似求解 ZWFFP，在等同并行机环境下，轩华等10考虑工件释放时间，提出了基于代理次梯度法的改进拉格朗日松弛算法以最小化总加权完成时间；HUANG等11考虑调整时间和交货时间窗，提出了改进蚁群优化算法以最小化总加权提前和拖期；PENG等12针对从炼钢-精炼-连铸过程提炼的带机器故障的FFP重调度问题，设计了结合炉次左移策略的向后解码方式，提出了混合变邻域搜索（variable neighborhood search，VNS）的离散人工蜂群（discrete artificial bee colony，DABC）算法以最小化平均滞留时间、未开工浇次开工提前/拖期、浇铸中断、初始调度和新调度的工序开工时间差之和，以及初始调度和新调度的不同机器上加工的工序数的加权和；ASEFI等13考虑序列相关调整时间，提出了一种融合非支配排序遗传算法和VNS的混合算法以同时最小化makespan和平均拖期；薄洪光等14以总加权完成时间为初始调度目标、总加权完工滞后时间为扰动修复目标，建立了干扰管理调度模型，提出了混合粒子群优化算法。在不相关并行机环境下，JAFARZADEH等15考虑返工时间，提出了调整离散多目标杂草优化算法以同时最小化makespan和平均延误时间；RABIEE等16考虑机器合格性和序列相关调整时间，提出了基于生物地理学的优化算法以最小化平均拖期；XUAN等17提出-171第 28 卷 轩华，等：基于混合离散人工蜂群算法的混合零等待柔性流水车间优化研究了一种遗传模拟退火算法以最小化总流程时间。围绕混合零等待问题，为求解流水车间调度，孙厚权和张其亮18假设同时存在阻塞和零等待约束，提出了DABC算法以最小化makespan；WANG等2、CHENG 等19考虑无零等待和零等待的混合约束，提出了改进的迭代贪婪（iterated greedy，IG）算法以最小化 makespan。为求解 FFP，GICQUEL等20考虑等同并行机、多处理器任务、混合零等待和有限等待时间约束，提出了一种基于离散时间表述和混合整数线性规划模型的精确求解方法以最小化总加权拖期；张其亮和陈永生21考虑了不相关并行机环境下零等待和阻塞的混合约束，提出了一种结合 IG 算法的离散粒于群优化算法（particle swam optimization，PSO）以最小化makespan。从目前所查阅的文献来看，已有的混合零等待问题的研究主要以流水车间环境为主，较少探讨更复杂的柔性流水车间环境，而不相关并行机结构进一步增加了MZWFFP的求解难度。考虑到PSO求解混合零等待约束的能力 21，鉴于人工蜂群（artificial bee colony，ABC）算法在求解车间调度（尤其是FFP）时有较好表现，本文为解决MZWFFP-UPM，引入IG算法、修正PSO和VNS，提出基于DABC算法的混合算法（hybrid discrete artificial bee colony，HDABC），以获得makespan问题的近优解。2 问题建模 2.1问题描述所研究的MZWFFP-UPM可描述为：n个工件按照相同的加工顺序，经过m个加工阶段进行处理。每阶段i有ui台不相关并行机，且至少有一个阶段ui1。在阶段i，每个工件可在并行机中的任一台进行加工，其加工时间取决于选定的机器。每台机器一次只能加工一个工件，每个工件一次也只能在一台机器上进行加工。为了满足工件部分工序的零等待要求，工件