基于Petri网的服装柔性生产工序优化

王晓华，王瑞卿，洪 良，张 蕾，张宏伟

(西安工程大学 电子信息学院，陕西 西安710048)

随着服装市场消费档次的多样化发展，服装的生产类型从批量大、品种少和周期长逐步过渡为批量小、品种多和周期短的类型，因而要求企业具有快速反应的生产能力[1]。从20世纪70年代发展起来的服装吊挂系统可以快速地更换产品类型，但是服装生产柔性度不高，同时进行多品种加工生产时容易出现设备竞争、工作站配置和流水线平衡等问题[2]。学者们针对服装吊挂系统的优化问题展开了研究[3-5]。文献[6]应用蚁群算法重新编排流水线工序，获得了制品传递距离最小化下的系统优化结果，但缺少对设备竞争工序控制策略的考察。文献[7]结合标准资料法和学习曲线法制定了工时定额法，一定程度上满足了服装生产柔性度的要求，但难以适用于多品种服装生产工序的优化。文献[8-9]应用遗传算法对整个生产线上的个别生产工序进行了优化，但未考虑全部生产工序及各项资源，特别是多任务生产情况，存在一定的局限性。Petri网在柔性制造系统优化调度方面[10-12]具有一定的优越性，使其在机械、化工[13-14]等生产领域及数控系统的在线实时故障诊断[15]中得到了广泛应用。文献[16-17]建立了制造系统的时间Petri网模型，给出了柔性生产过程的优化调度方法。文献[18]应用Petri网建模和遗传算法优化了模具车间的作业调度，但未给出具体的工序排列方法。文献[19]将Petri网引入到服装生产线中，但未涉及具体的建模方法和工序调度策略算法。

本文采用赋时库所Petri网建模方法，解决服装吊挂系统多任务生产中设备资源竞争的工序优化问题。考察多任务生产线的约束条件和优化目标，对多任务生产进行赋时库所Petri网建模，应用工序最优调度策略算法，通过模型演化推导出考虑设备竞争的服装加工工序实施顺序，获得多任务条件下时间最短的生产实施方案，提高服装吊挂系统的柔性生产程度。

1 基本概念

基本的标识Petri网(PN)可表示为一个5元组N=(P，T，F，W，M0)，其中，P为有限非空的库所集合，库所p∈P用圆圈表示，代表系统的状态;T为有限非空的变迁集合，变迁t∈T用方框表示，代表系统中的事件;F⊆(P×T)∪(T×P)为流关系或有向弧的集合;W: (P×T)∪(T×P)→N+为有向弧的权函数;M0:P→N+为一个列向量，表示系统初始状态下所有库所中的托肯数，称为N的初始标识。·t表示t的所有输入库所的集合。PN的运行规则为：变迁t∈T在标识M下是使能的，当且仅当∀p∈·t，M(p)≥W(p，t)时，使能的变迁t发射产生新标识M′(p)，表示系统跃迁状态，M′(p)=M(p)-W(p，t)+W(t，p)。当∀p∈P，变迁t发射后，根据该变迁的W(p，t)和W(t，p)，系统将从输入库所中移出与变迁的输入有向弧权值相应数量的托肯到输出库所。赋时库所Petri网(Timed Place Petri Net，TPPN)TPPN=(P，T，F，W，M0，D)，其中，P，T，F，W，M0与基本PN的定义相同。D={d1，d2，...，dn}为库所的时延集合，其中，di为pi的时延。TPPN的变迁发射与基本PN的规则相同，改变输入与输出库所中的托肯数，但放入输出库所中的托肯必须等待一定时间才可以使用，这段时间称为该库所的时延。

2 服装吊挂系统的TPPN模型建立

假定一个服装吊挂系统需要同时进行n种服装的生产，其生产任务分别表示为J1，J2，...，Jn。各任务包含的工序数分别为X1，X2，...，Xn; 加工时要用到烫台、包缝机、双针平缝机、筒形卷边机等Y种设备，每种设备各一台; 需要Z种裁片S1，S2，...，SZ。多任务生产时，由于并发过程的存在和设备资源竞争等问题，工序的执行顺序不同，完成n项任务的时间也不相同。结合TPPN的基本概念与服装加工过程的特点，需建立服装吊挂系统多任务生产的TPPN模型。

