存在设备时间限制的两个企业协同的综合调度算法

谢志强 裴莉榕

(哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080)

1 前言

随着工业经济的发展，建设高水平开放式区域协同创新体系成为工业经济发展的重中之重。企业协同随之成为企业发展必须解决的问题。企业之间通过信息共享，从而实现加工任务在合作车间之间的相互协调和交换，从而相互代为完成加工任务，使企业更大限度地完成一些不能独立完成的任务，最大限度地减少设备空闲时间，提高设备的使用率，提升企业收益，扩大企业规模。为此，协同加工更符合现阶段生产需求。关于车间调度问题的研究，从车间类型分析，分为流水车间[1]和作业车间[2]。从车间数目分析，分为单车间和多车间[3]。从加工设备属性分析，分为柔性车间[4–6]和非柔性车间。从目标数量分析，分为单目标和多目标[7–9]。随着产品复杂度变高，单车间制造已经无法满足现阶段的需求。为此，在单车间调度的基础上，众多学者对多车间以及分布式车间制造进行了深入的研究，并取得了相应的成果[10–15]。

以上这些研究都是将产品分化成零部件，将零部件进行分批次加工，加工完成后再进行组装，属于流水线工程，并没有考虑针对于单件复杂产品加工时，工序之间存在约束关系，将加工和装配并行进行，从而实现缩短加工时间以及减少加工成本，提升产品的生产效率。于是，谢志强等人[16–19]提出了一系列综合调度问题。关于综合调度问题的研究，从产品角度分析，包含一般产品综合调度问题和特殊产品综合调度问题。一般产品综合调度问题又分为单产品综合调度问题、多产品小批量综合调度问题。特殊产品综合调度问题分为工序紧密衔接调度问题和工序非紧密衔接调度问题。以上对于综合调度的研究大部分为单一企业内部车间问题，也就是一个企业内工件在单个车间或多个车间进行加工引发的一系列问题。文献[20]提出的基于混合教学优化算法的多车间协作综合调度，虽然提出了车间协作问题，但只考虑多车间设备集的交集部分且对于迁移问题的考虑固定且单一，并没有实质上的解决车间协作的问题。而针对企业车间协同问题研究较少，企业协同主要是分为两种，一种是自有加工企业设备使用时间存在限制，导致加工任务不能如期完成；另一种是存有特殊工序在特殊设备上进行加工，自有加工企业缺少该工序所需加工设备。上述两种情况使得自有加工企业都必须寻求其他加工企业进行辅助加工，从而完成加工任务。而在实际生产过程中，由于加工设备的定期维护会出现设备的正常使用时间存在极大的限制。因此，提出的存在设备时间限制的两个企业协同的综合调度算法即是针对企业车间协同问题中自有加工企业设备使用时间存在限制的综合调度问题进行进一步的分析和研究。设计加工任务分配策略保证了自有加工企业获得更多的收益，设计原加工企业工序车间选择策略和协同选择策略，在考虑到运输问题并满足交货期的前提下选取获得收益更大的协同加工企业。经过实例分析，该算法可以更好地解决加工企业由于设备使用时间的限制并带有交货期和收益的企业车间协同综合调度问题。

2 问题描述分析

综合调度问题既不仅考虑了产品的加工问题，同时也考虑了产品的装配问题。在实际的生产中，通过企业之间的信息共享，实现产品加工任务在合作车间之间的相互协调和交换，相互代为完成任务。协同加工不仅能够减少设备空闲时间，提高设备的使用率，同时能够提升企业的经济效益并增大企业收益。协同加工通常是由两种情况引起的，一种是自有加工企业设备使用时间存在限制，导致加工任务不能在交货期内完成；另一种是存有特殊工序需要在特殊设备上进行加工，自有加工企业不存在该工序所需加工设备，这两种情况使得自有加工企业都必须寻求其他加工企业辅助加工，从而完成加工任务。协同加工以往的模式是将企业任务信息，设备信息等所有信息集中处理，进行资源优化。但是这种方式数据量过于庞大并且在处理数据的过程中由于冗长的环节致使企业信息泄露对企业造成不可估量的损失。为此，提出存在设备时间限制的两个企业协同的综合调度算法需要满足以下要求：

