摘要：

有效的调度方法与优化技术的研究和应用，已成为先进制造技术实践的基础和关键。本文就车间调度问题的研究状况，探讨了SMT产品制造企业车间调度建模的研究方法，在面向对象的Petri网基础上,引入依赖消息,提出了一种扩充的面向对象Petri网(EOPN)模型,并建立了一台贴片机系统的完整的EOPN模型。

关键词：

SMT；车间调度；Petri网

0. 前言
随着电子产品向微型化、便携式、网络化和多媒体方向迅速发展，SMT(Surface Mount Technology 表面贴装技术)在电子工业中正得到越来越广泛的应用。如何提高SMT系统的生产效率，如何对SMT产品制造企业的车间调度进行优化，这一技术问题就提到了人们的视野中。对于SMT产品制造企业来讲，要想在激烈的竞争中取胜，最重要的是使SMT生产线发挥最大的效率，提高合格产品的产量。然而，要达到这一目标，必然会受到诸多因素的影响。所以必须对SMT 产品制造过程的车间调度进行优化，才可以实现高效生产。当代产品开发和交付周期大大缩短，多品种、小批量、用户定制化的生产逐渐流行起来。这种生产方式使得生产的计划、组织和控制变得更加复杂，并要求对制造过程中产生的各类信息进行及时的反馈和处理。因此,通过利用计算机技术实现车间调度计划优化，快速调整资源配制,统筹安排生产进度，以较低的成本按期交付用户满意的产品，对于提高企业自身的竞争力,具有重要意义。

车间调度会经常遇到生产计划停滞、变更的情况，如在生产过程中发现设计或工艺文件的缺陷或不够完善，或在检验加工件时发现超差,就需要等待技术人员处理；如在加工中遇到进度紧张、资源冲突或外协、外购的零部件、材料等无法在预定期限内交付使用,就需要调度人员及时协调。因此，车间调度与控制技术是实现生产高效率、高柔性和高质量的关键。车间生产过程的调度问题，是制造系统运筹技术、管理技术与优化技术发展的核心。

1. 车间调度问题的描述
1.1 车间调度问题的描述及其发展过程
从数学规划的角度看，车间调度问题可表达为在等式或不等式约束下，对一个或多个目标函数的优化。现代典型的车间调度问题是:将作业均衡地安排到各处理机上，并合理地安排作业的加工次序和开始时间，使约束条件被满足，同时优化一些性能指标。调度问题的研究始于20世纪50年代，Johnson提出了解决n/2/F/Cmax和部分特殊的n/3/F/Cmax问题的优化算法，代表调度理论研究的开始；60-70年代建立了调度理论的主体(经典调度理论)并重视调度复杂性的研究。随着70年代后期调度理论研究的深人及各种交叉学科的发展，又涌现出了许多新的车间调度理论与方法。

1.2车间调度问题的分类与特点
对于车间调度问题，有的学者进行了分类整理。按照不同的分类标准，可分为以下6种类型①开环车间和闭环车间。②单台处理机、多台并行机、Flow shop和Job shop。③基于调度费用和基于调度性能的指标。④确定性调度、随机性调度。⑤静态调度，动态实时调度。⑥有序加工，无序加工。
现代车间调度类型往往是Job shop型的，其调度问题有以下特点：①建模复杂性。②计算复杂性。③动态随机性。④多约束性。⑤多目标性。

1.3 SMT产品制造系统车间调度问题的描述
SMT产品制造系统的车间调度优化对象为SMT 生产线，并且配置的机器设备可能各不相同。有的生产线就是通常意义上的主要由丝网印刷机，高速贴片机，多功能贴片机，回流焊炉以及一些辅助设备组成。有的生产线在此基础上添加了AOI在线检测设备，分别配置在丝网印刷机后、多功能贴片机后、回流焊炉后。这种生产线主要用于要求精度很高的印制板的生产，可以实现在线检测，找出不良品进行返修?；褂械纳咴谝陨系幕∩嫌衷黾拥憬夯筒ǚ搴嘎?，以实现不同规格的印制板的生产。同时，在每条生产线上都装备一些辅助设备，如：上板机、下板机、翻板机、转板机，以及PCB传输线、SMC/SMD备料架与备料库、各种动力驱动设备等。每一条生产线的主要设备之间都通过传输设备与其它生产线相连接，这样就构成一种网状的制造单元，使各条生产线之间能够协同工作。使这些生产线能够在生产不同规格的印制板时能够高效的生产是车间调度优化的目标。

