1、仓储物流设计面向仓储物流的建模及控制系统设计方法 (1中山大学信息科学与技术学院，广东广州 510006；2中山大学数字家庭教育部重点实验审，广东广州510006；3广东商学院广东省电子商务市场应用技术重点实验室，广东 广州 510320；4山东大学现代物流中心，山东济南250061)摘要：为提高现代企业仓储物流的设计质量和效率，提出了一种基于资源颜色时序信号的扩展Petri网建模及控制系统设计方法。该方法首先采用资源颜色时序信号的扩展Petri网建谚r仓储系统的动态模型，清晰地描述了各种物流活动的顺序、并发、冲突等关系，并结合关联矩阵，阐述了判断死锁和陷阱的方法。该方法建、l，的模型可根据P
2、etri网运算规则进行保性化简，便于仿真分析和验证，且可直接用于系统口f编程逻辑控制器的控制程序设计。最后，以仓储物流控制系统为例，阐述了系统建模及控制设计过程。关键词：物流；自动化仓储系统；Petri网；可编程逻辑控制器；梯形图；建模中图分类号：TP3919；TP273；TM571 文献标识码：AModeling and controlprogram design of automated storage and retrieval systemXU Xiao-wei 1。LIANG Yinghon93，WUYao-hua(1School of InformationScienceTechn
3、ology，Sun Yatsen University，Guangzhou 510006，China；2Key LaboratoryofDigital Life(Sun YatsenUniversity)，Ministryof Education，Sun Yat-senUniversity，Guangzhou5 1 0006，China；3Guangdong Key Lab of Electronic Commerce MarketApplication Technology，Guangdong University of BusinessStudies，Guangzhou510320，Chi
4、na；4The Logistics Institute，Shandong University，Jinan 250061，China)Abstract：To improve the design efficiency and quality of logistics controlsystemin modern manufacturing enterprises，a modeling design method based on Signal Timed Colored Resource Petri Nets(STCRPNs)for AutomatedStorageand Retrieval
5、System(ASRS)was put forwardThis method used STCRPNs to construct the dynamicmodel of ASRS，which could clearly denote various logistic movements and the sequence，concurrence，conflict relationships among them in ASRSAnd by combining association matrix tools，the method tO judge deadlock andtrapin the m
6、odel was explainedThe dynamic model could also besimplified according to Petri Nets calculation rulesSO as to convenientlyconduct simulation analysis and verificationAnd the STCRPNs model could directly appliedtodesignthe programmable logic controller control programA casestudyon areal application w
7、as provided for interpreting the modeling design processKey words：logistics；automated storage and retrievalsystem(ASRS)；petri nets；programmable logic controller；ladder diagram；modeling收稿日期：200812-29；修订日期：20090522。Received 29Dec2008；accepted 22 May 2009基金项目：国家自然科学基金资助项目(50175064)，NSFC-广东联合基金资助项目(U073
8、5001，U0835004)；国家863计划资助项目(2006CB303106)。Foundation items：Project supported by the National Natural Science Foundation，China(No50175064)，the NSFCGuangdong Joint Fund，China(NoU0735001，U0835004)，and the National High-TeehR&D Program，China(No2006CB303106)作者简介：许晓伟(1977一)，男，山东泰安人，中山大学信息科学与技术学院博士后，主要从事现代物
9、流、图像识别、人工智能等的研究。E-mail：mrxxw163corn万方数据计算机集成制造系统 第15卷O 引言在全球市场竞争日趋激烈、供求关系飞速变化的产业环境中，自动仓储系统(Automated Storageand Retrieval System，ASRS)在现代企业物流和电子商务中得到了广泛应用，已成为企业生产自动化和管理信息化的标志之一。ASRS以其出入库台、输送机、堆垛机、自动导引小车(Auto GuidedVehicle，AGV)等多种设备构成了物料输送线，将企业生产线、配送线和立体仓库紧密连接在一起。现代企业制造的最主要特点是批量小、品种多时问性要求高，由多种生产工艺流程和
10、物料传输流程组成，系统运行因此变得十分复杂m2|。如何快速地挖掘出ASRS中的瓶颈和关键路径。优化运行方案，充分挖掘资源潜力，降低能耗，以实现多路径的物料输送平衡、资源平衡、时间平衡，是仓储物流控制系统设计中的主要问题。本文针对ASRS控制设计任务，提出了一种基于资源颜色时序信号的扩展Petri网(Signal Timed Colored Resource Petri Nets，STCRPNs)的建模设计方法，能够将模型映射为可编程逻辑控制器(Programmable Logic Controller，PLC)控制程序，并在实际应用中得到了验证。1相关研究对于这类离散事件动态系统问题，国内外学
11、者基于Petri网理论进行了大量的研究，目前主要集中在仓储物流系统模型的调度策略和动态性能评估问题上。例如文献3采用颜色Petri网构建了ASRS的动态模型，并提出了一种出库入库调度策略来实现系统的最大吞吐量。该模唰既可用于系统设计阶段离线性能评估，也可用作系统在线监控。文献4-i和文献5则将面向对象(Object Oriented，OO)技术引入ASRS建模过程中，使所建立的模型具有更强的可重用性和可操作性。在简化Petri网模型方面，颜色方法优于OO方法，但在实际建模过程中随着颜色粒度大小的不同，出现了各种各样的着色方法63。考虑到ASRS中每个任务的完成都需要一定时间，文献7引入了时间要
12、素，以堆垛机和小车作为托肯，任务路径作为颜色，建立了着色赋时Petri网(ColorTime Petri Net，CTPN)动态模型。在动态性能分析方面，文献1-83首先提出了基于Petri网的运输时间模型及演绎模型。对堆垛机运行进行建模，通过模型分解和仿真验证寻求系统最优控制策略，之后又进一步发展了随机颜色Petri网理论9，利用随机Petri网与马尔可夫链的同构等价关系，通过可视仿真器PACE 31分析时间性能和资源利用率。文献10则利用有限状态机和模块化的CTPN建立了Matlab状态流仿真环境，分析了多种调度策略对系统性能的影响。由于仓储物流系统的资源约束性，回路环路“死锁”的检测和消
13、除一直是调度控制策略研究的热点问题。文献11采用面向资源的Petri网构建了AGV路径的关系模型，分析了小车回路环路死锁的条件和消除算法，但没有说明小车路径的关联关系，而且包含多种设备的ASRS比单一的AGV系统复杂，该方法计算量大且困难。文献123将广义互斥约束概念扩展到CPN模型，提出了防止环路一级死锁和二级死锁控制的策略，并应用到火车行驶路径调度中，但也未能彻底避免死锁。文献1-133提出的控制策略利用多容量库所作为缓冲区，当有多辆小车作业时有利于避免死锁，但无法检测出环路临界状态。文献E143采用库所双重着色的CTPN方法，结合有向图工具，阐述了有轨小车(Rail Guided Veh
14、icle，RGV)系统的环路死锁原因和系统无死锁的充要条件，并提出一种死锁控制方法，但是该方法假定系统中只有一台升降机，并且不考虑RGV小车运行过程中的时间延迟等冈素。上述方法均是面向仿真验证的建模方法，在系统仿真过程中应用控制策略来解决“死锁”等调度问题，并不适于仓储物流实际控制系统的设计开发。迄今针对ASRS控制系统设计的动态模型均尚未进行深入的研究。目前，在工业控制系统上，PLC以其高重用性代替了硬接线式的控制继电器。IEC 611313标准采用五种PLC程序设计语言：指令列表(instruction list)、结构文本(structuredtext)、功能块图(function bl
15、ock diagram)、序列功能表(sequential function chart)和梯形图(1adder diagram)。但这些都是低级语言，整个设计开发工作量较大，在很大程度上依赖于工程师的个人经验，即时间、人力成本昂贵，并且控制系统验证工作一般只能通过多次仿真和现场试验方式进行。因此，使用Petri网作为PLC程序建模、分析和设计的自动化工具已经成为一种研究趋势。文献15提出了一种信号解释Petri网(Signal Interpreted Petri Nets，SIPNs)，该模型能够处理输入输出信号，并可通过一种图形化编辑器转成指令列表形式的PLC程序。万方数据第12期 许晓伟
16、等：面向仓储物流的建模及控制系统设计方法但指令列表形式的程序难以理解，而梯形图采用“软件设备”来模拟硬接线式继电器的梯形逻辑配置n6|，被业界工程师广泛地接受和使用。文献17使用Petri网模型为一小型机器人设计和实现了一种顺序控制器，直接生成关联的梯形图程序，但该方法仅在操作逻辑简单的教育系统中得到了应用。文献18对使用Petri网和梯形图进行控制系统设计的多种方案进行了深入对比分析后指出，无论是采用用户友好的高级语言或者硬件配置来产生Petri网控制器用于验证、分析和调试，还是反过来由PN网模型生成PLC控制程序，这一相互转化过程应该是可验证和自动化的。文献19针对敏捷制造系统提出了一种“
17、一对一”映射技术，将制造系统Petri网模型转化为相应的PI。C梯形图程序，但是该方法缺乏一致性，也不能处理实际仓储物流系统复杂的调度和控制情况。在实际应用中笔者注意到：系统的托盘化货物在仓储没备上的物流运输类似于Petri网中的标记在库所之间的变迁活动，由此提出了一种面向仓储物流的STCRPNs建模设计方法，所建立的系统动态模型清晰地描述了各种物流活动，并可以处理活动之间的顺序、并发、冲突关系，以解决系统“死锁”和“陷阱”问题。更重要的是，本文引进了事件和条件信号概念，使该方法除了可以用于仿真验证外，还可以采用元素对应映射方法，直接转化为控制系统PLC程序，有效降低了控制系统的开发、调试和业
18、务流程再设计成本。本文的研究对象是单容量资源控制系统，即系统中每个设备资源容量为1，这一设定也符合一般的仓储物流系统。2仓储物流系统简介一个典型的自动化仓储物流系统有堆垛机、输送机、RGV或AGV等设备，包括入库和出库两个工作流程。图1中的入库流程是将货物装在从空托盘区取来的空托盘上，从入库口输送机1(链式或棍子)入库。在经过输送机2后，按照入库货物的仓库排号，选择不同的出入库台。一般立体仓库的每个巷道对应一台堆垛机和两个出入库台，一个为人库台，一个为出库台，出入同一巷道、不同排号的货物选择相同的出入库台。货物到达入库台位置后，该巷道的堆垛机如果空闲，就把货物送到正确的仓库货位(排号、层号、列
19、号)。例如：某货物的仓库货位是P(3排2层5列)，入库路径为R(输送机1，2，4，6，7，8和堆垛机2)。出库流程一般指把生产线(或配送线)上需要的货物从立体仓库中取出，送到生产线(或配送线)附近的缓冲站上。例如：堆垛机1按出库指令从指定货位P(2排3层6列)上取来货物，送到该巷道对应的出库台输送机5，然后经输送机6，7，9，11，到达出库口输送机12，再由一台AGV或者其他车类(如RGV、叉车)送到指定的缓冲站，简单的也可以是经由传送带。缓冲站卸完货后，剩下的空托盘送上缓冲站，经AGV送至输送机13，然后由空托盘返嘲输送机14，15，16送回空托盘区，从而完成一个完整的物流过程。缓冲站3缓冲
20、站2图1典型自动化仓储物流系统布局图3面向仓储物流的建模Petri网理论是由德国Carl Adam Petri博士于1962年提出的一种完善的图形化数学工具20j，适于描述和分析具有同步、通讯、资源共享等特点的并发过程系统。下面首先介绍一些Petri网的基本概念和符号，更多信息可参考文献21和文献22。31 Petri网基本定义定义1一个Petri网表示为一个五元组N一(P，丁，J，O，Mo)。其中：P=P。，P2，P。)为一组库所集，mo；T一t1，t2，t。)为一组变迁集，咒0，PU T彦，P n T一髟；工为PTN的输入弧，它是从库所集到变迁集的一个映射，J(P，)为从库所P到变迁t的输
21、入弧权值；0为TPN的输出弧，它是从变迁集到库所集的一个映射，o(t，P)为从变迁t到库所P的输出弧权值；Mo：PN为初始标记，其中M(p。)表示库所P，中的标记(Token)数，i一1，2，m。定义2一个Petri网N一(P，T，J，O，Mo)，如万方数据计算机集成制造系统 第15卷果J(P，t)一0，1)，且O(t，P)一0，1)，则为普通Petri网。定义3一个Petri网N一(P，T，J，0，M0)，如果tT，J()n 0()一彩或者PP，I(户)n O(p)一力，则为纯Petri网。Petri网作为一种图形化建模工具，用圆圈表示库所，圆圈中的圆点数表示库所拥有的标记数，描述了系统的状
22、态；用栅条表示变迁，用带箭头的弧线表示输入输出弧，反映了系统的动态行为。系统状态的变化，表现为标记通过变迁在库所之间转移，其变迁规则为：如果M(p)J(P，)，则变迁t是使能的；使能变迁t发生后则有M 7(户)一M(户)一I(p，)+O(f，p)。32仓储物流系统资源Petri网建模由于仓储物流系统中设备资源的有限性，本文也采用了有限容量的资源Petri网(Resource PetriNets，RPNs)来描述系统。与其他Petri网表示资源方法3,7,12-133不同，本文的具体方法是：将系统中的每个运输设备(轨道输送机、堆垛机、AGV、RGV等)表示为一个有限容量的库所P资源，每个设备中的
23、货物表示为库所P的标记托肯，货物的数量表示为库所P的标记数M(P)，每两个设备之间货物的交接运输表示为变迁t，源设备上货物的输出表示为变迁t的输入弧J，目的设备上货物的输入表示为变迁t的输出弧o，即图1中的典型仓储物流系统可用图2中的RPNs模型表示。图2仓储系统RPNs模型如果某个设备资源库所P的容量Max(户)与其中的标记数M(声)满足Max(p)M(p)，则称相关变迁t是资源使能的。为简化系统复杂性，一般可将资源库所P的容量设定为1(Max(户)=1)，即每个设备仅容纳一件货物。由于仓储系统中的设备为专一使用，每件货物只能在两个设备之间进行运输交接，即输入弧J和输出弧。是唯一的。因此RP
24、Ns模型是一个纯的普通Petri网(如图2)，它清晰地描述了系统中各种物流活动，以及活动之间的顺序、并发、冲突关系(图2中的各元素具体含义如表1)，并可以唯一地表示成关联矩阵形式：ACad。，i1，2，z，歹1，2，m)。 (1)其中：a。=砖口i，P，P，t。T，+ f 1(r，Pi)0一 f1(户，f)J口j21 0其他 川“一1 0其他。(2)裹1 Petri网模型元素描述元素 描述户1，户2P16P17，PlsP19fl，t2t4t5，t6t7f8，t9tlot13t14t15t18rio，t20t3ttlt5t12tiet17tz2，tzd,tz3，t2st21t26tz7tz8系统
25、巾具有无限容量的虚资源，包括立体仓库货架，缓冲区、空托盘区等输送机116堆垛机12AGV货物在输送机甘J运输的事件堆垛机取输送机上货物的事件堆垛机向输送机卸货的事件AGV取出库口输送机12上货物的事件AGV向输送机13卸载空托盘的事件堆垛机将货物存到立体仓库货架的事件堆垛机拣选立体仓库货架上货物的事件货物装在空托盘l：放置到入库u输送机1上的事件AGV卸载货物到指定缓冲站的事件AGV取缓冲站空托盘的事件输送机16上的空托盘卸载到夺托盘区的事件通过关联矩阵可以分析模型的结构性质，如复杂仓库物流系统中经常出的“死锁”和“陷阱”，可根据判定定理l被检测出来。定理1一个Petri网N=(P，T，f，O
26、，Mj)，A为N的关联矩阵，Pi一PP挖，P*)为N的一个库所子集，则P；为网的一个死锁(陷阱)的充分必要条件是：A关于P，的列生成子阵A。，A。，At万方数据第12期 许晓伟等：面向仓储物流的建模及控制系统没计方法中，每个非全零行至少包含一个“一1”(或“1”)元素。根据Petri网的运算规则，此RPNs模型可进行保性化简，以便分析与仿真。由系统中设备资源库所的所属分类，图2中的模型可化简为图3所示的输送机系统子网PN。、堆垛机系统子网PNs、AGV系统子网PNA等子系统Petri网模型的组合。通过化简的RPNs模型，可以看到各个库所容量和库所资源的总量不变；变迁分为子网内部和子网间的，变迁
27、规则不变，变迁发生的条件也相同，原始模型的结构性质得到保持，物流信息的表示更为清晰和直观。图3仓储物流系统RPNs简化模型33仓储物流系统颜色和时序建模由RPNs模型性质和变迁规则，可推出物流设备间货物运输的必要条件：源设备上有货，目的设备上无货。但仅此还不能充分描述变迁事件发生的充分条件。例如，众所周知的“死锁”和“陷阱”现象是由Petri网中“分支”和“会合”两种冲突关系造成的(如图4)，它们在网络中共享输出和输入资源库所，对变迁的发生有着严格限制条件。为此，本文在RPNs中引入颜色和时序元素。镪 屯 内 见忪训两 肋t2a分支 b会合图4 Petri网冲突芙系定义4一个着色资源Petri
28、网(Colored Resource Petri Nets，CRPNs)表示为一个六元组N一(P，T，C，J，0，M0)。其中C是库所和变迁的颜色集：C(Pf)一aa扪，a钿一1，a钿)，i一1，2，m为颜色数；C(tj)=bjl，bj2，b如一l，靠)，歹=1，2，竹为颜色数；J：C(夕)C()一N(非负整数)为输入映射，取颜色a。时的P；到取颜色b业时的t的输入连接数记为，(n西，bj,)；0：C()C(户)一N(非负整数)为输出映射，取颜色b球时的t，到取颜色口小时的Pi的输出连接数记为0(bjk，a卉)。在CRPNs模型中，根据每个标记的目的属性赋予其相应的颜色Map(M，C)，来规定
29、它参与相应颜色的变迁，并经历相应颜色的库所，最终到达目的库所。例如：图2中，不妨令C(P：)一a。，a：)，C(2)一a1)，C(t4)一a2，C(P7)一a3，a4，C(tlo)一a。，C(t。)一a。)，当库所P。的标记颜色为a。时(Map(Mp2，C)一口I)，颜色为a。的变迁t2可发生(C(f：)一口。)，则称变迁t2是颜色a。使能的。如果库所P。的标记颜色为az时(Map(Mp。，C)一az)，颜色为a：的变迁t。可发生。这就解决了图1中货物在输送机2和6上的分叉运输问题。定义5 一个时序着色资源Petri网(TimedColored Resouree Petri Nets，TCRP
30、Ns)表示为一个七元组N一(P，T，C，J，o，D，M0)。其中：D一d。，i一1，2，行：PN(实数)，为库所的时间集合(Z为P，的时延)。为每一库所引入一时延，代表变迁事件发生经历的时间后产生新的状态所需要的时间。规定标记工作时间等于其产生时间加上其所在库所的时延。如果两个输入库所都具有标记，能使变迁发生来竞争共享的输出库所，则较早工作时间的标记有优先权，即先入先出(FirstIn FirstOut，FIFO)规则。例如：假设图2中d。一3，d515，t。和t；同时发生，即在图l中同时有货物Tokenl和货物Token2分别从输送机2一输送机4和堆垛机1一输送机5，货物标记先到输送机2，货物标记2后到输送机5，标记1的工作时间早于标记1的工作时间，则货物标记l优先发生变迁，t，
