基于着色Petri网实现A星算法的生产调度优化研究

任 上， 秦江涛

（1.上海理工大学信息化办公室，上海 200093；2.上海理工大学管理学院，上海 200093）

基于着色Petri网实现A星算法的生产调度优化研究

任 上1， 秦江涛2

（1.上海理工大学信息化办公室，上海 200093；2.上海理工大学管理学院，上海 200093）

基于着色Petri网对A星算法进行建模，研究生产调度优化问题.利用着色Petri网的理论优势，简化了大规模复杂工艺生产过程的调度模型过于复杂的问题.直接建立A星算法的着色Petri网模型，对于生产调度研究中的跨平台问题给出了一种解决方法.通过着色Petri网仿真模拟软件CPN Tools构建了基于着色Petri网的A星算法实例和生产调度实例.

着色Petri网；生产调度；A星算法

生产调度问题是多年来的研究热点，其研究方法包括数学规划方法、启发式搜索方法［1-2］、系统仿真方法、人工智能方法及计算智能方法等［3］.近年来，鉴于Petri网具有严格的数学定义和直观的图形表示，能够很好地描述离散系统的同步、并行、共享以及冲突等系统状态，许多学者基于Petri网来研究生产调度问题.基于Petri网研究生产调度问题的方法主要有两种：一是将Petri网作为计算工具，通过Petri网对生产过程建模，计算该Petri网模型的（可达）状态空间，通过启发式算法在状态空间中得到生产调度的最优路径［4］；二是将Petri网模型作为仿真工具，在基于Petri网对生产过程建模的基础上植入系统性能监视器，在仿真模拟过程中实时地对Petri网模型的性能指标数据进行收集，并将信息反馈给智能算法进行生产调度方案评判.一般选择遗传算法作为第二种研究方法中的智能算法［5-7］，其主要流程是将基因编码设计为生产调度问题中的调度策略、调度路径或模型的激发顺序等，将适应度函数设计为调度时间相关函数，通过一定的迭代次数得到调度问题的解.

在上述的第二种研究方法中，利用Petri网作为仿真模拟工具结合遗传算法研究时，对于适用的生产调度问题有局限性.这是由于其基因编码设计中一位基因片段只能对应一个加工机器，所以，该方法只适用于待加工工序只在一种机器上加工的生产系统.然而，近年来基于智能算法的研究占了多数，原因在于基于Petri网模型状态空间和启发式算法的研究目前主要存在两个问题.首先当生产工艺复杂化或者系统规模扩大化后，系统的状态空间呈现爆炸式膨胀，因此，很难直接求解；其次在Petri网建立的状态空间转化为启发式算法的输入数据的过程中，没有专门的软件平台支持，因而实现难度较大［8-9］.本文提出在着色Petri网理论基础上［10］，将生产调度系统的（可达）状态通过着色Petri网中的颜色集来描述，并在着色Petri网中构建了启发式算法的过程，不仅简化了生产调度模型，而且解决了利用启发式算法的生产调度研究中跨平台的问题.最后对一个简单的生产调度实例进行建模.

1 基于着色Petri网的生产调度模型

1.1 着色Petri网

1.2 基于着色Petri网的生产调度模型

现研究生产调度问题，该问题涉及多个工件，每个工件有各自不同的加工路径，加工路径上的操作称为该工件的工序，不同工件的不同工序可以在不同的机器上加工，每台机器一次只能加工一个工件的一道工序.在普通的Petri网建模中，库所存放的托肯是没有颜色的，托肯往往表示的是状态以及个数，生产调度模型所有的工件和工序及其加工操作都由相应的模块组成，模型相对比较复杂和繁琐，本文通过着色Petri网中颜色集的引入，使得模型简单易懂.如图1所示，Job库所存放的是所有工件的工序，Time Info库所存放的是不同工序在不同机器上加工的操作时间信息，Machine库所存放的是加工机器，Consequence库所存放的是加工顺路的记录.其中，TIM E，ORDER，CONSEQUENCE，M ACHINE表示各个库所存放托肯的颜色.

图1 基于着色Petri网的生产调度模型Fig.1 M odel of production scheduling based on colored Petri nets

2 基于着色Petri网实现A星算法

2.1 A星算法

A星算法是人工智能中典型的启发式算法［11］，是状态空间求最短路径最有效的方法之一.A星算法中有一个评估函数f（x）=g（x）+h（x）.其中，g（x）表示从起点到任意结点x的实际距离，h（x）表示任意结点x到目标结点的估算距离.A星算法的总体思路就是从起点开始选取评估函数值最优的结点为当前的最优结点，并扩展该结点寻找下一个最优结点，直到最优节点为终点，最后从终点回溯到起点记录下最优路径，其具体流程如图2所示.S为起始节点，k为实际距离.

