改进离散候鸟优化算法求解带缺失阶段的柔性流水车间问题_轩华.pdf

第 28 卷 第 1 期2023 年 2 月工业工程与管理Industrial Engineering and ManagementVol.28 No.1Feb.2023改进离散候鸟优化算法求解带缺失阶段的柔性流水车间问题轩华，樊银格，李冰（郑州大学 管理学院，河南 郑州 450001）摘要:针对每阶段包含不相关并行机的柔性流水车间调度，研究了具有缺失阶段的总加权完工时间问题。由于该问题是NP-hard的，因此，提出基于两段式编码和组合邻域策略的改进离散候鸟优化算法进行求解。基于机器和工件编号设计两段式编码，利用最短加工时间规则和随机策略获得初始候鸟种群。领飞鸟和跟飞鸟进化中引入组合邻域策略以产生邻域解，最后对最差个体设计重置机制以再次提高解的质量。针对不同规模问题，对所提算法和四种启发式算法进行仿真实验，实验结果表明改进离散候鸟优化算法得到了更高质量的满意解。关键词:柔性流水车间；缺失阶段；不相关并行机；改进离散候鸟优化算法；组合邻域策略中图分类号:TB 49 文献标识码:AImproved Discrete Migrating Birds Optimization Algorithm for Flexible Flowshop Problem with Missing StagesXUAN Hua，FAN Yinge，LI Bing（School of Management，Zhengzhou University，Zhengzhou，Henan 450001，China）Abstract:Flexible flowshop scheduling with unrelated parallel machines in each stage and missing stages was studied with the objective of minimizing total weighted completion time.Since the problem was NP-hard，an improved discrete migrating birds optimization algorithm based on two segment encoding and combined neighborhood strategy was proposed to solve it.In the proposed algorithm，two segment encoding was designed according to the machine and job number.The shortest processing time rule and random strategy were used to generate the initial migratory bird population.Combined neighborhood strategy was introduced to generate neighborhood solutions during the leader and follower evolution.A reset mechanism for the worst individual was proposed to improve the solution quality again.For different scale problems，simulation experiments were performed for the developed algorithm and four heuristic algorithms.Testing results show that the improved discrete migrating birds optimization algorithm yields satisfactory solutions with higher quality.Key words:flexible flowshop scheduling problem;missing stages;unrelated parallel machines;improved discrete migrating birds optimization algorithm;combined neighborhood strategy文章编号：1007-5429（2023）01-0098-12DOI：10.19495/ki.1007-5429.2023.01.012收稿日期：2021-05-28基金项目：国家自然科学基金资助项目（U1804151）;河南省科技攻关计划项目（202102310310）作者简介：轩华（1979），河南睢县人，博士，教授，研究方向为生产计划与调度、物流优化与控制等。E-mail：.-98第 1期工 业 工 程 与 管 理1 引言 具有不相关并行机的柔性流水车间问题可描述为：n个工件按相同的加工路线依次访问g个生产阶段以完成加工任务，每个阶段由多台不相关机构成，工件选择的机器不同，则它在相应阶段的加工时间也不同。典型的柔性流水车间问题要求每个工件都需在g个生产阶段加工。然而，为了满足日益增长的客户定制化以及产品的多样性需求，一些工件的加工路线可能会越过某些生产阶段，即缺失某些阶段。例如，在不锈钢厂，不锈钢接头的生产过程包括倒角和开孔两个阶段，至少有一个阶段有h1台并行机，T型和L型接头都需在这两个阶段加工，但P型接头仅需第二个阶段即可 1。为解决实际生产中工件运输与调度的协调问题，本文提出了不相关并行机环境下带缺失阶段和运输考虑的柔性流水车间问题（flexible flowshop problem with missing stages and transportation consideration，FFP-MS&TC）。由于柔性流水车间问题（flexible flowshop problem，FFP）是 NP-hard 的 2，所以本文研究的更复杂的FFP-MS&TC也是NP-hard的。目前，已有不少学者展开了带缺失阶段的车间调度问题的研究。就流水车间问题而言，YU等3针对带等待时间约束的两机问题，假设一些工件越过了第一台机器，提出了近似算法最小化等待时间变化。针对多机问题，郭盈和刘心报4提出了局部搜索算法以最小化总加权完工时间；HENNEBERG 和NEUFELD5提出了构造式启发式算法和两阶段模拟退火算法以最小化总流程时间；RAMEZANIAN和RAHMANI6以最小化最大完工时间为目标建立了混合整数线性规划模型以获取小规模问题的最优解，提出了遗传算法近似求解大规模问题；ROSSIT等7提出了结合遗传算法和模拟退火算法的两阶段求解方法以最小化总拖期。对于更复杂的带缺失阶段的 FFP，TSENG等1研究了一些工件越过阶段1的两阶段FFP，其中，阶段1有一台机器，而阶段2包含两台等同机，提出了启发式算法最小化最大完工时间。针对带等同机和缺失阶段的多阶段FFP，为最小化最大完工时间，MARICHELVAM 和 PRABAHARAN8、SARAVANAN 等9-10、DIOS 等11-12分别提出了混合遗传分散搜索算法、遗传算法、模拟退火算法、粒子群优化、分派规则和改进启发式；SARAVANAN等13提出了遗传算法与模拟退火算法最小化平均拖期；黄辉等14考虑序列设置时间，提出了改进的NSGA-算法，目标为同时最小化最大完工时间和设备负荷均衡指标。考虑运输时间，LI等15从铁水系统提炼出允许动态工序跳跃的FFP，提出了改进离散人工蜂群算法以最小化平均滞留时间、总提前、总拖期和关键机器跳跃率的加权和；LONG等16提出了改进遗传算法，求解从炼钢-连铸生产过程提炼出的带可调加工时间的带缺失阶段的柔性流 水 车 间 问 题（flexible flowshop problem with missing stages，FFP-MS），目标为最小化最大完工时间、等待时间以及加工时间与标准加工时间的偏差之和。候鸟优化（migrating birds optimization，MBO）算法是DUMAN等17提出的一种新兴的群智能优化算法，已被用于解决 FFP。PAN 和 DONG18提出了一种结合跳跃机制，针对问题特征的启发式和局部搜索的改进候鸟优化（improved MBO，IMBO）算法以最小化总流程时间。任彩乐等19提出了基于两阶段解码方法的 IMBO 算法最小化最大完工时间。任彩乐等20考虑不相关并行机，提出了结合移动和关机重启策略的IMBO算法以最小化能耗。ZHANG等21针对带批量流的FFP，结合最短等待时间规则和组合邻域搜索策略提出了 IMBO 算法以最小化总流程时间。WANG等22结合NEH启发式和局部搜索提出了 IMBO 算法以最小化最大完工时间。ZHANG等23研究了带机器故障和工件取消的柔性流水车间重调度问题，提出了多目标MBO算法以同时最小化最大完工时间、工件开始时间偏差以及机器分配差异。上述MBO算法主要适用于解决连续变量的问题，为求解离散组合优化问题，需对MBO算法进行离散改进。为最小化最大完工时间，张素君和顾幸生24针对置换流水车间问题，提出了结合NEH（nawaz，enscore and ham，NEH）和局部搜索的离散候鸟优化（discrete migrating birds optimization，DMBO）算法；HAN 等25针对带阻塞批量流调度问题，提出了结合多领域搜索、分布估计算法和局部搜索的改进 DMBO 算法；ZHANG等26针对无等待流水车间调度问题，提出了结合标准偏差启发式、混合多领域策略和局部搜索的改进DMBO算法。如上所述，不相关并行机环境下的FFP-MS&-99第 28 卷 轩华，等：改进离散候鸟优化算法求解带缺失阶段的柔性流水车间问题TC还未引起广泛探讨，已有的FFP-MS研究中每阶段的机器类型多聚焦于等同机，而且经常把缺失阶段当作加工时间为零的阶段1，8-16，从而将 FFP-MS视为每个工件需经所有阶段（即使某阶段的加工时间为零）的常规FFP，这种处理方式需在每个阶段对所有工件进行机器分配和排序安排。为了减小工件在缺失阶段对其他工件加工安排的影响，本文对每个工件设置其未缺失阶段集，只需考虑工件在该集合内阶段的加工，即每个阶段有访问该阶段的工件集，调度的目标仅需确定该工件集内的工件加工顺序以及机器分配。作为一种最复杂的并行机类型，不相关并行机使得同一阶段不同机器的加工时间相互独立，这增加了问题的求解难度，而总加权完工时间问题有助于制造企业提高物流连续性。当前关于FFP-MS和MBO算法的研究缺乏对不相关并行机类型和总加权完工时间问题的探讨，考虑到FFP-MS&TC为离散型组合问题，本文针对不相关并行机环境下FFP-MS&TC，以最小化总加权完工时间为目标，提出基于最短加工时间规则和组合邻域策略的改进离散候鸟优化（improved discrete migrating birds optimization，IDMBO）算法，得到问题的满意解。2 问题描述及模型建立 FFP-MS&TC 可描述如下：n 个工件连续经 g个生产阶段进行加工，每个阶段j（j j|j=1，g ）包含Mj台不相关并行机。一些工件可能不在某些阶段加工，即工件i（i i|i=1，n ）实际访问的总阶段数|Bi|g（Bi表示工件i实际加工所经的阶段集合），因此该工件缺失了g|Bi|个生产阶段的加工，且在阶段j加工的工件数|Aj|n（Aj表示访问阶段j的工件集合）。假设所有机器在计划时间范围内连续可用，当工件i（iAj）访问阶段j时，可从Mj台不相关并行机中任选一台进行加工，由于阶段j的各台机器k（k k|k=1，2，Mj）相互独立，因此工件对机器的选择会影响该工件在此生产阶段的加工时间。令：Pikj表示工件i在阶段j的机