(1)订单共享中心的任务不强制分配给各加工企业，各加工企业可自由选择。

(2)各加工企业提交协同意向后，并不表示合作达成。需要协同分配中心确定并签订合作达成意向书后，方可证明合作成功。

(3)任务共享中心中的任务会随时更新，但达成协议的任务不可毁约，协议达成立刻生效。

(4)因两个加工企业间协同任务引起的运输费用，由两个加工企业协商决定分配比例。

(5)现以最理想的模式分析，运输所消耗的时间和成本固定且模式单一，不会受到外界环境影响。

(6)由于是协同合作，所以各加工企业不可能存在无限制的加工，各加工企业车间设备加工有时限。

(7)各协同加工企业达成协议之后，必须按照其限定时间内完成加工，不受其他因素影响。

(8)各加工企业设备属性值均在正常范围内，不会出现超负载或损坏等问题。

(9)各加工企业设备为非柔性设备，加工工序和设备型号为一对一的关系。

(10)企业内部各加工工序在各设备间移动所消耗的时间和费用存在且固定不变。

(11)加工工序之间存在工艺约束，必须在其紧前工序全部加工完成后方可加工。

(12)设备在加工过程中不存在临时插入，必须加工完当前工序方可加工下一道工序。

(13)产品加工完成之后，直接送往管理中心，运输费用由自有加工企业承担。

利用数学的方式描述该调度问题，对所有相关的变量进行如下定义：

J表示所有工序即工序集，单件复杂产品存在n道工序，J=J1,J2,···,Jn。

B表示所有加工车间即车间集，共存在L个车间，B=B1, B2,···,BL。

存在设备时间限制的两个企业协同的综合调度算法的目标函数可定义为

其中，式(1)表示自有加工企业在该任务中获得的最终收益。式(2)表示的是交货期约束。式(3)和式(4)分别表示自有加工企业和协同加工企业的收益约束，各参数含义如表1所示。

表1 各参数含义

3 算法详细设计

近年来由于协同算法的提出，如何在保证商业信息安全的前提下，将不同区域内的加工企业建立合作并合理地分配加工任务，使企业获得更多的收益成了解决问题的关键，且该算法不受企业规模所影响。其主要步骤如下：

(1)需要自有加工企业将边际收益较低的任务或是不可独立完成的任务发送到任务共享中心。

(2)设备存在闲置的企业根据任务共享中心的信息提出协同意向及自身加工车间现况以及物流等信息。

(3)协同分配中心将各加工企业的协同意向进行合并处理，整理出方案列表，并反馈给自有加工企业。

(4)自有加工企业根据方案列表中的信息，选取心仪的方案，并确定合作意向，并将合作意向反馈给协同分配中心。

(5)协同分配中心确定双方合作意向达成。并回到步骤(2)，直至所有任务最终分配完毕。

3.1 加工任务拆分策略

为了保证自有加工企业能够获得更多的收益，需要将加工任务尽可能多的分配给自有加工企业进行加工，因此，需要将加工任务进行有效分解并设计了加工任务分配策略。加工任务分配策略主要分为初始拆分和拆分调整两大步骤，以图1加工树为例对其进行初始拆分。节点信息为工序号/设备号/加工时长(h)。

图1中箭头所指方向为该工序的紧后工序，以往的计算路径长度的方式都是从根节点开始，计算根节点到该节点的路径长度为该节点的路径长度值。采用逆向思维方式进行剪枝从而生成初始拆分树，具体步骤如下：

图1 加工树例1

(1)输入加工树中各节点信息。

