装配生产线建模方法及资源优化研究

任工昌,董钰颖,何 舟,崔晨浩

(陕西科技大学 机电工程学院，陕西 西安 710021)

0 引言

制造业装配生产线是当前普遍的一种生产作业形式，生产线的生产效率直接影响整个产品的生产效率乃至整个公司的竞争力.传统的装配生产线一定程度上实现了自动化生产，但是由于资源配置不均仍然存在生产效率低下，资源利用率不高的问题.如何在预算一定的前提下，合理分配资源，使得生产线的生产效率最大化是研究人员急需解决的核心问题[1].

资源优化作为一个典型的NP-Hard组合优化难题，国内外研究人员主要采用以下三种方法开展大量的研究：(1)数学分析法，对生产线进行数学分析建模求解能够找到问题的最优解，但是求解过程十分繁杂，且计算量非常大，削弱了其在实际复杂生产问题中的实用性[2,3].(2)工业工程法，针对具体生产线的整体和局部乃至个体的全方位的分析，从动作本身上采取有效的改善措施[4-6]，然而这种方法缺乏通用性.(3)启发式算法，在一个随机群体寻优的过程中，每个个体都可以利用其自身或全局的搜索经验，来决定各自的搜索寻优策略，较工业工程法而言更具有普适性.现有的启发式算法以仿自然体算法为主，主要有蚁群算法、遗传算法、模拟退火法、神经网络等智能算法，优缺点各不相同[7-9].

现有的启发式算法以仿自然体算法为主，主要有蚁群算法、遗传算法、模拟退火法、神经网络等智能算法，优缺点各不相同，而本文提出的基于线性规划的启发式算法本质上与上述智能算法有所不同.线性规划问题更加直观地反应资源优化配置问题的数学本质，同时结合Petri网P-不变式的数学特性，可不依赖穷举系统加工回路高效找到瓶颈工序进行资源优化配置，降低瓶颈工序的加工时间.对于大规模复杂结构的制造系统而言，此算法效率依然很高.

1 基于Petri网的装配生产线建模方法

一个制造系统是由工件的传输、加工以及控制信息的处理等制造活动集合而成的.这些活动通过各种资源(人，机器人，传输带，机床，半成品以及原材料等)的整合操作，最终生产出满足需求的合格产品.然而，对于生产线建立的模型需要准确的描述工序之间的优先关系，车间资源的分配关系，每道工序加工所需要的资源，而Petri网模型能够很好的描述此类离散系统的逻辑关系.

Petri网自20世纪60年代提出以后，由于其具有强大的建模分析能力、图形和数学双重表示、高效分析离散事件系统等优点，被广泛地应用于制造系统、运输系统及物流等系统.王青等[10]采用Petri网对飞机总装配生产线进行建模，采用贪心-匈牙利算法获得生产线最佳人工分配方案.栾飞等[11]利用Petri网对自动化立体仓库出入库调度优化进行模拟仿真.王浚元等[12]选用Petri网建立磁极铁芯生产线模型,Flexsim仿真生产线模型并找出瓶颈工序.用Petri网建模与分析系统，可以研究资源优化配置，资源调度，故障诊断，系统状态估计等一系列科学问题[13-15].

Petri网由两种节点：库所(P)和变迁(t)、有向弧、以及托肯等元素组成的，变迁和库所分别用圆圈和矩形表示，库所表示条件或者状态，变迁表示状态之间的流动，变迁和库所之间由有向弧连接，库所中的动态对象用小黑点表示，叫做托肯，可以从一个库所移动到另一个库所[16,17].

弧权值均为1的P/T网被称为普通网，事件图是所有库所只有一个输入变迁和一个输出变迁的普通网[18,19].与以往研究不同，本文采用了循环时间事件图(CTEG)对制造系统进行建模.网模型中从一个节点出发经过一系列动作又回到该节点所形成的回路称为基本回路.对于事件图来说，一个基本回路γ的循环时间Cγ可以通过(1)式计算：

(1)

式(1)中：μγ是回路γ中所有变迁的时延之和，Xγ是回路γ中托肯的数量.

本文采用循环时间事件图对制造装配线实际加工流程建模.如图1所示，描述的是系统的一个子工序.在图1中,Petri网结构N可以由五元组N=(P,T,Pre,Post,C)表示.P是6个库所集合，T是3个变迁集合，各库所与变迁的含义如表1 所述；如式(2)所示，Post，Pre分别为维度是6*3、元素为非负整数的矩阵分别表示N的输入矩阵和输出矩阵.矩阵C=Post-Pre，是一个6*3的整数矩阵称为关联矩阵，可以准确的刻画出网的具体结构.

