虚拟制造单元条件下考虑资源柔性的资源冲突检测与消解

吕 洁，赵金涛，韩文民

LV Jie, ZHAO Jin-tao, HAN Wen-min

（江苏科技大学 经济管理学院，镇江 212003）

0 引言

虚拟单元制造（Virtual Cellular Manufacturing，VCM）是在逻辑上对资源进行的动态配置和重置，不需在物理位置上进行重新安排[1]。VCM结合了单元式布局的调整时间高效性以及工艺化布局的路线灵活性[2]。在常规生产系统中，当完成生产计划后，根据系统中的设备能力根据静态调度方法进行资源平衡，从不同调度规则中选取最优调度策略，并得到最终调度结果。如果整个过程能按计划进行，那么这是提高系统效率和设备利用率的理想办法。但由于虚拟单元制造（VCM）环境中的复杂性、动态性和突变性，在调度的实施过程中可能出现多种突发情况并引起资源冲突问题，当在生产过程中有临时需插入的急件或某设备发生故障时，就可能引起资源的冲突[3]。虚拟单元中通常包含柔性资源，冲突发生时的外在表现是资源的冲突，实际上是同时使用资源的某种功能造成的冲突。当资源冲突出现时，明晰冲突发生的类型，对发生的冲突进行及时识别和消解有很大的现实意义。系统效率和稳定性通常会表现出一定的矛盾[4]。在实际生产中，反复调整调度计划会扰乱生产的实施，因此，冲突消解应兼顾效率和稳定性。

目前，一般生产条件下的资源冲突检测与消解方法已有部分研究。乔立红 、王超针对多级协同项目中的资源冲突问题，利用基于时间约束网络的冲突检测算法实现了多级协同项目中的资源冲突检测，该算法建立了任务关系的时间约束网络模型[5]。杨萍基于Agent协商理论，从资源最优配置的角度，论证了最优的协商策略，提出了可重复利用的不可分享型资源的冲突消解算法，但没有说明冲突识别的机制，而且在确定任务优先级时需要设置参数，不能完全反应生产系统的真实性[6]。黄喜等提出了一种基于时间约束网的项目冲突识别方法，运用时间约束网络对项目实施过程中的冲突展开研究，建立了项目实施网络，并对项目冲突进行了定量分析，提出基于时间约束网的项目冲突识别算法。但没有考虑多个资源的情况[7]。针对项目进度问题，尚志在关键链管理方法和贝叶斯网络模型的基础上，提出了关键链项目管理的贝叶斯网络模型（CCPMBN） 。并给出了CCPMBN的定义，描述了模型中的节点、有向边以及节点的条件概率分布；然后，提出了以贝叶斯网络为基础的关键链工序分解方法及建模方法；最后，证明了该模型在项目进度管理方面的应用前景。但没有给出具体的冲突识别和消解方法[8]。宋海权提出了混合Petri网模型及冲突判断的规则，然后根据规则对Petri网进行冲突检测，并得到考虑优先级的消解方案。但没有考虑可替代路线的情况[9]。F. Liang, Baykasoglu et al. 指出基于资源要素的能力分析在为某加工工序选择可替代设备时更具灵活性[10,11]。Saad et al.采用资源要素法对CMSs进行重构[12]。F. Liang研究了在VCM系统中基于资源要素法的资源建模和效果分析，提高了制造系统的灵活性和适应性，但未运用于冲突消解中[13]。从上面的研究中可以看出，针对虚拟制造单元冲突检测和消解过程中关于资源柔性、路径柔性的考虑不足。

本文提出了以制造系统生产过程稳定性和高效率为目标的资源冲突检测和消解机制。首先，在冲突检测阶段，将可能发生的冲突类型分为两种：强冲突和弱冲突，根据各个工序的加工计划将调度期划分为若干时间段，以时间段为单位进行冲突识别；在冲突消解阶段，对不同类型的冲突采取不同的消解策略，若所有时间段内不含强冲突，只需调整存在弱冲突时间段内的任务安排，无需对整个调度期重新安排，这在保证工期不发生延迟的情况下提高了生产系统的稳定性；当出现强冲突时，采用改进的遗传算法对调度期内的所有工序进行重调度，以保证完工时间不会出现延误或使延误最小化。通过实例和仿真表明，本文提出的冲突识别和消解方法能够在兼顾生产系统过程稳定的同时保持生产的高效率。