以包含2项生产任务的J1和J2服装吊挂系统为例[19-20]，建立系统的TPPN模型。任务J1有13项工序，在模型中表示为13个生产阶段J1，1，J1，2，...，J1，13；任务J2有15项工序，在模型中表示为15个生产阶段J2，1，J2，2，...，J2，15。共需要4台设备即烫台、钉扣机、包缝机和平缝机。加工一件衣服需要12种裁片，前衣片(2片)、后衣片(1片)、门里襟(2片)、胸袋(1片)、过肩(2片)、袖片(2片)、袖头(4片)、衩里襟(4片)、衩门襟(2片)、领座(2片)、翻领(2片)、口袋(2片)，分别表示为S1，S2，...，S12。根据2种服装各自的工序排列顺序，将裁片送往相应的工作站，结合人工操作与所需的加工设备，完成2种服装的生产。2项生产任务中服装吊挂系统任务(加工时间、所需设备、裁片类型、数量)如表1所示。

表1 服装吊挂系统任务表Table 1 Task table of garment hanging system

通过共享资源库所连接的2个子系统模型NJ1和NJ2可得服装吊挂系统的TPPN模型，如图1所示。

图1 由共享资源库所连接任务J1和J2的Petri网模型获得的服装吊挂系统TPPN模型Fig.1 The TPPN model of garment hanging system obtained from the Petri net model of J1 and J2 connected with shared resource places

3 服装吊挂系统最优调度策略算法

应用所建立的服装吊挂系统的TPPN模型，利用有限的资源来找出完成多任务用时最少的工序排列方法，以实现最优加工。最优调度策略算法为设置n项任务的优先级，得到多种实施方案。每种方案中最后完工任务Ji的用时为dr，找出所有实施方案中最小dr值对应的变迁发射序列，得出工序最优调度策略。多任务生产线的目标函数为

(1)

多任务生产线的约束条件如下：

(1)Petri网的变迁使能和发射规则。当且仅当∀p∈·t，M(p)≥W(p，t)，使能的变迁t在满足服装加工规则后发射产生新的状态标识M′(p)，M′(p)=M(p)-W(p，t)+W(t，p)。

(2)服装加工规则。任务的工序按一定顺序排列，即具体的某项任务Ji中变迁t的发射顺序是固定的。

(3)设备资源竞争。设任务Ji包含ki台设备，n项任务J1，J2，...，Jn所需设备数量k为(k1，k2，...，kn)，其中每类设备各一台。当不同任务的工序竞争同一台设备时，根据优先级或使能时刻确定其使用顺序。

根据服装吊挂系统多任务生产线的目标函数和约束条件，得出系统最优调度策略算法，其中，算法的输入、输出及实施步骤如下所述。

输入：n项任务的服装吊挂系统TPPN。

输出：完成n项任务最短时间d，变迁最优发射序列。

Step2：由初始标识M0开始，当变迁t的前集库所中的托肯满足M(p)≥W(p，t)时，变迁t使能，找出所有使能的变迁。

Step3：搜索使能变迁，执行Step 3.1或3.2。

Step4：跳转至Step3，直至所有变迁都已发射。

Step6：跳转至Step 1，直至n!+n种实施方案都已完成。

在服装吊挂系统多任务生产工序调度问题中，考虑Petri网变迁的使能和发射规则、服装加工规则和设备竞争等约束条件，将完工时间最短设为调度目标，找出最短时间条件下变迁的发射时间和序列。映射变迁到服装吊挂系统中与工序关联的事件，得出n项任务的工序排列顺序和时刻，即最优调度策略。赋时库所Petri网TPPN模型工序最优调度策略算法流程如图2所示。

图2 赋时库所Petri网TPPN模型工序最优调度策略算法流程Fig.2 Flow chart of optimal scheduling policy algorithm of process based on TPPN model

4 试验与分析

方案1的最后完工任务为J2，则

方案2的最后完工任务为J1，则

(13+6)+(36+81)+(25+0)+(32+0)+(22+

0)+(30+0)+(33+0)+(105+0)+(47+0)+

(94+0)+(127+0)=1 097 s

方案3的最后完工任务为J2，则

(13+0)+(36+12)+(10+0)+(7+0)+(25+

0)+(32+0)+(22+0)+(30+8)+(33+3)+

(105+72)+(47+0)+(94+47)+(127+33)=902 s

方案4的最后完工任务为J1，则

(13+0)+(36+23)+(25+6)+(32+7)+(22+

0)+(30+8)+(33+3)+(105+72)+(47+0)+

(94+47)+(127+33)=926 s

表2 加工时间最短条件下变迁发射序列Table 2 The transition firing sequence under the minimum processing time

表3 基于Petri网的服装柔性生产工序最优调度策略Table 3 Optimal scheduling policy of garment flexible production process based on Petri net

为验证基于Petri网的服装柔性生产工序优化方法的实用性，本文整理了其他研究者获得的服装生产优化的信息[20-21]，多品种服装的多任务加工数据如表4所示。

表4 多品种服装的多任务加工相关数据Table 4 Multitask processing-related data of various clothing

将n值依次设为2，3，4，5，6，输入工序、时间和设备等数据，使用最优调度策略算法进行工序优化，计算得到的完工时间分别为902、1 638、1 167、1 543、1 268 s，其与由原文数据计算出的生产时间的对比如表4所示。

