基于Plant Simulation的作业调度仿真研究

□ 汪致宾

(珠海格力电器股份有限公司，广东 珠海 519000)

1 引言

单品类东西在当今世界经济融合发展的进程中并不能满足所有消费者的需求，各企业必须针对不同消费者群体制造不同的产品以求生存，但是不同种类的产品各生产制造环节具有较大的差异 ；与此同时，各市场需求风云变幻，日常生产制造异常不可控等因素均会给企业在车间作业调度中带来较大的问题，而当前的车间作业调度模式无法较好地解决各类异常状况。

2 传统单线作业调度

2.1 PFSP(Permutation Flow Shop Problem,PFSP)问题的描述与假设

2.1.1 问题的描述

PFSP问题属于一类经典的NP-hard生产作业调度问题。在实际生产中同一机器需连续对许多的在制品进行加工处理，同时每个在制品需要在多台机器上进行加工处理，并且如果机器不同时各在制品所需的加工处理时间是不同的，因此确定各在制品在不同机器上加工处理的先后顺序会对其最终加工时间结果具有较大的影响。根据并行机的类别，经典的PFSP可以划分为以下三类：相同并行机混合流水线[1]；均匀并行机混合流水线[2]；不相关并行机混合流水线[3]。考虑到实际生产作业中的工艺约束和加工作业环境，在过去一段时间，大量学者都对PFSP问题进行了横向和纵向的研究，同时提出了不同的PFSP作业调度问题和模型。该问题具体说明如下：

n个加工任务(N=J1,J2,…,Jn)，三类产品X、Y、Z需在m台机器(M=M1,M2,…,Mm)上完成加工，每个加工任务都包括操作集合J={Oi1,Oi2,Ojm}，加工任务Jj在第Mi台机器上需要的加工时间记为Pi,j(i=1,2,…,m;j=1,2,…,n)。PFSP问题通过n/m/P/Cmax来 表述，也就是n个加工任务/m台设备/置换流水线调度/最大完成时间。

加工顺序π={π1,π2,…，πn}，n个加工任务会依次经过台机器。任务πj在机器m上加工完成时间表示为C(πj,m)。按照加工次序π={π1,π2,…,πn}，PFSP问题的加工完成时间如下所示：

C(π1)=Pπ,1

(1)

C(πj,1)=C(πj-1,1)+Pπ,1,j=2,…;n

(2)

C(π1,i)=C(π1,i-1)+Pπ,j,i=2,…,m

(3)

Cπj,j=max{C(πj-1,1),C(πj,i-1)+Pπ,1,J=2,…，m}

(4)

Makespan定义为：Cmax(π)=C(πn,m)。其中，Makespan指的是最大加工完成时间。PFSP问题的目的是寻求该排列的最优解：

π*∶Cmax(π*)≤C(πn,m),∀π∈∏。

2.1.2 PFSP问题的假设

为了确保不少于一个特性指标可以得到最优解，PFSP问题的首要目的即是确定好n个加工任务在各台机器上的最佳加工次序。故对于此问题有如下假设：①所有工件在每台机器设备上均有指定的加工次序；②单台机器设备在加工处理工件时具有时间上的唯一性；③每个工件的加工任务在每台机器设备上进行加工处理时具有时间上的唯一性；④各加工工序具有随机自主性；⑤每个工序处理顺序和准备时间不会相互影响，同时准备时间属于加工时间一部分；⑥所有的加工任务在该系统中机器设备上的加工顺序是一致的；⑦每台机器均持续可用；⑧如某台机器已在加工处理该任务则在完成前均不能够停滞亦不能有别的在制品插入进行加工处理。

2.2 Palmer启发式算法

对于一般的车间作业调度问题，可以通过分支定界法来保证得到普通问题的最优解。在现实生产作业中若需要对较大规模的问题进行求解时采用分支定界法以求得到普通问题的最优解需花费大量的时间来完成，因而其代价较大。要想通过较低的计算量即可得到较为满意的结果，可使用更为实用的启发式方法。Palmer启发式算法研究的是按照斜度指标给工件完成排序，其公式如下(5)所示：

(5)

上述公式，表示机器设备的数量；tij指工件Ji在所指定机器设备Mj上需要的处理时间。

2.3 建模与仿真

①如图1建立模型。

图1 Palmer仿真模型图

②工件X、Y、Z分别于M1、M2、M3上的所需的加工处理时间如表1所示。

表1 各工件处理加工明细表

③各工件生成如公式(6)所示：

λ(t)=0.4+0.3*sin[(i*pi)/15]

(6)

④工件X、Y、Z数量均为33。

⑤该系统模型参数完成设置后，不借助Palmer方法而是直接点击运行EventController，让其以随意的加工作业顺序完成各项任务，以此得到的最大流程时间如图2所示为12天21小时47分钟52秒。

