虚拟单元内外运输能力受限的异质并行机调度研究.pdf

第 卷第 期运 筹 与 管 理 ，年 月 收稿日期：基金项目：国家自然科学基金资助项目（）；江苏省研究生科研创新计划项目（）作者简介：高龙龙（），男，山东郓城人，讲师，研究方向：生产运作管理；韩文民（），通讯作者，男，江苏南京人，博士，教授，研究方向：工业工程与管理，人因工程。虚拟单元内外运输能力受限的异质并行机调度研究高龙龙，韩文民（江苏科技大学 经济管理学院，江苏 镇江 ）摘要：针对以往虚拟单元调度相关研究忽略了单元内外运输能力的限制、空载运输时间，以及对并行机的异质性考虑不够充分等问题，本研究以最大完工时间最小和总运输时间最短为目标，构建了虚拟单元运输组织与异质并行机调度联合决策模型，并提出了改进的 算法对模型进行求解。所提算法将粒子群算法与 的交叉、变异过程相融合，提高了算法的收敛速度。并将模拟退火算法的进化机制应用于 的变异过程，避免了 容易陷入局部最优的问题。通过小、中、大规模算例的仿真实验发现，所提算法与标准的 相比，算法的鲁棒性、收敛性和解集的质量、多样性等方面表现出较高的优势。关键词：虚拟制造单元；调度；生产物流；异质并行机；中图分类号：文章标识码：文章编号：（）：，（，）：，（“”），（），：；引言虚拟制造单元（以下简称“虚拟单元”）作为柔性制造的一个重要分支，近年来引起了许多关注。虚拟单元是指根据生产任务的相似性，并考虑各项生产条件或约束，从备选设备资源中选出需要的设备，组成逻辑生产单元，通过物流系统的连接，无需改变设备和资源的物理布局，而形成逻辑相互关联的虚拟动态生产实体，其具有减少生产准备时间和在制品库存，提高设备利用率等优点。虚拟单元多适用于大型复杂产品生产，其生产及物流组织复杂，工件的运输多采用平板运输车、行车、叉车等大型运输设备。由此可以看出，虚拟单元的有效实施，依赖于生产物流系统的有效流转，运输组织方式对调度方案的有效制定与实施具有重要的影响。但是，目前大部分虚拟单元研究对运输组织问题的考 虑 是 不 充 分 的。如 和 以总加工成本和单元内工件的平均加工时间之和最小为目标研究了虚拟单元构建、调度与布局问题。以最大完工时间和总运输距离之间的加权和最小为目标，研究了虚拟单元调度问题。在单元调度（设备物理位置可变的单元）和柔性作业车间调度中，有学者对该问题展开了进一步的讨论。曾程宽和刘士新 研究了运输空间约束下的多单元协作调度问题。等 研究了具有序列相关和单元间运输时间约束的单元调度问题。王亚昆等 考虑了设备间的运输时间因素，对柔性作业车间节能调度问题进行了研究。但是，以上这些研究都假定设备的运输能力是无限的，但该假设过于简单，脱离了生产实际。在现实生产环境中，工件的每一道工序完成加工后，存在部分运输设备被占用、运输设备无法在工件被完成加工后立刻或提前在当前加工设备前等待执行运输任务等情况，致使工件不能全部被立即运输。上述状况在大型复杂产品生产组织中表现得更为突出，这是由于其大型工件的运输准备及运输时间一般都较长，且由于运输设备大型化、价值高、所需作业场地大，这就使得这类企业车间运输能力受限的情况更为常见。因此，有必要研究在运输能力受限的情况下，运输组织与虚拟单元调度的交互影响，并进行相应的决策。针对该问题有部分学者展开了讨论。等 以最大完工时间最小为目标，研究了运输资源数量和能力受限的柔性作业车间调度问题。等 以设备加工与运输能耗最小和总加工时间最小为目标，研究了运输受限的柔性作业车间和起重机运输的绿色集成调度问题。等 研究了 能力受限的单元构建与调度问题。但是，上述研究大都忽略了空载运输时间（运输设备不运载工件时在车间内的移动时间）对生产调度的影响。在实际生产过程中，运输设备存在大量的空载时间，而该类空载时间影响了运输设备的循环使用和其可利用性，进而影响了生产物流的连续性和调度方案的制定与执行。因此，有必要将空载运输时间作为制约因素，研究运输能力受限的虚拟单元运输组织与调度联合决策问题。另外，目前关于虚拟单元并行机问题的研究，大部分学者都假定并行机的类型为一致并行机，即同一阶段上的并行机完全一致，具有相同的处理速度 ，。然而实际工业环境下，通常存在新老设备交替使用的情况。同时，虚拟单元多属于单件小批生产，设备的通用性较高，不同设备常可承担相同的加工任务，但其加工效率和工时耗费存在着差异性。通过以上分析可以发现，虚拟单元的有效实施，依赖于生产物流系统的有效流转。现有虚拟单元相关研究忽略了单元内外运输能力限制、空载运输时间等因素，对并行机的异质性考虑也够不充分。这导致所得到的调度方案往往与实际生产组运 筹 与 管 理 年第 卷织过程产生较大的偏差，甚至不可行。本文综合考虑以上因素，以最大完工时间最小和总运输时间最短为目标，构建了虚拟单元内外运输能力受限下的运输组织与异质并行机调度联合决策模型。同时提出了改进的 算法对所构建的多目标模型进行求解。所提算法将粒子群算法与 的交叉、变异过程相融合，以提高算法的搜索能力。并将模拟退火算法的进化机制应用于 的变异过程，以避免 容易陷入局部最优的问题。通过小、中、大规模算例验证所提算法的有效性。问题描述和模型构建 虚拟单元异质并行机调度问题描述虚拟单元异质并行机调度问题可以描述为：在加工车间中共包含 个虚拟单元，个待加工工件和 台加工设备。每个虚拟单元包含多台加工设备，承担特定工件族的工件的加工任务。一台加工设备可以属于多个单元，且设备的物理布局是已知的。每个工件在加工过程中包含了有限次、顺序一定的工序，每道工序只能在一台加工设备上完成加工，具有加工每道工序能力的加工设备至少一台。同一工序选择的设备不同，完工时间可能不同，每道工序在每台设备上的加工时间是已知的。每个工件族中的工件大部分工序都可以在所属的单元内完成加工。如果工件族中的某道工序无法在所处单元内完成加工，则需要在具有该工序加工能力的加工设备所属的单元进行加工，由此产生跨单元加工。具体假设如下：（）所有工件在 时刻都准备就绪。（）每个工件都有相同的优先级。（）车间内所有的加工设备在 时刻可用。（）同一时间内，每台设备只能加工一个工件。（）每道工序在加工设备上开始加工后不能中断。（）加工设备和工件所属的单元已知。虚拟单元运输组织问题描述虚拟单元运输组织的问题可被描述为：每个虚拟单元内有 台运输设备，虚拟单元内的运输设备除了完成本单元内的运输任务外，还可根据需要，完成本单元内工件的跨单元运输任务。车间内运输设备集中停放区域 个，以供车间内运输设备的停放。每个加工设备附近都有一个运输设备停放区域，以停放运行至该加工设备的运输设备。虚拟单元内的运输设备能力是有限的，部分工件被加工完成后，存在等待被运输的情况。具体假设如下：（）所有的运输设备在 时刻可用。（）每辆运输设备都有相同的优先级。（）每辆运输设备在同一时刻，只能运输一个工件。（）如果运输设备正在进行运输作业，则运输作业不能中断。（）虚拟单元内的运输设备，完成跨单元运输后，立刻返回距离所属单元较近的运输设备集中停放区域，除非当前任务的运输完成时间与该运输设备下一任务的空载开始时间相同。（）加工设备附近的运输设备停放区域，每次只可停放一台运输设备。（）运输设备完成当前运输任务后，距离下次被安排的运输开始时间超过返回集中停放区域的倍时，需要运输设备返回集中停放区域。否则，在当前加工设备附近的运输设备停放区域等待。（）当加工设备附近的运输设备停放区域被占用，导致后续运行至该加工设备的运输设备无法停放时，停放在该区域的运输设备需要返回集中停放区域。在实际生产过程中，运输设备在车间内的移动时间包括：运输设备实际运输工件的时间和空载时间。为了清晰区分在生产加工任务中运输设备的运输类型，以便在运输组织与调度联合决策模型中区别考虑，参考 等 的研究，将运输时间共划分为 种类型，即运输设备运行至工作地的空载运输时间、运输设备返回集中停放区域的空载运输时间和运输设备的实际运输时间。符号说明 为车间内待加工工件编号 ，；为工件的工序编号 ，（）；为车间内虚拟单元编号 ，；为车间内的加工设备编号 ，；为车间内运输设备集中停放区域编号，；为每个虚拟单元内的运输设备编号 ，；，；为在加工设备 上加工的工序编号 ，；为运输设备 上被安排的工序编号，。表示工件 的第 道工序；表示 的加工完成时间；表示 的加工开始时间；表示 在加工设备 上的加工时间；表示运输设备从加工设备 到 的运输时间；表示从加工设备到距离运输设备最近的集中停放区域 的运输时间；表示在虚拟单元 内单元内运输设备 ，空载至（）被安排的加工设备附近的运输设备停放区域，准备完成 运输的空载开始时间；表示在虚拟单元 内单元内运输设备 ，空载至（）被安排的加工设备附近运输设备停放第 期高龙龙，等：虚拟单元内外运输能力受限的异质并行机调度研究区域，准备完成 运输的空载结束时间；表示 由虚拟单元 内的运输设备 负责运输到下一工作地完成加工的实际运输开始时间；表示 由虚拟单元 内的运输设备 运输到下一工作地完成加工的实际运输结束时间；表示 由单元内运输设备 运输完成后，返回单元内设备集中停放区域 的空载开始时间；表示 由单元内运输设备 运输完成后，返回单元内设备集中停放区域 的空载结束时间。表示如果工件 属于虚拟单元 则为 ，否则为 ；表示如果 由虚拟单元内运输设备 负责运输则为 ，否则为 ；表示如果 在加工设备 上加工则为 ，否则 ；表示如果加工设备 属于单元 则为 ，否则 ；表示如果 在设备 上先于 被加工则为 ，否则 ；表示如果 是加工设备 上被安排的第 个加工任务则为 ，否则为 ；表示如果 在虚拟单元 中的运输设备 上被安排在第 个被运输则为，否则为 。目标函数和约束条件目标函数：（）（）（）（）（）（）约束条件：（）（）（）（）当 ，（）（）（）（）（）（）（）（）如果 （），或 （）（），如果 ，（）否则（）（）（），（）（）否则（）目标函数（）表示最大完工时间最小，目标函数（）表示总运输时间最短。约束（）表示 只能在一台加工设备上进行加工。约束（）表示一道工序的开始加工时间与完成加工之间的关系，且不可中断。约束（）表示工件的工序约束。约束（）表示工件的实际开始运输时间大于等于该工件上一道工序的加工完成时间。约束（）表示 的加工开始时间与实际运输结束时间之间的关系。约束（）表示 的空载结束时间与实际运输开始时间的关系。约束（）表示工件的实际运输结束时间与开始时间的关系。约束（）表示运输设备返回空载与实际运输结束时间之间的关系。约束（）表示每个工件的每道工序只能在一台运输设备完工运输。（）表示返回空载开始时间与结束时间的关系。（）表示开往工作地的空载开始时间与结束时间之间的关系。算法设计 算法在调度模型的求解方面展现出较大的优势，其主要原因在于 在全局搜索能力上表现出较高的优势。但是，也存在一定的局限性，如容易陷入局部最优和收敛较慢等问题。模拟退火算法具有很强的局部搜索能力，而粒子群算法具有操作简单，收敛速度快等优点。因此，将粒子群算法与 的交叉、变异过程相融合，以提高算法的搜索能力。并将模拟退火算法的进化机制应用于 的变异过程，以避免 容易陷入局部最优的问题。编码和解码在编码过程中，采用三层编码设计，第一层为工序层、第二层为加工设备层，第三层为加工设备所属的单元层。具体编码方式如图 所示。运 筹 与 管 理 年第 卷考虑到运输时间对调度的影响，具体解码方式为：从 时刻开始，根据染色体编码选取待加工工件的工序，若该工序所选加工设备被占用，则挂起该加工任务，直到被安排的加工设备被释放。根据公式（）计算当前工序的完工时间。当所有的待加工工件被挂起，则 时刻结束，令 。每个工件的第一道工序不需要被运输，运输时间为。在之后的每个时刻，遍历所有工件族中的待加工工件的工序。当 时刻，工件 的第 道工序被加工完成后，如果工件 的第 道工序在当前设备上加工，运输时间为 ；如果该工件的第 道工序在其它设备上进行加工，判断本单元内运输设备是否可用。如果运输设备不可用，则挂起运输任务，直到有运输设备可以执行该加工任务。如果运输设备可用，根据公式（），（）计算运输设备的空载时间，并向前插入，尽可能保证工件 的第 道工序被加工完成后，运输设备恰好到达工件 的第 道工序加工设备前，并根据公式（）计算当前工序的实际运输时间。如果单元内多台运输设备均可用，则随机选择一台运输设备完成当前运输任务。依次类推，直到所有工件所有工序被加工完成。图 染色体编码 选择、交叉与变异操作在选择过程中，选择二元锦标赛算法对种群进行选择操作。采用单点交叉和变异进行交叉与变异操作，在此期间，加工设备号与对应的加工设备所在的单元号一同变换。并将粒子群算法的更新规则融入到 的交叉、变异过程中，以提高遗传算法的收敛速度。具体见章节 。基于模拟退火的子代保留规则当子代为父代的支配解时，为了扩大了种群的多样性，避免 陷入局部最优。将模拟退火算法引入到 和粒子群算法的融合算法中改变子代保留规则。具体步骤如下：步骤 设定初温度 。步骤 通过遗传算法的选择、交叉、变异操作得到新的子粒子群。步骤 若产生的新子代是父代的支配解则以 （）接收形成新的子代，否则丢弃，其中，表示目标函数 的适应度值，表示接受概率。步骤 父代与子代合并形成新的种群。算法流程所提算法的总流程如下所示。步骤 随机化初始种群。步骤 对初始种群进行非支配排序，同时，找出全局最优个体。步骤 父代与全局最优个体交叉、变异生成一代子粒子群。步骤 设定退火温度 ，更新全局最优个体。步骤 各个粒子先后与全局最优个体进行交叉、变异操作。步骤 若子代为父代的支配解，执行基于模拟退火的子代保留规则；否则舍弃子代。步骤 对新的粒子群进行支配排序和计算拥挤度，并保留精英个体形成新的父代，更新全局最优个体。步骤 判断是否达到最大代数，若是算法终止，否则返回步骤 。数值仿真 算例及仿真数据与参数设置算例采用 等 的算例数据生成方式和所划分的单元，对所构建的虚拟单元内外运输能力受限下的运输组织与异质并行机调度联合决策模型及所设计的改进 算法，进行数值仿真和有效性验证。以小规模数据为例 表示车间有八个工件、八台加工设备、三个单元组成，中规模为 ，大规模为 。三种规模的工件族划分别为：小规模（，；，；，），中规模（，；，；，；，），大规模（，；，；，；，）。在移动距离生成方面，采用 等 的移动距离生成方式，运输距离属于 ，。为使所研究的虚拟单元内外运输能力受限下运输组织与调度联合决策问题既有典型性又不致过于复杂，第 期高龙龙，等：虚拟单元内外运输能力受限的异质并行机调度研究在算例中暂假设每个单元内运输设备为 台，运输设备集中停放区域 个。在算法参数设置方面，以反世代距离（）为评价指标，并采用田口实验 进行参数设置。由于，本算例获得真实的 解集比较困难。本研究采用所提算法与 算法得到的非支配解集作为真实的 解集，以对 进行计算。最终，得到的参数设置为：初始种群数 ，交叉概率 ，变异概率 ；并设置迭代代数 ，退火初始温度 ，常数 。计算 机 配 置 为：系 统，（）（），编程软件 。算法对比为了验证所提算法的性能，在同样的参数设置下，将其与标准 算法进行结果对比。评价指标选取大部分多目标算法评价常采用的覆盖率指标（）、分布性指标（）和综合指标 等三个指标 ，。在不同数据规模下，将每个算法均独立运行 次，分别计算出每个算法的三个性能指标的平均值。结果如表 所示。表 算法性能指标算例所提算法（）（）所提算法 所提算法 （，）（，）注：图中黑色矩形框代表工件的实际运输时间；代表该工序被安排的加工设备，代表该设备所属的单元图 所提算法（）甘特图通过覆盖率指标来看，所提算法的 测度值均大于 ，说明所提算法相较于 能获得更好的解。尤其在中、大规模问题中，所提算法的 测度值明显优于 算法，说明在中、大规模问题中所提算法具有明显优势。同时，算法的性能不受数据规模的改变而改变，具有较高的鲁棒性。从分布性指标来看，所提算法的分布性值更小，说明所提算法具有更好的搜索能力。同时，随着问题规模的增大，所提算法的分布性指标逐渐变小，说明其搜索能力对大规模问题更强。其原因在于 与模拟退火算法的结合增强了算法的全局和局部搜索能力，避免了 容易陷入局部最优的问题。从 指标来看，所提算法在收敛性上具有较高的优势。另外，从运算时间上来看，所提算法在三种规模下的平均运算时间分别为 ，要 明 显 优 于 算 法 的 ，。这就说明 与粒子群算法的融合提高了算法的收敛速度。综上，所提算法明显提高了 算法的综合性能。小规模算例所得到的甘特图如图 所示。运输距离大小灵敏度分析为了分析运输距离大小的变化和运输能力对调度结果的影响，采用 等 所采用的三种运输运 筹 与 管 理 年第 卷距离生成方式对运输距离和运输能力对虚拟单元生产调度结果的影响程度进行分析。在每种数据规模下，采用所提算法分别运行 次得到的运输距离大小对平均最大完工时间的影响曲线如图 所示。从图 可以看出，随着运输距离的增大，工件的最大完工时间逐渐增大。同时，随着问题规模的增大，运输距离对调度结果的影响越大。从运输能力来看，运输能力受限情况下的最大完工时间相较于运输能力充足下的最大完工时间具有较大的差异性。因此，在大型复杂产品加工调度方案制定过程中对运输时间和运输能力的考虑是非常必要的。图 不同运输距离和运输能力下的最大完工时间平均值 结论本文综合考虑虚拟单元内外运输能力受限、空载运输时间和异质并行机等因素，研究了虚拟单元运输组织与异质并行机调度联合决策问题。所构建的虚拟单元运输组织与调度联合决策模型更贴合企业生产实际。同时，提出了基于 、粒子群算法和模拟退火算法的融合算法来对模型进行求解。通过小、中、大规模的算例测试来看，所提算法的鲁棒性、收敛性和解集的质量、多样性等方面表现出较好的优势。在实际生产中，相同运输距离下，不同工件的运输时间可能存在一定差异性，且每个工件加工和运输任务的优先级也可能不同。在未来的研究中，可以进一步提高算法的求解能力，同时将不同工件的运输组织方式的差异性、每个工件加工和运输任务的优先级等因素纳入到虚拟单元内外运输组织与异质并行机调度联合决策问题中进行考虑。参考文献：，：，（）：曾程宽，刘士新 求解存在运输空间约束多单元协作调度问题的拍卖算法 控制与决策，（）：，（）：王亚昆，刘应波，吴永明，等 改进 算法求解考虑运输约束的柔性作业车间节能调度问题 计算 机 集 成 制 造 系 统，：，（）：，：，（）：，：，：，：，（）：，：姚远远，叶春明，杨枫 双目标可重入混合流水车间调度问 题 的 离散 灰 狼 优 化 算 法 运 筹 与 管 理，（）：第 期高龙龙，等：虚拟单元内外运输能力受限的异质并行机调度研究