基于时延库所Petri网的动态联盟任务调度研究

黄 彬1, 2，高诚辉1, 2，陈 亮1



基于时延库所Petri网的动态联盟任务调度研究

黄 彬，高诚辉，陈 亮

（1. 福州大学机械工程及自动化学院，福建福州 350108；2. 福建省制造业数字化设计工程研究中心，福建福州350002）

针对动态联盟中任务调度的特点，提出了采用时延库所Petri网对动态联盟任务调度进行建模。给出了模型的形式化描述及变迁规则，对动态联盟中的产品加工类型进行了分类，并建立了各种加工类型的时延库所Petri网模型，分析了通过模型中零时差的库所求解关键路径和利用可达图求解合理调度方案的方法。最后，以实例表明了该方法的可行性和有效性。

任务调度；时延库所Petri网；动态联盟

敏捷制造是美国于1991年在“美国21世纪制造战略报告”中提出的一种新的制造模式，被称为“21世纪制造企业的战略”。在敏捷制造模式下，借助动态联盟这种组织形式，盟主企业通过快速集成动态联盟内各成员企业的核心优势，进行快速的产品设计、制造、销售和服务，向用户提供各种符合个性要求的定制化产品，使企业能够从容应对快速变化的市场需求，最终赢得市场竞争。对于敏捷制造而言，生产运作仍然是其最基本的活动，要实现敏捷制造的目标，关键在于如何组织来自于动态联盟内不同企业实体的各种资源，快速实现共同的市场机会。

动态联盟中的任务调度（企业间的调度）与传统的车间调度不同。首先，动态联盟中的各成员企业都是利益自治体，相互之间不存在强制的集中式控制（包括盟主企业对成员企业）。其次，每个成员企业只负责整个产品的某个或某些部件的生产，成员之间对各自内部的生产过程不了解。但由于不同产品部件的生产存在时序约束关系，使得成员企业不能不考虑其他成员企业的生产进度对本企业生产过程的影响以及本企业的进度对整个联盟的影响等，这就要求成员企业之间的生产过程必须彼此协调，因此动态联盟企业的调度问题对传统的生产调度方法提出了新的挑战。通常采用的解析法、神经网络、遗传算法等纯数学方法已不能解决动态联盟企业任务调度的问题。

Petri网是联邦德国的Carl Adam Petri教授于1962年首次提出的一种网络理论，它是一种图形化的建模工具，特别便于描述分布式系统中进程或部件的顺序、并发、冲突以及异步关系。为了模拟和分析系统在时间层次上的关系，又定义和研究了各种含时间因素的Petri网。目前，研究人员在基于Petri网模型的调度方法方面做了很多工作，但多见于车间调度问题。本研究采用时延库所Petri网对动态联盟任务调度进行建模，建立了动态联盟中各种加工类型的时延库所Petri网模型，所有变迁的触发都是瞬时的，通过在库所上增加一个延时来描述动态联盟任务进行时的持续时间。

1 基本概念

定义1 时延库所Petri网是一个六元组

TPPN= (,,,,,)

式中为TPPN的库所集，表示某项任务，用布尔量表示，容量为1；为TPPN的变迁集，表示某项任务的开始或结束，和满足；：，：，这里，和的权系数均为1；：→（为非负整数集），表示所有库所的时延集，即完成中托肯所对应的任务需要的时间；为系统的初始标识。TPPN是一个出现网，即TPPN满足：

在敏捷制造模式下，由于许多任务都是一次性的，完工时间的不确定性较大，所以一般给出3个估计值：，，，其中表示最乐观时间，表示最保守时间，表示最可能时间，然后应用概率的方法计算各项任务时间的期望平均值，任务时间的期望平均值，TPPN网中的指的就是任务完成时间的期望平均值。

定义2 变迁触发条件

定义3 变迁触发结果