P1：原料就绪；P2：机床等待加工；P3：工件加工完成；P4：工件从机器中移出；M：机器；R：该工序配置的劳动力；t1：上料 ；t2：机床开始加工；t3：卸料图1 某工序的Petri网建模图

(2)

标识M是6维非负整数列向量，M0=[4 0 0 0 1 1]T是初始状态生产线的资源配置.变迁t1的输入库所p1、M中都有可以使用的资源，因此t1为使能变迁，t1激发后的标识M′=M0+C*t1.若从初始状态M0开始M0[t1>M1[t2>M2…[tn>Mn]]]成立，则称Mn从标识M0可达.发射序列σ=t1,t2,…,tn.

该Petri网中的变迁t1,t2,t3分别表示着该工位加工过程中上料，机床加工和卸料三个动作，用时5 s、20 s和5 s.将库所分为资源库所和系统库所，资源库所由系统加工机器M、劳动力R等资源组成.系统库所是装配生产线的加工工序.如图1中存在三个基本回路γ1：t1,p2,t2,p3,t3,M,t1；γ2：t1,R,t1；γ3：t3,R,t3.γ1表示着工件由专用机器M进行加工的过程，γ2、γ3分别表示工件由劳动力R进行上、下料的过程.对于Petri网模型，一个基本回路γ，称之为该Petri网的一个P-不变量[20].根据P-不变量数学特性，基本回路满足如式(3)所示的数学关系：

αγTC=0

(3)

式(3)中：αγ是基本回路库所集合的特征向量.C是Petri网的关联矩阵.

因此，装配生产线各工序的前后关系、并行关系就可以由Petri网表示出来，并根据Petri网的数学特性，写出网的关联矩阵.这样就可以将一个抽象的生产线问题转换成具体的数学矩阵问题，便于进一步分析.

2 问题描述以及资源优化

2.1 装配线资源优化问题描述

针对当前流水生产线各工序资源分配不当导致生产效率低的问题.如何在预算有限的前提下，寻找到生产线的瓶颈回路，并在该回路中进行资源的优化配置，降低瓶颈回路的加工时间、提高生产线的加工效率，是制造业目前急需解决的关键问题.数学模型描述如下：

(4)

式(4)中：CTγ(M)表示系统瓶颈回路的循环时间,Г表示所有初级回路γ的集合，u(i)表示资源i的单价，n(i)表示资源i的数量，M表示系统当前的资源配置情况，b表示预算.

2.2 基于线性规划的启发式算法

针对上述问题，本文结合Petri网的数学特性提出一种启发式算法对生产线进行资源优化，具体步骤如下：

(1)首先，配置初始资源(M0)，原则是保证系统的活性即保证装配线的正常运行；通过仿真计算出生产线初始状态下生产系统的循环时间CT(M0).如果初始状态的成本a0

(2)寻找影响整个系统加工时间的瓶颈回路，在不超过预算的基础上，向该回路的资源库所中添加资源.对此工作，以往总是采用穷举法枚举每个基本回路的循环时间，从而找到瓶颈回路.但是对于大规模的制造系统来说存在很大局限性.因此，基于Petri网的数学特性，结合式(1)基本回路循环时间的计算公式，可建立线性规划数学模型寻找出系统的瓶颈回路.该模型的目标函数为：

(5)

s.t.αγTC=0

(6)

αγTM=1

(7)

αγ≥0

式(5)中：αγTpre表示属于回路γ的变迁集合的特征向量，T表示激发时延变迁的时间集合.αγTM是回路γ中托肯和Xγ；αγTPreT是回路γ的时间总和μγ.约束(6)保证决策变量αγ是基本回路库所集合的特征向量.约束(7)将目标函数的非线性规划模型转化为如下线性规划模型:

CTγ(M)=maxαγTPreT

(8)

s.t.αγTC=0

(9)

αγ≥0

(3)在上一步找到的瓶颈回路的资源库所中添加资源，判断优化后新的状态M1下总成本a1是否超过预算，若未超过预算则进一步的迭代优化直至总成本an超过预算，则撤回最后一步优化资源，输出an-1为最优的资源配置.

2.3 算法框架

启发式算法的框架如图2所示.

图2 启发式算法框架