图2 正常调度甘特图

⑥设置系统使用Palmer启发式算法并对模型进行运行，得到如图3所示的最大流程时间为12天17小时40分钟34秒，与图2对比可看出Palmer启发式算法降低约4个小时。

图3 Palmer甘特图

⑦对M2的失效选项卡参数进行重新设置，使其失效24小时。

⑧重新点击运行EventController，得到如图4所示的最大流程时间为13天18小时30分钟53秒，与图2-3对比可见显著提高约25小时。

图4 机器失效Palmer算法作业调度甘特图

⑨整个系统在M2失效时在制品数变动如图5所示。

图5 机器失效Palmer算法在制品变化图

从上述三种仿真模型结果可知Palmer启发式算法尽管可以减少最大流程时间，但是若机器设备出现故障而同时有多类加工件需要加工处理时会提高该系统的最大流程时间，延迟该批生产订单的交付周期，不仅如此，该系统中的在制品数量亦显著提高。

3 基于局部信息的自主决策作业调度

3.1 问题描述

在获得相关局部信息的同时，各智能物流对象还需根据该信息完成相关决策；另一方面，各物流对象获得的局部信息中包含着大量的干扰信息，使得各物流对象所做的每一个下一步骤具有更高的普适性。在智能调度中，各在制品工件本身可以自主确定使用某台机器完成加工作业。而对于不同类型的在制品工件所需的处理时间各不相同这一状况亦需作为参考，本文中具体的各类产品所需加工处理时间见表2。

本文讨论的基于队列长度估计(Queue Length Estimator,QLE)的自主作业调度，其工件或产品计为X、Y、Z。各类产品在自己产线上所需要的加工时间是最短的，而如果该产品想要变更产线的话，则其加工处理时间会更长。同时假定变更产线的决策通过该工件自身以得到的缓冲区局部信息来完成的。所以该产品在考虑是否变更生产线时会计算其它产线的加工处理时间会比其自身产线所需加工时间更长这一情况。在每一台机器设备上，该产品自主计算对比切换机器设备所需处理时间和它自己设备所需处理时间，而后选择加工完成时间更少的机器设备。如图6所示。

图6 流程图示例

3.2 建模与仿真

①如图7建立模型。

图7 QLE仿真模型图

②如表2所示明确X、Y、Z在M11、M12、M13、M21、M22、M23、M31、M32、M33上所需加工处理时间，且它们数量都是99件。

表2 QLE工件加工时间表

③对相关参数进行设置后，点击运行EventController，如图8所示得到的最大流程时间是7天4小时25分钟。

图8 基于QLE作业调度甘特图

④对M22失效选项卡进行重新设置，让它失效24小时。

⑤重新点击运行EventController得到如图9所示的最大流程时间为7天11小时30分钟，对比M22未失效时最大流程时间提高了约7小时。

图9 机器失效QLE作业调度甘特图

⑥如图10所示为M22失效状况下该模型系统中的制品数量变化情况。

图10 机器失效下QLE在制品变化图

在系统中某台机器出现异常无法完成加工作业时，Palmer算法模型中的在制品数量快速的增加，而且长时间未见减少；QLE可以对机器出现异常无法完成加工作业的突发状况进行较快的反应，QLE模型中的在制品数量尽管在一定时间内出现增加，但是在较短时间内就减少到了平均值，整个模型系统受到较低的影响，对于机器异常无法完成加工作业的突发情况具有更好的响应。

与Palmer算法的作业调度对比，基于队列长度估计的多类型产品作业调度在机器能够正常作业和某一台机器发生异常无法进行加工作业24h这两类的最大流程时间下，其均可在很大程度上减少最大流程时间，机器异常无法进行加工作业对整个模型系统的正常运行具有更低的影响。

4 总结和展望

4.1 本文的主要结论

本文以Plant Simulation为工具，获得下述结论。

①Palmer算法尽管对解决PFSP问题具有一定程度的效果，然而其效用是有限的，如模型所示若某台机器出现异常无法作业时，Palmer算法更是无法发挥效用。

②不论机器是否出现异常无法进行加工作业，QLE模型中的作业调度方法对整个系统在最大作业时间方面具有更好的影响，整个系统具有更强的鲁棒性。

4.2 研究展望

总体而言，使用QLE这种基于局部信息的自主作业调度方式，各类工件均能够根据实际情况自行调整，对于突发状况能够做出较好的反应。对于该方向的深入研究具有一定的促进作用。鉴于本文篇幅有限，基于局部信息的自主作业调度能够在工件完成加工的终止时间、类别优先级等方向上来做深入的研究，同时在制品变化量、滞留等待时间等亦是可作为研究比较的指标。另外本文所提到的加工作业时间、准产线间的切换时间、准备时间等同样可以做深入的研究。