1.4 SMT产品制造系统的车间调度与其他制造系统车间调度问题的区别
传统的制造系统车间调度分为作业车间调度问题(Job Shop Scheduling Problem, JSSP)和流水车间调度问题(Flow Shop Scheduling Problem, FSSP)两种类型，在JSSP中，产品品种多、数量少、加工路径短且有随机性，其任务就是在满足工件工艺路线要求的前提下，为各个工件寻找一条有时间限制的路线，使得工件按照这种有时限的路线能够顺利生产出来；在FSSP中,产品单一、大批量生产、加工路径相对固定。每种产品，尽管材料规格不同，整个车间总是采用同样的流程。实际上，流水车间调度问题是JSSP的一个特例，它是在JSSP的基础上统一了工件流经加工网络的路线，因而比一般的JSSP大大简化。而在SMT产品制造系统中，既有面向库存的大批量生产，也有面向定单的生产，只在有订单需求下才生产；更多的是根据顾客需求量身定做，不但产品种类繁多，各类产品需求量亦多不大。所以，SMT产品制造系统的车间调度问题是不同于JSSP和FSSP的混合型制造系统，其典型特征是生产分阶段进行，设备按阶段使用，在不同的生产阶段遵循不同的生产方式?；诖? SMT产品制造系统的车间调度优化问题用传统算法很难解决，难点主要有两个方面：一是问题描述难，二是求解难。这也正是SMT产品制造系统区别于一般制造系统的重要特点。

2.  车间调度问题的建模方法
一般的车间调度都是对于具体生产环境中复杂动态、多目标、多约束调度问题的一种抽象和简化，其首要问题是对制造系统进行建模。目前建模方法很多，主要有以下两大类。

2.1图与网络方法
作为制造系统主要的建模方法，主要有活动循环图、关键路径法、组合网络、Petri网、GRAI网等，而其中Petri网以其独特的优势广泛应用在制造系统的设计、分析与仿真中。这里，主要介绍一下Petri网。

(1)基本Petri网。
基本Petri网模型具有直观易理解的优点，但其在描述复杂系统时节点数目过多，因而只适用于简单制造系统的建模。

 (2)扩展Petri网。
这里介绍几种典型扩展Petri网。①EP-N模型。它通过增加决策节点，使Petri网具有描述诸如FMS调度决策过程的能力。这种模型有节点数目过多的缺点，只适用于简单系统的建模。②CP-N模型。CP-N是Petri网的压缩形式，同基本Petri网相比它具有较少的节点数目，较适合复杂系统的建模，但其分析方法较为复杂。③TP-N模型。它不仅能够描述系统中事件和状态演化中的逻辑关系，而且通过设置时间与变迁或库所的联系来分析Petri网演化过程。有的学者将TP-N应用到了FMS的局域网建模、控制和仿真当中。④P/TP-N模型。这种网比EP-N有更少的节点和更简单的结构，但没有决策节点。⑤HLP-N模型。将P/TP-N和CP-N结合起来，就组成了HLP-N模型。我国的学者严洪森在HLP-N和EP-N的基础卜，提出了EHLEP-N，该网结构简单、节点少，很适合于FMS的建模、仿真与控制。

(3) Petri网的最新发展。
随着面向对象(OO)技术的发展与应用，人们开始研究如何将两者结合起来，以增强Petri网的设计描述能力和功能实现能力，降低其建模和分析的系统依赖性与难度。Petri网技术与00技术的结合有以下两种方式：Objects inside Petri Net和Petri Nets inside Objects，并将此类Petri网分为基于对象的Petri网(OBPN)、面向对象的Petri网(OOPN)和对象Petri网(OPN)。