图1 虚拟制造单元资源冲突检测与消解模型

1 基于资源要素法的冲突检测

定义一：多个任务在同一台设备上存在时间重叠，则存在使用该设备资源的冲突；若在不改变计划加工时间（如：工序ojh的计划加工时间Ti=[ti,ti+1]）的前提下，通过更换其他设备可以消除冲突，那么该冲突为弱冲突，否则，称之为强冲突。

根据初期调度计划中时间节点，按先后分为若干时间段，如：Ti=[ti,ti+1]；经过分析所有时间段内设备上不同加工工序是否存在时间上的重叠，判断存在资源冲突的时间段；然后对存在冲突的时间段进行冲突类型的识别；若存在某时间段是强冲突，那么，该调度期内的资源冲突类型为强冲突，否则为弱冲突。 其中，对调度期内的冲突类型作出判断是资源冲突检测的关键，其判断流程如图2所示。

图2 资源冲突类型判别流程

1.1 基于资源要素法的设备能力分析

在资源要素（Resource Element,RE）理论中，资源要素是机械加工设备特有的能力单位，最早是用来定义机器设备的共有和独有能力，并用来辅助车间分布式布局的一种方法[12]。把设备的切削成形模式叫做Form Generating Schema（FGS），具备一定关系的多种FGS集合叫做一个资源要素，这三者间的关系如图3所示。

表1给出了例子阐明FGSs与设备间的关系，包括5台机器和7个FGSs。每一列需要与所有未聚集的列相比较。在这一表格中，第1列与第4列相同。因此，F1和F4构成第一个RE，第二列与第三列相同，F2与F3聚集在一起生成第二个RE。以这种方式F5和F6构成第三个RE，最后F7表示最后一个RE。

表1 设备--FGSs矩阵

1.2 资源冲突类型的判别步骤

下面给出了某一时间段[ti,ti+1]内的资源冲突判别步骤：

步骤1：定义二：设集合A，B，C，D，如果A⊂ C，B⊂C，C⊂D，A⊄B，B⊄A，那么称A、B为一级集合，C、D分别为二、三级集合。

步骤2：包含资源要素ri的资源要素设备集用Mi=（mi,mj,mk,…,ml）表示，根据第二步中集合间的关系，对资源要素设备集Mi进行级别分类，并令资源要素ri的级别对应资源要素设备集Mi的级别。

步骤3：首先对一级资源要素进行检测，根据该级别下的各资源要素需求数量，在该级别设备集下遍历所有可能（每当对某资源要素分配某种设备时，就需要对含该设备的资源要素设备集更新，在更新后的资源要素设备集中去掉该设备），若不存在一种满足各资源要素需求的情况，则存在强冲突，输出强冲突并终止；否则，输出使用该资源要素的设备分配方案并转下一步。

步骤4：对下一级资源要素使用情况进行检测，方法同上一步。直到完成对所有层级资源要素的检测。

步骤5：汇总步骤3中得到的资源要素设备分配方案，得到该时间段内的可行调整方案Qj。

2 资源冲突的消解

2.1 弱冲突的消解

在调度期的所有时间段中都没有出现强冲突，则只需对其中出现弱冲突时间段内的任务工序进行调整，在1.2节资源冲突类型的判别中，输出了消除时间段内弱冲突的设备调整方案Qj，调度期内的弱冲突消解方案即为时间段内弱冲突的设备调整方案的集合{Qj}。

2.2 强资源冲突消解的数学模型

当存在强冲突时，需要找出未完成任务的调度方案来消除冲突。调度问题可描述为：n个工件在m台设备上加工；每个工件包含一道或多道工序；工序顺序是预先确定的；每道工序可以在至少一台机器上加工；调度目标是确定每道工序的加工机器，以及每台机器上各工序的加工顺序和开始时间，使系统的生产总流程时间最小。

符号说明：

n：工件总数；

m：机器总数；

hj：第j工序的工序总数；

ojh：第j工件的第h道工序；

Mijh：第j工件的第h道工序在机器i上加工；

pijh：第j工件的第h道工序在机器i上的加工时间；

sjh：第j工件的第h道工序加工开始时间；