在图2中,eg表示瓶颈工序添加资源位置的特征向量，u(g)表示资源i的单价，在当前状态的关键回路g中添加资源，得到新的标识状态和成本.判断优化后的总成本a1是否超过预算，若未超过预算则开始循环体语句；直到总成本an超过预算，则移除上一步所添加的资源，并输出生产线资源最优配置状态mn-1,装配线成本为an-1，从而在不超过预算的基础上最大程度地提高产品的产出效率.

3 实例验证

3.1 液力变矩器资源配置问题

本文以陕西西安某公司投入生产的液力变矩器装配生产线作为研究对象.该企业目前的液力变矩器装配生产线由泵轮生产线，涡轮与闭锁离合器组件生产线，导轮生产线，罩轮生产线以及液力变矩器总装配线组成，共有43道工序，62道工位，31个劳动力，41台机器设备.依照上述工序的建模规则，该生产线根据实际生产中的工艺布局建立的Petri网模型.如图3所示，该模型由106个变迁，172个库所，81个基本回路组成.

图3 液力变矩器装配生产线Petri网建模图

规定固定资产的总预算b为13万元，通过充分市场调研，生产线中各机器价格见表1所示，劳动力0.6万元/人，在满足系统可以正常运行的状态下，初始成本为9.45万元.

表1 各机器价格统计

表2记录部分工位加工时间信息，规定人工上下料分别用时5 s.

表2 部分生产线的工时统计表

根据上述信息和初始状态下装配线的资源配置情况m0对生产线进行仿真，经过分析结果可以得到每个变迁的发射频率，再通过Petri网的特性公式，计算生产线的循环时间.

CT=σ/f

(10)

式(10)中：CT是生产线的循环时间，σ是变迁的发射序列，f是变迁的发射频率.

通过Matlab对现有生产线仿真，仿真结果可知：整个系统完成一次加工任务变迁t106只发射一次，该变迁的发射频率为0.006 9.利用公式(10)可计算出初始状态下生产线的循环时间CT为145 s.

3.2 迭代优化

3.2.1 基于线性规划的优化

本实验采用MATLAB软件对2.2提出的算法进行求解.计算机硬件仿真平台的参数如下：惠普690-078CCN，处理器i7-9750H，内存16 GB，独显GTX 1600Ti 6G，计算结果如表3所示.通过对线性规划模型进行求解，优化前生产线的瓶颈回路为回路γ42，循环时间为130 s.由于资源配置不当导致生产线的生产效率较低，需要进行优化改进.该回路是装配涡轮工序，由1人手工进行装配，考虑到这样的情况，选择增加一名工人协助装配.对加入新员工之后的工序重新进行时间测定.改善后，装配涡轮工序的循环时间由130 s降低到了65 s.此时生产线的资源配置情况为机器41台，劳动力32人，总成本为10.4万元，并未超出预算，则进一步计算初步优化后生产线的瓶颈回路.

表3 迭代优化生产线对比

照上述算法优化，直到第四次优化后，装配线的资源配置情况为42台机器和34名劳动力，总成本为13万元等于预算，若继续增加资源则会超过预算因此停止优化.采用这种优化算法，优化之后装配线的循环时间70 s，下降了52%，有效的提高了生产线的生产效率.

3.2.2 穷举验证计算结果

本部分采用穷举方法寻找瓶颈工序.优化前各工序循环时间如图4所示，迭代优化过程如图5所示.

图4 优化前各基本回路的循环时间

(a)第一次优化后 (b)第二次优化后

(c)第三次优化后 (d)第四次优化后图5 迭代优化过程中循环时间对比

将图5的仿真结果与表3计算结果进行对比验证了线性规划模型寻找瓶颈工序的正确性.另外，观察图5可以发现，经过4次资源优化配置，生产线的各工序加工循环时间趋于平衡，从而验证提出的启发式算法能够有效的改善生产线资源配置不均、生产效率低的问题.

4 结论

针对生产线生产效率低的问题，本文提出了一种启发式算法对生产线进行资源优化：首先用Petri网对生产线建模；其次结合Petri网的数学特性提出一个线性规划模型寻找生产线的瓶颈回路；通过迭代启发式算法在预算一定的前提下对瓶颈工序进行资源优化.

以某液力变矩器装配生产线为例，利用Matlab软件进行实验，实验结果证明采用本文所提出的算法进行资源优化，生产线的循环时间降低了52%，有效提高生产线的生产效率.最后通过穷举法计算结果与线性规划模型进行对比，验证本模型的正确性.另外，在本文研究的基础上，可进一步开展工序优化及设备性能优化等研究工作，这也是本文作者未来的研究方向.