2.2 基于着色Petri网对A星算法建模

图2 A星算法流程图Fig.2 Flow diagra m of A star algorith m

如图2所示，将A星算法分解为选择最优结点、判断目标节点、扩展最优节点、更新OPEN表和CLOSED表、回溯最优路径5个算法子模块.这5个算法子模块与图3所示的模型图中ChooseBest，CheckTarget，Explode，CheckSets，CollectPath这5个变迁相对应.在基于着色Petri网的A星算法模型中，OpenSet库所、ClosedSet库所分别代表了A星算法中的OPEN表和CLOSED表，BestNode库所存放当次迭代中的最优节点，NextNode库所存放当次迭代中最优节点的后续结点，Path库所存放搜索出的最优路径.

图3 基于Petri网实现A星算法的建模Fig.3 M odeling of A star Algorith m in colored Petri nets

3 基于着色Petri网实现A星算法实例

每一个算法单元都是由一个变迁和若干库所组成，而算法单元的函数功能就是由变迁中的变迁函数体现的.在算法单元设计之前，首先要定义算法单元之间传递数据的数据类型，在着色Petri网中就是定义库所中托肯的颜色.

3.1 生产调度问题描述与颜色集定义

生产调度问题中的单个工件的状态可以用工件、工序和加工机器这3个参数来描述，其颜色定义为PRO=product JOB*N U M*M ACH，其中，JOB，N U M，M ACH是分别代表工件、工序、加工机器的枚举型颜色集.A星算法中的结点包含生产调度系统的状态信息，系统状态由所有工件的状态叠加而成，假设现要加工2个工件，那么，记录系统状态和评估函数f值的颜色定义为FX=product PRO* PRO*IN T.表1与表2分别为待加工的2个工件的工艺以及加工时间.在A星算法中从起点搜索到终点后，需要通过结点信息追溯路径，需要每个结点都记录其父亲结点，因此，将A星算法单元间传递的颜色定义为NOD=record fath：FX*self：FX.定义LNOD=list NOD为NOD类型数据的列表.

A星算法的子算法单元包括选择最优结点单元、检查目标结点单元、扩展结点单元、更新OPEN表和CLOSED表单元以及回溯最优路径单元.本文仅重点介绍扩展结点单元以及更新OPEN表和CLOSED表单元.

表1 生产调度问题中的产品工艺描述Tab.1 Product operation description in production scheduling problem

表2 生产调度问题中的工序时间描述Tab.2 Operation time description in production scheduling problem

3.2 扩展结点单元

扩展结点单元的功能是根据工件工艺信息，扩展当前最优结点，并计算它们的评估函数f值.

如图4所示，扩展结点单元由Explode变迁以及TempSet，Info，NextNode库所组成.TempSet库所传递的是当前的最优结点，Info库所包含工艺和加工时间的信息，通过Explode变迁的激发，生成扩展结点存放到NextNode库所.

Explode变迁的变迁函数为List.drop（foldr insert2（foldr insert1 templistinfo）info，1）

其功能为扩展当前的最优结点，其具体操作是通过insert1函数查找所有第1个工件的下一步工艺，insert2函数查找所有第2个工件的下一步工艺，来查找该工件所有可能的下一步加工工艺的过程.

图4 扩展结点单元Fig.4 Exploding nodes unit

3.3 更新OPEN表和CLOSED表单元

更新OPEN表和CLOSED表单元的功能主要是将最优结点的后继节点放入OPEN表中，如果后继结点已经存在于表中，则比较f值，选取f值较小的结点.

如图5所示，CheckSets变迁的变迁函数由2个子表达式组成，分别是生成newopen列表的表达式：foldr opencheck opensets nextnodes以及生成newclosed列表的表达式：foldr closedcheck closedsets nextnodes.其中opencheck和closedcheck为函数名，它们的定义为

如果扩展结点已经存在于OPEN表，则在OPEN表中留下评估函数f值较小的结点.如果扩展结点已经存在于CLOSED表，则比较2个结点的评估函数f值.如果扩展结点的f值较大，则忽略，因为已经有更优的路径到达该结点；如果扩展结点的f值较小，则从CLOSED表中删除该结点，并将其加入OPEN表，因为，CLOSED表中包含该结点D，说明该结点重新返回OPEN表后其f值仍然是最小的，因此，该结点会在下一步迭代中成为最优结点.