cjh：第j工件的第h道工序加工完成时间；

L：一个足够大的数；

cmax：最大完工时间。

目标函数：

满足以下约束条件：

其中：i=1,2,…,m; j=1,2,…,n; h=1,2,…,hj。

其中：j=1,2,…,n; h=1,2,…,hj-1。

其中：j=1,2,…,n。

其中：j=0,1,…,n；k=1,2,…,n；h=1,2,…,hj；l=1,2, …,hk；i=1,2,…,m。

其中：j=1,2,…,n；k=0,1,…,n；h=1,2,…,hj-1；l=1,2, …,hk；i=1,2,…,m。

其中：h=1,2,…,hj；j=1,2,…,n。

其中：j=0,1,…,n；h=1,2,…,hj。

式(1)和式(2)表示每一个工件的工序先后顺序约束；式(3)表示工件的完工时间的约束；式(4)和式(5)表示同一时刻同一机器只能加工一道工序；式(6)表示的是机器约束，即某一时刻某一工序仅能被一台机器加工；式(7)表示各个参数变量必须是正数。

3 改进的遗传调度算法

遗传算法（GA）在1975年由美国Michigan大学的John Holland教授首先提出，是一种模拟生物进化的优化算法。遗传算法是一种通用的优化算法[14]，优化过程不受限制性条件的约束，能够在复杂空间中进行全局优化搜索，并具有较强的鲁棒性。染色体编码过程是将问题的解用染色体的形式表示出来，是该算法的关键。本文采用整数编码，可满足调度规模变化的情况，也保证了交叉、变异时产生的是可行解，提高执行效率。

本文中的冲突消解调度过程包括两个子问题：机器选择和工序排序。本文结合了分段编码易操作、易表现等特点对普通编码方法进行改进，设计一种整数编码（MSOS）方法。染色体由两部分组成：机器选择部分（MS）及工序排序部分（OS），染色体的结构如图4所示。机器选择部分的染色体长度为所有任务的工序数之和T0，每个基因用整数表示。按任务的工序顺序排列，每个整数代表当前工序所选的机器在可选机器集合中的顺序编号，而不是机器号。工序排序部分染色体长度也是T0，每个基因用任务号编码，任务号出现的顺序表示该工序工序间的先后顺序。

图4 染色体编码

4 案例分析

AEF公司电梯产品中的核心部件是PM曳引机，该公司曳引机目前共有四个品种，每个品种根据电梯速度、载重量的不同，选配的曳引轮、制动器、电磁线圈的规格型号都不尽相同，形成了PM曳引机拥有四个品种，二十几种型号的产品组。根据不同订单的要求，所需生产数量和型号是不断变化的。传统的单元生产不能很好的应对这一情况，虚拟单元以生产任务为中心，根据生产任务的不断变化来调整生产计划或是生产过程中的调度方案，从而能够及时的满足生产要求。本文选取了PM曳引机组件的零部件加工车间中10个具有代表

单元内作业工序分别是O11-O12-O13,O21-O22-O23,O31-O32-O33，并在时间t=3时，加入了新任务O*，并有设备m1从单元中分离出去。设备信息如前表1所述，经过能力分析得出设备-资源要素矩阵（如表2所示），下面是加工任务的资源使用计划表（如表3所示）。

表2 设备-资源要素矩阵

表3 加工任务的资源使用计划表

根据调度计划表4将时间划分为t1=[1,2]，t2=[2,3], t3=[3,4]，t4=[4,5]，t5=[5,6]五个时间段。经过冲突识别后得出：t1时间内不存在资源冲突；t2时间内存在弱资源冲突，并同时得出该时间段的弱冲突消解方案：O11-r1-m1，O32-r2-m2，O22-r3-m3；在t3时间内存在强资源冲突。

因此，采用强冲突的消解策略，考虑资源柔性导致的可替代加工路线，以总完工时间最短为目标，设置种群规模为60，最大迭代次数为100，得到消除强冲突的调度方案，调度结果甘特图如图5所示，并与没有考虑资源柔性的冲突消解调度策略（图6）进行了对比，根据表4分析可知，该解调度方案有效消除了冲突缩短了总延迟时间和总流程时间，提高了系统效率，具有一定的可行性及有效性。