(2)标记各节点层数。加工树共有C层，根节点层数为1，依次递增，最后1层层数为C，按层遍历加工树。

(3)判断该工序是否有紧前工序，若不存在紧前工序跳到步骤(4)。若存在紧前工序跳到步骤(5)。

(4)计算各工序路径长度，路径长度=max{紧前工序路径长度+当前工序加工时长}。

(5)标记各工序路径长度。

(6)判断加工树中是否存在未标记工序，若是转到步骤(3)，若否转到步骤(7)。

(7)按后序遍历的方式将加工树中路径长度小于设备时限的工序进行剪枝。

(8)建立虚拟根节点，将剪枝下的工序重新构建成一棵加工树，即初始拆分树。

按照初始拆分的步骤，首先逆向计算各工序的路径长度，并进行标记，如图2所示。以工序J8为例，工序J8存在3个紧前工序，最大紧前工序路径长度与自身加工时间加和结果为J8的路径长度。以加工时长为13作为设备加工时限，将所有路径长度小于13的工序和子树进行剪枝。带虚线的工序为被剪掉的工序。

将图2中虚线圈出的工序进行剪枝，然后建立虚拟跟节点，构建拆分树，生成初始拆分树，如图3所示。

图2 标记加工树

图3 初始拆分树

在实际调度过程中设备总时长会受工序中关系约束和迁移约束影响且加工设备存在时间限制，所以首次拆分后产生的初始拆分树在实际操作过程中，并不一定能够满足时间限制约束。因此需要对拆分树中的工序进行调整，在对初始拆分树进行微调整的过程中，需要对树中各工序确定加工车间。判断是否存在超时工序，若存在超时的工序，将超时工序从拆分树中删除，并添加到协同加工树中。由于初始拆分树是从自有加工工艺树剪枝后合成的，所以存在纯叶子节点，即该工序不存在紧前工序且优先级值为1。

3.2 原加工企业车间选择策略

可调度工序存在紧前工序和紧后工序，由于存在多个车间且每个车间包含的加工设备型号不一致，将所有设备统一在一起，计算各型号设备个数，存在个数为1的设备，标记为特殊设备，当存在工序加工设备为特殊设备时，标记Di=1，否则为0。用二进制形式标记各工序加工设备所在车间，假设，存在3个车间B1,B2,B3，车间B1包含设备D1,D2,D4，车间B2包含设备D2,D3，车间B3包含设备D3,D4，工序i可以在设备D3上加工。则用二进制表示为011。若其紧后工序i+1所用设备为D2，则用二进制表示为110，将两者进行“&”运算得出结果为010，可以确定可共用车间为B2。工序车间选择具体步骤如下：

(1)将初始拆分树中非纯叶子节点的各工序信息输入。

(2)用二进制形式标记各工序加工设备所在车间，并对在特殊设备上加工的工序标记Di=1。

(4)建立虚拟加工工序，模拟工序迁移情况，并计算工序在其加工设备所在车间的最早开始时间，若最早开始时间相同转到步骤(5)，若最早开始时间不相同，选取最早开始时间最早的车间，转到步骤(8)。

(5)查看该工序紧后工序二进制值进行“&”运算，确定结果为1的车间，并记录车间数CB。

(6)判断CB值是否为1。若为1，将该工序安排在该加工车间，转到步骤(8)，若不为1，转到步骤(7)。

(7)判断不同车间内该工序所需设备上的空闲时间段，选取空闲时间段小的车间。

(8)将该工序从工序集中删除，判断工序集是否为空，若工序集为空，输出甘特图，转到步骤(9)，若工序集不为空，转到步骤(3)。

(9)将补入集中纯叶子节点输入，查找空闲时间段，利用考虑无缝拉伸的多设备紧凑优化调度策略将纯叶子工序插入。

(10)判断插入后是否超时，若不超时，转到步骤(11)，若超时，转到步骤(12)。