2.2非图或网络的建模方法
这类方法主要有3种。
 (1)控制论的方法(主要为扰动分析法(PA)和极大代数法)。PA兼容了仿真法与理论分析的长处，同时也避免了单纯用仿真法的大量计算和理论分析研究复杂问题所遇到的困难。它主要用于研究制造系统的性能指标(生产率等)对参数变化的敏感性，并以此为基础对系统的运行进行优化。其缺点是:对多参数的扰动很难用表或状态方程表示仿真运行过程，扰动较大时，近似度较差。极大代数法用与解决线性系统相类似的方法对DEDS进行建模。它根据系统的运行关系建立起一系列事件发生时间的关系方程。但用极大代数法时，必须在工件加工顺序事先确定的条件下，才能进行建模分析，因而仅适合制造系统的性能分析，而不适合调度。

 (2)数学规划法排队网络(QN)可以分析系统生产率、平均生产时间等，但它很难将车间的其他资源(如AGV等)考虑进去，很难处理系统出现异常时的情况。QN主要用于FMS初步的定性分析[6]、此外，常用的方法还有线性规划(LP)法等。

(3)仿真法仿真是研究DEDS的另一常用方法，较常见的计算机仿真语言如SIMSCRIP-，SIMAN .ECSL，SIMON，SLAM，GPSS等等。仿真法的主要问题是代价高昂。

