求解柔性分批调度问题的双层搜索框架入侵杂草算法_闫富乾.pdf

第 卷第期计算机集成制造系统 年月 ：收稿日期：；修订日期：。；基金项目：国家重点研发计划资助项目（）。：，（）求解柔性分批调度问题的双层搜索框架入侵杂草算法闫富乾，陈浩杰，丁国富，孟祥印，张剑（西南交通大学 先进设计与制造技术研究所，四川成都 ）摘要：针对柔性作业车间分批调度问题，提出一种双层搜索框架下的改进入侵杂草算法，以获得理想的分批调度方案。首先提出融合批次批量、工序排列和加工机器信息的层基因编码；其次设计一种双层搜索优化框架，先通过分批搜索层进行柔性批量划分，再采用排序搜索层迭代优化获取分批调度方案。在分批搜索层中，基于工序平均工时缩小分批的解空间，提出随机数字分割法用以生成分批方案；在排序搜索层中，采用入侵杂草算法实现迭代优化，同时设计了分层初始化方法、混合机器选择策略和种局部搜索算子，以提升算法搜索能力，并避免陷入局部最优。最后以最大完工时间为评价指标，从性能实验分析、框架实验验证和实例实验验证个维度验证了所提算法的优越性和可行性。关键词：柔性作业车间；柔性分批调度；入侵杂草优化算法；双层搜索框架中图分类号：文献标识码：，（，）：，；，：，：；第期闫富乾 等：求解柔性分批调度问题的双层搜索框架入侵杂草算法引言作为传统作业车间调度问题（，）的扩展，柔性作业车间调度问题（，）打破了 机器固化的约束，更加符合实际生产需求，是当前车间生产调度领域的重要研究方向。然而，的调度优化研究大多基于单件调度，在实际生产过程中，为提高产品质量和降低成本，往往采用批量生产模式。虽然能以将某批工件视作整体的方式求解排序和机器选择等子问题，但是生产中批次批量的划分对完工时间等目标优化影响较大，为此 被拓展为柔性作业车间分批调度问题（，），其优化研究对于指导实际生产、缩短完工时间、提高机床利用率等具有重要意义。近年来，受到学术界的关注，然而总体研究较少。等针对具有批次的 建立了数学模型，提出一种两阶段优化方法，并实现了混合整数线性规划、约束规划和基于图的模型。如何对工件分批是 的研究重点，目前主要具有柔性分批和等量分批两种分批策略。在等量分批方面，孙志峻等提出一种将工件等量分批调度的遗传算法，能够同时优化批次划分和子批的加工顺序；黎英杰等针对多层级装配 ，基于等量分批策略提出该类车间基于可行域搜索的遗传算法；等提 出 一 种 新 的 混 合 整 数 规 划 问 题（，）公式，解决了生产中常见的批量调度问题。在柔性分批方面，陆志强等针对生产调度过程中由于设备退化引起的产品质量劣化问题，构建了考虑质量与设备状态之间的耦合关系以及生产批次可分的批量流调度与预防性维护的联合优化模型；等 将多目标梅花鹿算法与并行非支配排序遗传算法 结合，提出一种混合多目标元启发式算法。现有研究中，主要以等量分批的方式为主，批次数量固化会降低问题的组合性，缩小解空间，使优化陷入局部最优。而在有限的柔性分批研究中将分批与调度集成优化，会因缺乏局部层的深度搜索导致优化效果不理想。入侵杂草优化算法（，）是由 提出的一种智 能 算 法，具 有 良 好 的 全 局 和 局 部 搜 索 能力，适用于求解离散组合问题，但将其用于求解 尚缺乏相关研究。本文针对现有批量调度分批算法局部深度搜索不足的缺陷设计了一种双层搜索框架，外层搜索通过分批约束方案和随机数字分割法生成分批方案，并为本文提出的改进入侵杂草优化算法（，）提供初始种群，内层搜索则通过 迭代优化得到最优的分批调度方案。同时，针对传统 容易陷入局部最优的缺陷，设计一种分层选择法以增加种群多样性，并结合变邻域搜索和混合机床选择策略提升 的局部和全局搜索能力，以达到更好的搜索效果。最后，通过现有文献算例和工程实例，验证了该方法的有效性。柔性作业车间分批调度问题 问题描述 可以描述为：有台机床，类工件，每类工件的数量为，而且每类工件有，道工序，能加工每道工序的机床有（）台，每道工序的加工时间随机床性能差异变化。每类工件可分成多个子批量，在不同机器上加工，各子批量作为一个整体处理，包括加工、搬运等，并占用同一辅助时间。为便于描述模型，本文所使用的相关变量如下：为第类工件第批的完工时间；为第类工件第批第道工序在机器上的单件工时；为第类工件第道工序在机床上的辅助时间；为第类工件第批第道工序在机器上的开始加工时间；为第类工件第批第道工序在机器上的加工完成时间；为机器选择决策变量，当工序 可以在机器上加工时 ，否则 ；为辅助时间决策变量，当在机床上加工的工件类别与在该机床加工的上一个工件类别相同时，反之。该类问题满足以下假设：（）任何一批工件必须在前一道工序完成后才能进入下一道工序。计算机集成制造系统第 卷（）每台机床同一时刻只允许加工一个工件。（）工件的加工时间是确定的。（）工序一旦开始就不能中断，只有当该批工件的该工序全部被加工完成后，才能加工另一批工件。（）不同批次的工序没有先后约束关系。（）在零时刻，任意机器均可加工任意批次的任意工件。数学模型本文采用的目标函数为最大完工时间 ，即最后一批工件的最后一道工序的完工时间，其数学模型如下：。（），（，）；（），；（），；（）（），（）；（）。（）其中：式（）为机器选择约束，每道工序只能在可加工该工序的机床上加工；式（）为零件的分批约束，即每批工件下的所有子批数量之和等于该批工件数量；式（）表示任何子批都应在该机器加工的上一道工序结束后开始加工；式（）为工艺约束，紧后工序的开始时间要大于或等于紧前工序的完工时间；式（）表示一批工件一道工序的加工完成时间要大于或等于该工序的开始加工时间、辅助时间和该批次所有工件工时三者之和。双层搜索框架入侵杂草算法 算法概述 是一种模拟杂草种子空间扩散、生长、繁殖和竞争性消亡过程的智能优化算法，和其他进化算法相比，拥有更大的搜索空间和更好的鲁棒性与自适应性。曹磊等 针对存在异性质员工的多目标 构建了具有 学习效应的调度模型，并用杂草算法进行求解；等 针对无空闲流水车间调度问题，以最大完工时间最小化为准则，提 出 一 种 入 侵 杂 草 优 化 调 度 算 法；等 采用 解决 ，证明了 对求解 的可行性和优越性。的主要步骤如下：步骤随机生成初始种群，种群规模为 。步骤计算杂草的适应度值，生成相应数目的种子。步骤杂草种子按均值为、标准差为步长的正态分布进行扩散，并繁殖成新的杂草加入种群。步骤判断杂草种群是否达到最大种群规模 ，达到则将种群规模保持在 ，并将所有杂草个体按适应度值排序，选出适应度高的前 个个体组成子代初始种群，进入步骤，否则转步骤。步骤判断是否达到 的最大迭代次数，是则输出最优解，算法终止，否则返回步骤。为了更好地优化求解 ，本文设计了一种 ，主要改进如下：为了提升搜索的广度和深度，设计了一种双层搜索框架，其外层搜索主要通过分批约束方案产生合理的批次批量，为 提供初始解；内层搜索则通过 迭代优化得到最优的排序和机器选择策略。为了提升算法搜索能力并避免传统 容易陷入局部最优的缺陷，对传统 的优化过程进行改进，采用多邻域结构策略混合机床分配和分层选择法来提升组合策略的效果和种群的多样性，同时结合变邻域局部搜索避免 后期杂草种群陷入局部最优，并提升算法搜索能力。具体算法流程如图所示。可见本文设计的双层搜索框架策略，外层搜索主要是通过随机数字分割法得到具体的分批策略，在该分批策略下进行编码得到 初始种群，以此作为内层搜索的输入，而内层搜索则是以 为基础，深度搜索各分批策略下的最优调度方案，当算法陷入局部最优时，会进入变邻域局部搜索，依次通过个变邻域操作寻找较优值，各分批策略下的最优调度方案则作为内层搜索的输出，既避免了批量调度分批算法局部深度搜索不足的缺陷，也在一定程度上提高了 的全局搜索能力。编码与解码实现两层搜索策略的核心在于编码和解码。因为 可分解为个子问题，即各类工件批次的划分、各子批工件下工序的加工顺序、各子批工件下工序的机器选择，所以编码包括两个过程：（）批次划分，如图所示。本文设计了一种随机数字分割法来控制批次批量划分，将个工件通过个数字（如图中的斜线背景数字）分为批，数字即为对应批次的批量。在 中，由于存在工序紧前紧后约束，加工时长过长的工序容易导致紧后工序的加工机床闲置第期闫富乾 等：求解柔性分批调度问题的双层搜索框架入侵杂草算法等待和机床负荷不均；而在 中，将一批工件作为一个整体处理，单道工序时长成倍增长，会导致更为严重的机床闲置等待和机床负荷不均。为此，本文基于工件的平均工序时长，设计了一种分批约束方案：如果某工件的单工序平均加工时间 大于平均每个工件的单工序平均加工时间 ，则批次变量 （），分批数 量，；反 之，（），分批数量，。其中 表示最大分批数量，由决策者根据实际情况决定。假设有两类工件需要加工，工件共道工序，工序平均加工时长 ，工件共两道工序，工序平均加工时长 ，则平均每个工件的 ，设最大分批数量为，则批次变量，即工件的分批数量取值范围为，工件的分批数量取值范围为，。在该分批约束方案下，各类工件的分批数量能根据工序的加工时长自动调节，从而有效缩小分批范围，提高算法搜索效率，当工件的分批数量确定后，再随机生成维度为的单调递增整数向量，将个工件划分为不同批次。（）得到批次划分结果后，设计一种可变长度的基因编码来求解 。整个编码过程分为层，第层记录随机数字分割法得到的批次批量，第层为分批后各批工件工序的加工顺序，第层为各工序选择的加工机器，层编码中，不同种类工件的批次、工序加工顺序以及各自工序选择的机器均按工件编号排列，具体示例如图所示。图中共有类工件，每类工件设有两道工序、个工件，在分批层的编码中，个小格中的数字对应类工件的分批方案，第格中的数字表示第类工件被分为两批，第批为编号的个工件，第批为编号之后至编号 的个工件；第格中的数字 表示第类工件被分为批，第批为编号的个工件，第批为编号之后至编号之间的个工件，第批为编号之后至编号 的个工件；第格中的数字表示第批工件不分批，即 个工件作为一批。在工序层中，第个数字 计算机集成制造系统第 卷表示工件的第批的第道工序，第个数字 表示工件的第批的第道工序，各数字第几次出现即表示第几道工序。机器层中的数字表示各工序所选择的加工机器。解码过程分为两部分，首先对批次批量划分策略进行解码，得到每类工件具体的批次数和每批次的工件数；其次根据每道工序所选的加工机床计算该调度方案的 ，在计算每道工序的完工时间时，用该工序在所选机床上的加工时间乘以批量数，如果和机床上一道加工工序的工件种类相同，则不用计算辅助时间，否则需要计算辅助时间。种群初始化基于编码结构，的种群初始化需要产生层基因，其方式如图所示。在批量层中，在 节的分批约束方案约束下，通过标准正态分布随机产生各类工件的分批数和每批工件的批量数；在工序排序层，首先以标准正态分布产生一个随机数向量，该向量中各随机数大小不等，再根据随机数大小进行排序，最后将初始工序按随机数排序重排得到新的工序排列，其初始化流程如图所示；在机器层，本文设计了一种混合机床选择策略，即 个体为各工序选择可选机器中加工时间最短的机器，个体为各工序选择可选机器中已加工负荷最小的机器，其余个体随机选择可选机器中的机器。在该策略下，工序加工机器的选择不仅在满足优化目标的同时减少机器负荷，还保证了随机性，得到了更优的调度解，提高了种群多样性。基于变邻域的种群繁殖及扩散杂草繁殖的种子数由杂草个体的适应度决定，繁殖能力与适应度正相关可以保证适应性强的杂草生存下来，而本文 的目标为最小化 ，因此杂草的适应度值与其对应基因解码得到的完工时间负相关，即完工时间越小适应度值越高。杂草的种子数 （）。（）式中：，分别为杂草最大和最小可生成种子数；，分别为当前种群中的最大和最小杂草适应度值。在扩散过程中，各杂草种子需要成长为独立的基因个体，即在维空间内，通过父代变量值，（初始化中的随机数）加上一定随机步长值，生成子代向量，。各基因在维空间中服从均值为零且标准差为的正态分布，（）（）。（）式中：为 的最大迭代次数；为当前 的迭代次数；，分别为杂草种子的初始步长和最终步长；为非线性调节指