如果在下可以被激活，当前标识相应改变为后继标识，有并且，中的托肯经过时延后可用，这一变迁可以表示为[。

2 基于时延库所Petri网的任务调度建模

一项需敏捷制造完成的产品经过分解成若干个零部件后，即形成了若干个加工任务，由若干个相应的联盟成员完成。动态联盟内，在产品的完成过程中包含了以下几种加工类型：一般加工、顺序加工、并行加工、装配。一般加工指一个零部件的完成对应于一个加工任务，该加工任务由一个联盟成员负责完成；顺序加工指一个零部件的完成对应于若干个加工任务，每一个加工任务由一个联盟成员负责完成，并且在每一个加工任务间存在前后道工序关系；并行加工指若干个加工任务在某个时间段可以同时进行；若干个零件经由装配环节形成部件，若干个部件经由装配环节形成更大的部件，直至最终形成整个产品。

一般加工的TPPN模型可用两个变迁t和t以及一个库所表示，如图1所示。其中t表示加工任务的开始，t表示加工任务的结束，库所中有一个托肯时表示加工任务正在进行，的时延d表示从t发生（获得托肯）开始，至少要经过d个时间单位，t才能发生。

图1 一般加工的TPPN模型

顺序加工的TPPN模型如图2所示。该模型表示加工任务是加工任务的前道工序，d表示零部件从完成任务的加盟成员到达承担任务的加盟成员所需的物流时间。当d＝0，即不考虑物流时间时，可将p去除，加工任务的t和加工任务的t重合，图2简化为图3所示。由于物流时间的不确定性和网模型的复杂性，本研究不考虑物流时间因素，即顺序加工的TPPN模型以图3为据。

图2 顺序加工的TPPN模型

图3 不考虑物流时间的顺序加工TPPN模型

图4 并行加工的TPPN模型

表示由两个一般加工任务完成的零部件组成装配的TPPN模型如图5所示。存在装配关系的两个零部件1和2都完成后，装配才能开始，用t表示，经时延d，装配结束于t。

图5 装配的TPPN模型

3 TPPN任务调度模型的分析与求解

3.1 模型的分析

（2）

（3）

（5）

（6）

3.2 模型的求解

具体的模型求解步骤如下：

（1）根据已知的、、值，计算各任务完工的期望平均时间和方差。

（2）画出产品加工的TPPN模型。

（3）以各任务完工的期望平均时间作为完工时间，根据公式(1)~(4)计算出TPPN模型中的、以及，并求出产品的关键路径。

（4）画出TPPN模型的可达图，并根据公式(5)、公式(6)求出图中的和。

4 实 例

针对市场机遇，若干家企业组成动态联盟生产某产品。产品分解后得到的加工任务，各任务之间的前后工序关系、各任务的、、值及经计算得到的各任务的期望平均工期如表1所示。

由表2得产品加工的关键路径为：A→B→H→F→G→L。

表1 产品的任务组成、任务的前后工序关系及工期

图6 产品加工的TPPN模型

从表3可以看出，合理的M为：M、M、M、M、M、M、M、M、M、M。M的存在时间区间为[0,6]，从图7知道，在M状态下，只有任务A进行；M的存在时间区间为[6,13]，在M状态下，只有任务B进行；M的存在时间区间为[13,27]，在M状态下，任务C、D、H、I、J并行进行；M的存在时间区间为[21,32]，在M状态下，任务C、E、H、I、J并行进行；M的存在时间区间为[23,27]，在M状态下，任务C、D、H、I、K并行进行；M的存在时间区间为[32,36]，在M状态下，任务C、F、I、J并行进行；M的存在时间区间为[23,32]，在M状态下，任务C、E、H、I、K并行进行；M的存在时间区间为[32,40]，在M状态下，任务C、F、I、K并行进行；M的存在时间区间为[40,51]，在M状态下，任务C、G、K并行进行；M的存在时间区间为[51,55]，在M状态下，只有任务L进行。

合理的调度方案有三种：

M→M→M→M→M→M→M→M

M→M→M→M→M→M→M→M

M→M→M→M→M→M→M→M

由此，画出任务调度的Gantt图，如图8所示。

图7 图6的可达图

表3 图7中Mi的ES(Mi)和LF(Mi)值

图8 任务调度的Gantt图

5 结束语

本研究利用时延库所Petri网对动态联盟的任务调度进行了建模分析与求解，反映出了其中多任务间的并发、异步等动态行为，该模型不仅可以及时了解产品各个组成部分的生产进展，也可根据实际生产状况动态修改原计划调度或进行再调度，以适应不断变化的新环境，提升企业的敏捷性。

[1] 罗振璧, 汪劲松, 周兆英, 等. 灵捷制造——21世纪制造企业的战略[J]. 机械工程学报, 1994, 30(4): 1-6.

[2] Yusuf Y Y, Sarhadi M, Gunasekaran A. Agile manufacturing: the drivers,concepts and attributes [J]. International Journal of Production Economics, 1999, 62: 33-43.

[3] [美]Rick Dove. 敏捷企业(上)[J]. 张申生译. 中国机械工程, 1996, 7(3): 22-27.

[4] 袁崇义. Petri网原理与应用[M]. 北京: 电子工业出版社, 2005. 2-7.

[5] 吴哲辉. Petri网导论[M]. 北京: 机械工业出版社, 2006. 1-19.

[6] Murate T. Petri nets: properties, analysis and applications [J]. Proceedings of IEEE, 1989, 77: 541-580.

[7] Bowden F D J. A brief survey and synthesis of the roles of time in Petri nets [J]. Mathematical and Computer Modelling, 2000, 31: 55-68.

[8] Lee D Y, Dicesare F. Scheduling flexible manufacturing systems using Petri nets and heuristic search [J]. IEEE Transaction on Robotics and Automation, 1994, 10(2): 123-132.

[9] Chen J H, Fu L C, Lin M H, et al. Petri-net and GA-based approach to modeling, scheduling, and performance evaluation for wafer fabrication [J]. IEEE Transaction on Robotics and Automation, 2001, 17(5): 619-636.

[10] Mahas G, Parisa A B, Peter L, et al. Petri-net based formulation and algorithm for short-term scheduling of batch plants [J]. Computers and Chemical Engineering, 2005, 29: 249-259.

Research on Virtual Enterprises Task Scheduling Based on Timed Place Petri Net

HUANG Bin,GAO Cheng-hui, CHEN Liang

( 1. College of Mechanical Engineering and Automation, Fuzhou University, Fuzhou Fujian 350108, China; 2. Fujian Province Digital Design Center for Manufacturing, Fuzhou Fujian 350002, China )

Considering the characteristics of virtual enterprises task scheduling, timed place Petri-net(TPPN) based approach is proposed to model the task scheduling. On the basis of formal definition and transition rules of the TPPN, product manufacturing types in virtual enterprises are classified, and the TPPN model of each kind of manufacturing is provided, then the methods of resolving critical path with place zero activity floats and solving reasonable scheduling scheme with reachability graph are analyzed. Finally, the simulation of a case indicates that the approach is feasible and effective.

task scheduling; timed palce Petri-net; virtual enterprises

TH 165

A

1003-0158(2011)01-0148-06

2009-04-01

国家自然科学基金资助项目（50875049）；福建省重大科技资助项目（2007H2011）；福建省教育厅科技资助项目（JA09031）

黄 彬（1971-），男，江西南昌人，副教授，博士研究生，主要研究方向为敏捷制造、制造系统工程。