2.3 SMT产品制造系统车间调度的建模方法
本文提出一种基于对象的Petri网建模的方法。面向对象方法是当前较为先进的建模技术，它的主要思想是将系统所涉及的数据及相关的操作以对象对待，通过消息的传递机制让对象完成其操作。Petri网处理复杂问题的办法是对系统建立层次化和?？榛哪Ｐ?，而面向对象思想可以把各个单元网更好地组织起来，可以直观反映系统的结构和功能分布、并使建模过程符合人们的思维模式。由于Petri网有坚实的数学基础作为依据，能够比较精确地描述系统结构、系统事件之间的顺序或并发关系、资源的约束、事件发生的条件以及引起的后果，并能够进行有效的系统分析和仿真，因而被广泛的应用于FMS 的建模和仿真。而SMT产品制造系统正是比较典型的柔性制造系统，而且 Petri网最重要的应用是系统建模以及在模型基础上对系统进行分析，所以基于对象的Petri网建模方法是二者相结合较为有效的一种方式。
　
3. SMT产品制造系统的Petri网建模
3.1 扩充的面向对象Petri网（EOPN）定义
在一个OPN模型中，一个系统描述为可相互通信的物理对象和它们之间的联系。在进一步引入依赖消息的EOPN中,可作如下定义。
定义1 ： S=(O，R ).
其中，O={Oi | i=1, 2, … , I , I∈N}，Oi是物理对象的EOPN，即EOPNi，Oi就是系统中所有物理对象(EOPNi)的集合。
R={Rij | i,j=1, 2, … , I ,  i≠j , I∈N} ，R是物理对象(EOPNi)间消息传送关系的集合。
定义2 Oi=( Spi, Mpi, Ti, Fi, dep_MPi, dep_Fi, Mo）。

其中，SPi是Oi中的状态库所；MPi是Oi中的消息库所；Ti是活动变迁集；Fi是Oi中活动变迁与状态消息库所之间的输入输出关系；dep_MPi为依赖消息库所集，该集合中某一元素依赖于MPi中某一元素的存在而存在，在EOPN的图形中表为虚线椭圆框；dep_Fi称为依赖消息流关系，它是dep_MPi中某一消息库所到Ti中某一变迁的有序偶集合，即dep_Fi 内含于dep_MPi×Ti， 在EOPN的图形中表为有向虚线；Mo为初始标识。

一个物理对象的行为表现在两个方面，一是其自身内部的行为变迁，二是外部的消息传送。在这里，内部的行为变迁用状态库所和活动变迁来描述，而外部的不同对象间消息的传送和接收是通过消息库所来实现的。如对于消息发送对象Oi、消息接收对象Oj之间的通信用互连关系Rij(i≠j)表示，它定义为Rij={(MPi,Gij,MPj)}，其中Gij是一种特殊类型的变迁，称它为门(Gate)。当在消息库所MPi中有一托肯(token)或由外部指定控制规则时Gij被点火，一个消息库所MPj可以接收一个消息(即token)的条件是消息发送对象中有托肯且Gij可被点火。

3.2 贴片机系统的描述
根据EOPN模型来为一贴片机(SMT)系统建模，以SIEMENSMS-102贴片自动拾放系统为例，其工作平台如图1所示。

贴片机系统是由CAD文件驱动的，该文件包括元件类型名称、元件坐标值、位号等消息,需贴装的元件放在可移动物料区内，机械手在可取区内一定的槽位上吸取一个元件，放置在PCB上的相应位置。当一个料位内的元件取完时，下一个可移动物料区前移进入机械手可取区内?？砂颜飧鎏低晨闯墒怯?a href=https://www.xsjjx.net/ target=_blank class=infotextkey>机械手、可移动物料区PCB轨道组成的。按EOPN模型的要求，可进一步抽象成为四个对象：机械手、PCB轨道、可移动物料区、指令集,其中指令集由CAD文件得到并包含元件所处的物料区号等消息。
图2至图5分别给出了PCB轨道的EOPN模型、指令集的EOPN模型、可移动物料区的EOPN模型和机械手的EOPN模型。

图5中,用虚线椭圆框表示的依赖消息库所MP43,含义是它的存在要依赖于另一个消息库所MP42,即若未产生消息库所MP42,则不会产生依赖消息库所MP43;用有向虚线表示的从MP43到T44的依赖消息流关系含义是,活动变迁T44是否能够发生变迁不完全依赖于消息库所MP43,也就是说,当状态库所P44中有托肯存在时,若这时由于机器出现故障或由于人为干预而使机器暂停,则会产生一消息库所MP42,在故障解除或工作人员查看完毕后发出故障恢复消息,即依赖消息库所MP43,这时T44发生变迁条件满足,机器从刚才暂停处继续工作,否则,未发生故障.若消息库所MP42不存在,则依赖消息库所MP43也不存在,活动变迁T44的发生只与状态库所P44有关。

整个PCB贴装的过程可以描述如图6。其中的PCB放送器、PCB拾取器、PCB轨道、指令集、可移动物料区、机械手以及人等对象的内部行为对外是不可见的，它们之间的通信由消息库所来完成，门负责系统的逻辑控制?？梢晕桓鲋圃煜低持械拿扛龆韵蟮腅OPN建立类库(比如物理对象类、消息类等)，当有一个新的系统需要增加或者要对现有系统进行部分修改时，可从目前已有系统的EOPN类库中派生出所需的EOPN，即，首先构造好新系统的EOPN，或抽取出原有系统中需修改部分的EOPN进行补充修改。然后将它们与原有系统的EOPN结合起来，形成所需新系统的完整的EOPN模型。在这样的系统中，各个EOPN对应的物理设备的功能基本不会发生变化，而因新系统或某些补充部分的引入，故可能引起控制逻辑的改变，这时只须引入一些特殊的门来指定新系统的控制逻辑就可以了，从而提高了EOPN模型的?？樾院涂芍赜眯?。

4. 结 论
本文通过对车间调度问题的分析，得到SMT产品制造企业车间调度的描述。并且针对现有Petri网在建模过程中存在的诸如结点数过多、面对复杂系统的决策能力不强及其关矩阵的空间过大等问题，提出了扩充的面向对象Petri网(EOPN)模型，并建立了一台贴片机系统的完整的EOPN模型。从建模中可以发现，用EOPN建?？梢越低车穆呒丛有苑纸庠诮５牟煌锥魏筒煌牟愦蔚敝?，而且模型结构与系统的实际结构可以很清晰的对应起来，可以很容易地发现模型中错误发生的地方。此外，由于EOPN模型采用分层建模，将方法作为类的子网，而在最终对整个系统，以及分析和性能评价时可以完全不考虑各对象的内部结构，这样使得系统模型的规模与复杂度减小。EOPN模型的建立对SMT产品制造企业车间调度系统的优化及仿真的实现打下了基础，是进行下一步研究的必要条件。

参考文献：

1. 李培根、张 洁. 敏捷化智能制造系统的重构与控制［M］ 北京：机械工业出版社，2003
2. 江志斌. Petri网及其在制造系统建模与控制中的应用[M]. 北京: 机械工业出版社,2004.
3. 范玉顺,曹军威编著. 复杂系统的面向对象建模分析与设计. 清华大学出版社,2000,9
4. 方剑，席裕庚. FMS中的工件调度. 北京:高技术通讯. 2001(7)
5. Zuberek W M. Time Petri nets in modeling and analysis of the simple scheduling for manufacturing cells〔J〕.Computers and Mathematics  with Applications,1999,37(11-12)
6. Champagnat R, Esteban P, Ping aud H, Valette R. Petri net Based modeling of hybrids ystems〔J〕.Computers in Industry,1998,36(1-2)