由表4可以看出，本文算法适合不同种类和多种款式服装的工序优化，利用最优加工策略算法对各工序的加工时刻进行合理分配，使得总体时间减少，提高了服装吊挂系统对于小批量和多品种的服装生产效率。

5 结 语

本文将赋时Petri网理论引入服装吊挂系统的生产工序优化研究中，结合Petri网的概念、服装在生产线上的加工特性和工序优化的规则，编写出最优调度策略算法。试验证明，应用基于Petri网的最优调度策略方法可缩短多种服装同时加工的时间，提高系统的运行效率。但本研究只考虑每种设备仅有一台的情况，根据各台设备在完成一次任务中的使用频率，将对于设备种类和数量的优化做为下一步研究的目标。

参 考 文 献

[1] 蔡文静，金京. 服装吊挂传输系统发展概况及应用研究[J]. 轻工科技，2015(8): 115-117.

[2] 吴鑫，俞建定，赵鹏飞，等. 基于以太网和RS485的服装吊挂生产线控制系统[J].机电工程，2013，30(10): 1280-1285.

[3] MORK P Y，CHEUNG T Y. Intelligent production planning for complex garment manufacturing [J]. Journal of Intelligent Manufacturing，2013，24(1): 133-145.

[4] CUI H R，YAN Y N. The optimization design of uniform’s hanging production line [J]. International Journal of Clothing Science and Technology，2015，27(3): 370-389.

[5] ZHANG R，CHANG P C，SONG S. A multi-objective artificial bee colony algorithm for parallel batch-processing machine scheduling in fabric dyeing processes [J]. Knowledge-Based Systems，2017，116(1): 114-129.

[6] 于昕辰，曾培峰，赵冉，等. 基于蚁群算法的服装生产流水线作业平衡[J]. 东华大学学报(自然科学版)，2014，40(4): 456-460.

[7] 叶宁，阎玉秀. 多品种小批量服装生产的工时定额制定方法[J]. 纺织学报，2012，33(6): 101-106.

[8] WANG J A，PAN R，WANG H. An automatic scheduling method for weaving enterprise based on genetic algorithm [J]. Journal of the Textile Institute，2015，106(12): 1377-1387.

[9] 王东云，刘慧琴. 基于遗传算法的铺布与裁剪过程的优化调度[J]. 纺织学报，2005，26(5): 111-114.

[10] HONG L，CHAO D Y. Enumeration of reachable states for arbitrary marked graphs [J]. IET Control Theory & Applications，2012，6(10): 1536-1543.

[11] HONG L，HOU Y F，JING J F，et al. Deadlock prevention policy with behavioral optimality or suboptimality achieved by the redundancy identification of constraints and the rearrangement of monitors[J]. Discrete Dynamics in Nature and Society，2015，2015(1): 1-15.

[12] HONG L，WANG A R，JING J F，et al. Combinatorics and resource circuit-based enumeration of reachable states for S3PR [J]. Advances in Mechanical Engineering，2015，8(6): 1-11.

[13] 苏国军，汪晋，田立国. 基于Petri网模型的柔性制造系统优化调度[J]. 系统工程理论与实践，2014，34(10): 2717-2721.

[14] 周家忠，罗继亮，詹瑜坤. 间歇式化工系统的Petri网优化调度与控制方法[J]. 控制理论与应用，2016，33(6): 809-815.

[15] 田仁铁，杨建国. 一种基于Petri网模型的数控系统的分析与在线实时故障诊断方法[J]. 东华大学学报(自然科学版)，2015，41(4): 503-508.

[16] JUNG C，KIM H，LEE T. A branch and band algorithm for cyclic scheduling of Timed Petri nets[J]. IEEE Transitions on Automation Science and Engineering，2015，12(1): 309-323.

[17] PANG C，LE C V. Optimization of total energy consumption in flexible manufacturing system using weighted P-Timed Petri nets and dynamic programming [J]. IEEE Transition on Automation Science and Engineering，2013，11(4): 1083-1096.

[18] YAO W L，PAN Y M. A Petri nets and genetic algorithm based optimal scheduling for Job Shop manufacturing system [C] //ICSSE-IEEE International Conference on System Science and Engineering. 2013: 99-104.

[19] 张玉斌，陈雁. Petri网在服装生产平衡中的应用[J]. 轻纺工业与技术，2009，38(1): 38-40.

[20] 陈海湄. 服装缝制流水线的作业编排与优化研究[D]. 苏州: 苏州大学纺织与服装工程学院，2005.

[21] 刘谣. 基于ProModel的仿真系统的服装混合流水线平衡优化[D]. 上海: 东华大学纺织学院，2015.