基于混合帝国竞争算法求解柔性作业车间调度_王雨洋.pdf

Science&Technology Vision科技视界0引言通过解决柔性作业车间调度问题（Flexible jobshop scheduling problem，FJSP），有效地组织车间的资源，对企业生产具有积极意义。该问题模型相较传统模型，工序加工任务指派的机器具有更多选择，更加贴近实际生产情况1。模型约束相比传统问题模型更为复杂，是更复杂的 NP-hard 问题2。相较于精确求解方法而言，智能优化算法更适用于求解 FJSP 模型，是如今求解该模型的主流求解方法。X Wang 等3基于 Pareto 最优的适应度方案，依据免疫和最小熵原理设计了一种多目标遗传算法，其在寻优时保持了种群的多样性，优化了过早收敛的缺陷。X Li 等4以最大完工时间为模型目标，将禁忌搜索与遗传算法混合，算法具有良好的收敛性和多样性，求解过程中展现了优秀的寻优能力。X Shao 等5将离散粒子群算法和模拟退火算法相混合，两种算法分别负责全局搜索与局部寻优，并采用多种方法进行粒子的适应度的识别。S Huang 等6将变邻域搜索融入离散多目标粒子群优化算法进行改进，该算法以关键块为基础构建邻域进行变邻域搜索，从而改善了算法的寻优能力。Q Deng 等7提出了一种适用于求解最大完成时间、瓶颈机器负载及机器总负载为研究目标的非支配排序遗传算法，采用蜜蜂进化引导策略提高了解空间寻优能力。本文以最大完工时间、关键机器负载以及机器总负载作为目标，在帝国竞争算法的基础上进行改进。通过基准算例测试表明，该算法在求解柔性作业车间调度方面具有较好的性能和效果。1模型描述1.1问题描述FJSP 模型描述如下：已知工件集有 n 个工件需进行加工（Ji，i=1，2，n）要在 m 台机器（Mk，k=1，2，m）上加工。工件 Ji需要完成工艺路线规定的工序（Oij，i=1，2，n，j=1，2，ni），其中 ni是工件 Ji的工序数。每道工序可在可行机器集机器（Mij，MijMk）中任选一台机器加工。每道工序 Oij在机器 k 上的对应时间记为 pijk。记 Ck为机器 k 的完成时间，Wk为机器DOI：10.19694/ki.issn2095-2457.2022.31.50基于混合帝国竞争算法求解柔性作业车间调度王雨洋丁剑飞（中原工学院机电学院，河南 郑州450007）【摘要】柔 性 作 业 车 间 调 度 问 题 的 求 解 对 于 企 业 生 产 具 有 重 要 意 义。针 对 现 有 多 品 种、小 批 量 作 业 车 间 调 度 问题，以 最 小 化 最 大 完 工 时 间、关 键 机 器 负 载 以 及 机 器 总 负 载 为 目 标 建 立 调 度 数 学 模 型，提 出 一 种 改 进 帝 国 竞 争 算 法 进行求 解。算法 引 入殖 民 国改 革，使 寻优过 程 中产 生 更大 的 邻 域，通 过 与变 邻域 算 法混 合 进 行 求 解，并采 用 外部 档案 集对其 中 较 优 解 个 体 进 行 保 留，采 用 变 动 权 重 加 权 法 对 个 体 进 行 评 价，对Kacem基 准 算 例 进 行 求 解，以 证 明 所 提 出 算 法 求解 性 能。【关键词】柔 性 作业 车间调 度；多目 标 调 度；帝 国 竞争 算 法；变 邻 域搜 索基金 项 目：河南省 科 技攻 关项目（182102210515）。作 者简 介：王 雨洋，硕士研 究 生，研 究 方 向为智 能 化 生产 调 度。丁 剑飞，博 士，讲师，硕士生 导 师，研究 方 向为 运 筹优 化，企 业 信 息化。管理科学175科技视界Science&Technology Visionk 的总负载。问题模型中存在约束：在任意时刻某机器最多加工一道工序，且任意工件不能同时出在多台机器上；本问题模型中，机器加工不存在机器故障的情况，即加工开始后不可中断等。1.2数学模型本问题模型中优化目标函数如下：（1）最大完工时间f1（x）=minmax0kmCk（1）（2）关键机器负载f2（x）=minmax0kmWk（2）（3）机器的总负载f3（x）=minmk=1Wk（3）本文选择 f1（x）、f2（x）、f3（x）的加权和作为优化目标，如式（4）所示。f（x）=w1f1（x）+w2f2（x）+w3f3（x）（4）其中：w1+w2+w3=1，0w1，w2，w31。2基于变邻域搜索混合帝国竞争算法帝国竞争算法（Imperialist competition algorithm，ICA）与其他常用群智能算法相比，能够更快更准确地求解，且在全局求解中有较强的收敛性。但是标准的ICA 容易出现“早熟”现象。变邻域搜索（VariableNeighborhood Search，VNS）在可行域进行寻优时，具有很强的局部寻优能力，且适用于混合求解。因此我们为提升 ICA 的求解寻优能力，把 ICA 和 VNS 相结合，以增强标准 ICA 的局部探索能力，提高算法的求解能力。2.1算法流程在应用 ICA 时，首先需要生成一组可行解作为迭代的初始群体，该群体的个体各自视为一个国家。势力较强的国家作为帝国集团的殖民国，其他国家则成为这些帝国中的殖民地。每个帝国都拥有一定数量的殖民地，殖民国会对它的殖民地进行同化，并在这个过程中吸取有用的殖民地信息以产生改革提高自己，殖民地也会通过革命来提高自身的势力。通过同化、改革和革命，帝国集团的势力会发生变化，其中势力最强的殖民地会取代原有殖民国。形成新的帝国集团状态后，各帝国集团之间将以竞争的方式再次调整殖民地分配，较弱的帝国集团在此过程中将会被其他帝国逐渐瓜分，若其已失去所有殖民地，它将会作为其他帝国的殖民地存在8。算法步骤如下：步骤一：采用双段式编码随机生成 N 个合理初始种群，将最大完工时间、关键机器负荷以及总负荷进行加权后对种群进行评价，从中选出 Nim 个优秀种群作为初始帝国中的殖民国，其余解作为殖民地，依据殖民国的评价顺序对殖民地进行分配，形成初始帝国。步骤二：进行殖民地同化，以殖民地工序编码为父代，随机生成 1-3 个定位值，将其对应位置的机器编号替换成殖民国的同位代码，并对新生成的殖民地编码进行调整，使其满足工业要求与约束，将其同化前编码存入外部档案集。步骤三：进行殖民国改革，通过生成随机数，与改革因子 Pg 进行比较，若小于改革因子，则将殖民国中的某个工件的加工机器全部替换为最优殖民地的机器序号，将其改革前个体编码。步骤四：在殖民地进行革命操作时，基于关键路径产生对应的邻域结构，通过同机器内的工序移动构建邻域解。同机器内的工序移动是指，各工序所选的对应加工机器编码不发生改变，寻找到加工过程中的关键工序，将关键工序的位置进行更改，即调整编码方案中某些工序部分对应位置。将这个过程中产生的个体记入外部档案集步骤五：对所有殖民地评价值进行计算，并与现在帝国中的殖民国进行对比，评价值最高的国家将作为新的殖民国，并将剩余个体与外部档案集中的个体进行排序，选出原有殖民地数量的个体成为新殖民地，并清空外部档案集。步骤六：以所有帝国集团为环境，计算所有帝国的平均势力值，其中评价值最低的帝国将会损失随机一个殖民地，该殖民地将会由其他帝国重新分配，若某一帝国仅剩殖民国，则对该殖民国进行分配，并将该帝国集团剔除。步骤七：依据设置的终止条件进行判断，若符合条件则结束迭代，若不满足条件，则返回步骤二进行迭代。2.2编码方式本文在求解单目标 FJSP 问题时采用双段式编管理科学176Science&Technology Vision科技视界码，将问题的解以整数串形式进行编码，整数串的长度为 2 倍的 Nh，并且将问题分为两个子问题，所以染色体的形式分为 2 层，每层长度为 Nh，上层为机器加工顺序部分，染色体的数字表示工件序号，通过工件序号出现的次数表示该工件的工序号；下层为机器选择部分，其代表的数字含义即从可选机器集 MHij中选出对应机器进行加工。采用这种方式进行下层染色体的编码，可以在编码时避免某些情况产生的“非法染色体”出现导致的求解失误。当然，在进行少批量维度的模型或者完全柔性模型进行求解时，可以采用机器序号作为染色体的基因位。2.3帝国竞争帝国集团之间的竞争将会对最弱帝国的随机殖民地进行再次分配，此过程采用随机规则进行。每个帝国集团的总势力将影响其获得分配的概率，总势力用公式（5）计算。TCi=Ci+1ncolincolij=1Cij（5）其中和分别是帝国 i 的势力和对应帝国集团总势力；Cij是帝国 i 中第 j 个殖民地的势力；帝国 i 所拥有的殖民地数量记为 ncoli。常数为 殖民地的考虑因子，通常取小于 1 的数。通过帝国竞争，最弱的帝国会逐渐失去它拥有的殖民地，这个帝国也会随之消亡，变成其他帝国的殖民地。2.4适应度计算适应度值用来评价算法生成的所有国家的性能，为了消除三个目标函数值不同量级的影响，我们采用了式（6）所示的归一化的适应度计算公式。fitnessi=3d=1wdfid-fmindfmaxd-fmind（6）式中：wd表示第 d 个目标函数的权值，fid表示第 i个国家的第 d 个目标函数值，fmind则表示第 d 个优化目标的最小值，表示第 d 个优化目标的最大值。在进行初代评价时，先采用相等的权重对种群进行评价，以外部档案集尽可能降低权重造成的影响，根据第一次迭代过程中所得最优解的结果对个目标的权重进行归一化加权调整，使各目标函数在经过加权后数量级保持在同一范围，即在迭代过程中目标函数的权重将会产生变化。3算法测试为验证本文所提算法在求解 FJSP 时的性能，通过算例进行验证，且同文献中其他算法进行对比。本文设计的算法采用 Microsoft Visual C#2019 开发，并在 8G 内存 1.8GHz CPU 的 PC 机上进行了测试。本算法采用的基准算例包括 Kacem 算例中的 88、1010 及 1510 三个测试算例1，测试值是 10 次独立运行后的最优解。测试问题的运行参数如下：最大迭代次数为 200，国家数量为 60，其中帝国占比 15%，殖民国改革因子Pg=0.05，总势力计算公式中殖民地考虑因子=0.098。我们选择进行对比的算法包括：hDPSO（混合离散粒子群算法）5、MPSO-VNS（基于变邻域搜索的粒子群算法）6、BEG-NSGAII（蜜蜂进化导向非支配排序遗传算法）7。与其他算法就测试算例进行结果对比，如表 1 所示。表1Kacem三个算例的运算结果图 1 给出了 Kacem1510 算例的一个最优解的甘特图，该算例要求在 10 台机器上完成 15 个工件的 56项加工任务。由甘特图可知，最优解的最大完工时间Cm=12，关键机器负载 Wm=10，机器总负载 Wt=93。算法8810101510CmWmWtCmWmWtCmWmWthDPSO141277754311119115127576421210931613738542MPSO-VNS151275754311119116117776421110931613738542BEG-NSGAII141277754311119115127576421210931613738542ICA-VNS141277754311119115127576421210931613738542管理科学177科技视界Science&Technology Vision图1Kacem1510最优解甘特图4结论与展望针对多目标 FJSP 模型，提出一种混合变邻域搜索策略的改进帝国竞争算法（ICA-VNS），并与文献中其他算法就 Kacem 算例的求解结果进行对比。从结果可以看出，该算法能够有效获取问题中的最优解。本文讨论的是学术界研究最广泛的柔性作业车间调度问题，与实际生产情况相比尚有一定差距。很多内容需要进一步进行扩充，比如考虑准备时间、机器可能出现的故障以及紧急订单插入等。【参考文献】1IKacem，SHammadi，PBorne.Approachbylocalizationandmul