表4 冲突消解结果分析表

图5 考虑资源柔性的冲突消解调度甘特图

图6 未考虑资源柔性的冲突消解调度甘特图

下面通过蒙特卡洛模拟仿真，验证弱冲突消解时对虚拟单元生产系统内调度过程稳定性的影响。假设虚拟单元某生产周期内划分为5个时间段，强冲突与弱冲突的发生相互独立，每个时间段内发生弱冲突和强冲突的概率都为5%，在95%的置信度下，模拟10000次后得出调度期内出现冲突的分布情况，如图7所示，横坐标上0表示没有发生冲突；-1表示发生了强冲突；1、2和3分别表示在1、2和3个时间段上发生了弱冲突 ，而没有发生强冲突。从仿真结果可以得出：没有发生冲突的概率约为59%；发生冲突的概率约为41%，其中强冲突的概率为24%，弱冲突的概率为17%；并且在弱冲突的情况中，冲突发生的次数呈指数减少，出现的冲突次数主要是1次，还有少量的2次，几乎没有3次以上的情况。根据冲突发生的概率可以估计出发生弱冲突时的系统调整即仅需对局部时间段内的生产任务作出调整，约占全部时间段的22.35%。仿真结果表明本文提出的资源冲突检测与消解方法能够较好的应对虚拟单元制造中的不确定扰动情况，消除资源冲突并保持整个生产过程的稳定性。

图7 冲突的概率分布

5 结论

本文针对虚拟单元制造中存在的问题，结合其生产过程的动态性、资源冲突的不可预测性、存在柔性设备等特点，提出了以制造系统生产过程稳定性和高效率为目标的资源冲突检测和消解模型。根据不同情况采取不同的消解策略，有效的消除了出现的冲突，并在一定程度上减少由于冲突引起的全局改变，有利于应用于实际生产中。

[1] Nitesh Khilwani et al. A methodology to design virtual cellular manufacturing systems[J].Journal of Intelligent Manufacturing, 2011,22:533-544.

[2] Saadettin Erhan Kesen. A mixed integer programming formulation for scheduling of virtual manufacturing cells (VMCs)[J].Int J Adv Manuf Technol,(2010) 47:665-678.

[3] 王军强,等.作业车间区间型多属性瓶颈识别方法[J].计算机集成制造系统,2013,19(2):0429-0437.

[4] Wang, Shuang-Xi. Flexible job shop dynamic scheduling under different reschedule periods[J].Computer Integrated Manufacturing Systems,2014,20(10):2470-2478.

[5] 乔立红,王超.多级协同项目执行中的资源冲突检测与管理[J]. 北京航空航天大学学报,2008,34(11):1266-1270.

[6] 杨萍,龙正平,王桐.基于协商的Agent资源冲突消解算法研究[J].指挥控制与仿真,2011,33(1):27-30.

[7] 黄喜,于天飞.基于时间约束网络的项目实施冲突识别算法[J]. 中国管理科学,2008,16:0197-0201.

[8] 尚志.基于贝叶斯网络的关键链项目管理模型[J].中国空间科学技术,2011,6(3).

[9] 宋海权,郭进,李耀.基于Petri网的分布式系统冲突消解[J].计算机工程与设计,2013,34(4):1351-1355.

[10] F. Liang, R.Y.K. Fung,Z.Jiang.Modelling approach and behaviour analysis of manufacturing resources in virtual cellular manufacturing systems using resource element concept[J]. International Journal of Computer Integrated Manufacturing, 2011,24(12):1168-1182.

[11] Adil Baykasoglu, Mustafa Göken.Capability-based distributed layout and its simulation based analyses[J].Journal of Intelligent Manufacturing,2010,21(4):471-485.

[12] Saad, S. M.et al.An integrated framework for reconfiguration of cellular manufacturing systems using virtual cells[J].Production Planning & Control,2002,13(4):381-393.

[13] F. Liang , R.Y.K. Fung,Z.Jiang.Modelling approach and behaviour analysis of manufacturing resources in virtual cellular manufacturing systems using resource element concept[J]. International Journal of Computer Integrated Manufacturing, 2011,24(12):1168-1182.

[14] 欧阳浩.用遗传算法解决物流中的仓库选址问题[J].制造业自动化,2014,36(1):51-64.