传统制造业习惯于在遇到管理问题时，通过成立专门应对部门的方法来解决，这就导致各个层级的管理部门越来越多，组织机构错综复杂，管理权限界定不明确，往往老的问题还没有解决，新的衍生问题又浮出水面。

(11)输出该工序。

(12)从补入集中删除该工序，判断补入集是否为空，若为空，转到步骤(13)，若不为空，转到步骤(9)。

(13)输出甘特图，结束。

3.3 协同车间选择策略

对于每个企业来说，可以将边际效益低或无法独自加工完成的任务发送到共享中心中寻找协同企业进行加工合作，挣取对应收益，而自身获取收益的高低则是选择合作伙伴的关键。由此，对于协同任务的分析变得尤为重要。加工树经过拆分后生成自有加工企业加工的拆分加工树，而其余部分为协同加工企业加工的协同加工树。为了使自有加工企业在满足交货期的前提下，获取最大的收益，需要对协同加工树分析，确定协同加工企业所需设备的最低要求，以及在存在运输问题的情况下，加工任务能够在交货期内完成。主要从以下4个点进行分析，设备型号、协同车间最大加工时间、设备数、收益。详细流程图如图4所示。

图4 协同选择策略流程

(1)设备型号是根据协同加工树中各节点信息确定协同车间需要的设备型号。

(2)协同车间最大加工时间是根据各企业之间的实际地理位置建立数据库，确定运输时间Tv以及协同车间到管理中心的时间Tm，由于拆分树已知，且在拆分树调整过程中便可得到对应的甘特图，从而得到原加工车间加工时间To，利用公式Ts= TQ–(To+Tv+Tm)，得到协同车间最大加工时间Ts。

(3)设备数是假定同型号设备数目为Dw=1，w表示型号标号，以协同车间最大加工时间Ts为时间限制，调用拆分树调整算法对协同加工树进行分析，标记存在延迟的工序，判断是否存在工序加工时间超过Ts。对超过Ts工序及其紧前工序集中发生延迟的工序时长进行分析，寻找对应型号设备并将设备数目加1，输出各型号设备数。假定工序J1的紧前工序为J2,J3，工序J2的紧前工序为J4，存在3种型号设备D1,D2,D3。

假定工序调度后的甘特图如图5中下半部分，虚线为时间线，当工序J1超时，首先判断超时工序是否为延迟工序。J1为延迟工序。增加该工序所用设备，重新调度判断是否超时，图例中刚好未超时。假若重新调节后工序仍然超时，判断其紧前工序集中工序所在设备是否需要增加，如图6所示。J1仍为超时，查询延迟时间最大设备，增加该设备数，新调度判断是否超时，直到不存在超时工序或不存在延迟时间。

图5 协同加工树调度甘特图

图6 增加设备后对比甘特图

(4) 收益是由于各车间情况基本确定，且对应的运输情况也已知，便可以获得相关费用信息，利用公式R=Ro–(Fo+αFv+Fm)确定不同企业协同合作下的收益，最终以收益最大值为协同加工企业。

4 实例分析

算法可以用于复杂的单产品，为了便于理解，实例用较为简单的产品工艺树进行分析。模拟其中数据并以图7所示加工树为实例，图中工序信息为工序号、设备号、加工时长。从叶子节点开始，逆向计算各工序路径长度，假定以时长20 h为限，对加工树进行剪枝，如图8所示。

图7 加工树实例

图8 标记加工树

构建虚拟根节点，将剪枝下的树和节点中不存在紧后工序的节点与根节点建立连接，如图9所示。

图9 初始拆分树

从根节点开始，正序计算各工序路径长度并标记其层数，不存在紧前工序的节点为叶子节点。将不存在紧前工序且层数为1 的纯叶子节点即{J7,J15,J16}放入补入集。如图10所示，深灰色填充的工序为纯叶子节点。将除纯叶子节点以外的叶子节点工序放入工序集。虚线画出的节点为叶子节点。