图5 更新O P E N表和CL OSE D表单元Fig.5 Updating of table O P E N and table CL OSE D unit

3.4 完整的A星算法

将全部算法单元合并在一起可以得到A星算法网络.为了避免各单元之间的运行顺序失常，给予各单元各自的优先级如图6所示（见下页）.Petri网中优先级的具体定义为，当多个变迁的输入弧表达式不为空且守卫函数为真时，优先级最高的变迁使能，当多个变迁的优先级同时最高时则同时使能.

如图6所示，A星算法网络中TargetState库所、Info库所及OnePath库所由蓝色标签标记. TargetState库所及Info库所分别存放着生产调度系统的目标状态及工艺信息，是A星算法网络的外部输入，OnePath库所则作为存放调度队列的库所，是A星算法网络的外部输出.图7（见下页）为在着色Petri网中生产调度模型与A星算法模型的组合模型，可以看出，使用着色Petri网构建A星算法网络，从全局建模的角度具有结构简单、应用方便的优势.研究设备控制、系统应急等问题时，在不修改A星算法网络的前提下，只要对生产调度系统建模中A星算法网络的使用稍加调整，就可以实时交互系统状态信息与A星算法的计算信息，模拟不同的系统状况.

图6 A星算法在着色Petri网中的建模实例Fig.6 M odeling exa m ple of A star Algorith m in colored Petri nets

图7 生产调度与A星算法在着色Petri网中的建模Fig.7 M odeling of production scheduling with A star algorith m in colored Petri nets

4 结束语

利用着色Petri网中颜色集的优势简化了生产调度模型，利用CPN Tools建模仿真软件对生产调度过程以及A星算法实例建模，使得基于A星算法的生产调度研究能够在统一的着色Petri网平台上进行，克服了跨平台研究的不便.

［1］ 刘长平，叶春明.求解置换流水车间调度问题的布谷鸟算法［J］.上海理工大学学报，2013，35（1）：17-20.

［2］ 傅家旗，叶春明，赵伟民.混合量子算法在生产调度中的应用［J］.上海理工大学学报，2009，31（6）：557-561.

［3］ 马正元，王伟玲，王玉生.生产调度问题的系统研究［J］.成组技术与生产现代化，2005，22（1）：10-14.

［4］ 徐俊刚，戴国忠，王宏安.生产调度理论和方法研究综述［J］.计算机研究与发展，2004，41（2）：257-267.

［5］ 王国新，宁汝新，王爱民.基于仿真的生产调度优化技术研究［J］.计算机集成制造系统，2007，13（7）：1419 -1427.

［6］ 郝东，蒋昌俊，林琳.基于Petri网与GA算法的F M S调度优化［J］.计算机学报，2005，28（2）：201-208.

［7］ 周卫东，杨加敏，贾磊，等.一种Petri网结合遗传算法的优化方法及应用［J］.山东大学学报（工学版），2005，35（4）：59-63.

［8］ 薛雷，郝跃.基于Petri网的启发式生产调度［J］.自动化学报，2002，28（5）：827-831.

［9］ 江志斌.Petri网及其在制造系统建模与控制中的应用［M］.北京：机械工业出版社，2004.

［10］ Jensen K.Colored Petri nets：a high-levellanguage for system design and analysis［J］.Computer Science，1991（483）：342-416.

［11］ 蔡自兴.人工智能及其应用［M］.北京：清华大学出版社，2007.

（编辑：石 瑛）

A Star Algorith m for Scheduling O ptimization Based on Colored Petri Nets

REN Shang1， QIN Jiang-tao2
（1.Inform atization Office，University of Shanghai for Science and Technology，Shanghai 200093，China；2.Business School，University of Shanghai for Science and Technology，Shanghai 200093，China）

The scheduling process and A star algorithm were modeled based on colored Petri nets. The complexity of scheduling process resulting frommass scale and complicated procedures of manufacturing systemwas decreased by taking the advantage of colored Petri nets theory. Moreover，the A star algorithm was modeled based on colored Petri nets directly in order to solve the problemof doing production scheduling on some different software platforms.Apretical modelling example of scheduling and A star algorithm was conducted colored Petri nets by use of the modeling and simulation software CPN Tools.

colored Petri nets；scheduling；A star algorith m

TP 311.1

A

1007-6735（2013）05-0463-06

2012-08-11

国家自然科学基金资助项目（71071097）

任 上（1988-），男，硕士研究生.研究方向：制造系统生产调度方法及性能分析.E-mai l：shawn_ren＠163.com