图10 标记初始拆分树

得到工序集{J28,J27,J26,J24,J23,J22,J21,J20,J18,J9}，路径值最大工序为J20，路径长度为19，加工设备为D4，设备对应工序备选集为{J27,J20}，最大层数工序为J27，输出J27，设备D4为特殊设备，将工序J27安排在车间B2中，记录开始时间和结束时间(0 ,2)，将J27从工序集合备选集中删除，产生新叶子节点工序J19，设备为D3，将工序J19加入工序集，工序J20未输出，备选集中工序为{J20}，个数为1，直接分配J20车间为B2，记录开始时间和结束时间(2,7)，将J20从工序集和备选集中删除，备选集中工序个数为0。不断更新循环得到的甘特图如图11所示。输入补入集工序{J7,J15,J16}，工序J7所用设备为D2，工序(J15,J16)所用设备为D3，利用无缝拉伸的多设备紧凑优化调度思想，将工序{J7,J15,J16}按加工时长依次插入，插入后未发生超时，插入后甘特图如图12所示。

图11 初始拆分树调度发生超时甘特图

图12 纯叶子节点插入后对比甘特图

文献[17]中涉及交货期问题，但针对的是多产品小批量问题，基于此，假定产品优先级为1，迁移时间同表2所示，阈值仍为20，利用文献[17]中的算法调度后的甘特图如图13所示。通过计算可知，算法在阈值内可加工20道工序，加工总时长为85.8 h，而文献[17]中的算法在阈值内可加工14道工序，加工总时长为65.8 h，相差6道工序和20 h。对比结果可得，算法对于求解加工企业设备使用时间存在限制并带有交货期和收益的企业车间协同综合调度问题能够得到优良结果。说明了算法的有效性，相较已有文献[12]中的算法具有一定的优越性。针对协同加工树进行分析确定加工设备型号。经过调节后，最终形成的协同加工树，协同加工树仍然需要4种型号设备D1,D2,D3,D4，利用长路径、层优先和短用时策略对协同加工树进行调度，形成图14所示甘特图。

表2 企业内部设备迁移信息 (h)

图13 文献[17]调度甘特图

图14 协同加工树调度甘特图

假定交货期TQ=60，利用协同选择策略发现存在3家企业符合要求，时间未超过交货期，由于图例较为简单，恰好未存在延迟工序且不存在超时现象，故不存在可增加设备，只需考虑运输问题。假定3家符合条件的协同企业P1,P2,P3，相关信息如表3所示。

表3 协同加工企业相关信息

假定α取值为0.5(具体取值根据实际合约情况决定)，Ro=150,Fo=50,To=19.6。利用公式R=Ro–(Fo+αFv+Fm)和TQ=To+Ts+Tv+Tm计算得到如下结果：R1=80.0, T1=54.9, R2=82.25,T2=56.5, R3=81.91, T3=58。由此可以看出，在未超过交货期的前提下，盈利最多的是P2，故选择协同加工企业P2进行合作。

5 结束语

(1) 相比以往的研究，本文首次提出解决两个企业车间协同合作问题的方法，通过对比收益值能够更加直观反应企业收益。较比单一多车间加工与单一分布式车间加工的加工方式，协同加工合作能为加工企业取得更多的盈利。

(2) 将工序在多车间迁移问题和产品在两车间的运输问题以具体数值进行分析，提高了结果准确性。

因此，提出的存在设备时间限制的两个企业协同的综合调度算法，可以更好解决加工企业设备使用时间存在限制并带有交货期和收益的企业车间协同综合调度问题，使企业更大限度地完成一些不能独立完成的任务，最大限度地减少设备空闲时间，提高设备的使用率，提升企业收益，扩大企业规模。对企业协同综合调度问题的进一步研究具有一定的意义。