基于Petri网与GA算法的FMS调度优化

计　　算　　机　　学　　报

CHINESEJOURNALOFCOMPUTERS

Vol.28No.2

Feb.2005

　基于Petri网与GA算法的FMS调度优化

郝　东　蒋昌俊　林　琳

(同济大学计算机科学与工程系　上海　200092)

(国家高性能计算机工程技术研究中心同济分中心　上海　200092)

摘　要　提出了一种应用遗传算法解决柔性制造系统调度优化问题的新方法.首先用Petri网对柔性制造系统进行建模,然后应用遗传算法对该模型进行调度并获取近似最优解.在该算法中,用Petri网模型的激发序列作为染色体,采用期望值方法作为选择算子,总加工时间作为适应度函数,两点交叉法作为交叉算子,交叉点选择能到达相同标记的转移.对于变异算子,首先从染色体上随机选择一点作为变异点,然后从这点开始应用变异算法,该变异算法类似于Petri网的可达树算法.由于算法中的选择、交叉和变异算子都是对Petri网模型中的元素进行操作,与问题空间中的元素无关,因此,与其它调度算法相比,它有较高的通用性.既可以处理典型的Job2Shop问题,也可以处理小批量、多品种的FMS(FlexibleManufacturingSystem)调度问题.文中通过实验验证了算法的有效性.关键词　生产调度;Petri网;遗传算法;柔性制造系统中图法分类号TP393

PetriNetBasedModelingandGABasedSchedulingforFMS

HAODong　JIANGChang2Jun　LINLin

(DepartmentofComputerScience&Engineering,TongjiUniversity,Shanghai　200092)

(TongjiBranch,NationalEngineering&TechnologyCenterofHighPerformanceComputer,Shanghai　200092)

Abstract　InthispaperanewwayofapplyingGAalgorithmtooptimizeFMS(FlexibleManu2facturingSystem)schedulingispresented.FirstPetrinetisusedtomodelFMSs.ThenGAalgo2rithmisusedtoschedulethePetrinetmodel,andanearoptimizedresultisgot.InthealgorithmthefiringsequencesofthePetrinetmodelareusedaschromosomes.Theauthorschoosetheex2pectedvaluemodelasselectionoperator.ThefitnessfunctionisthemakespanoftheFMSandPowerScalingisused.Theauthorschoosethetwo2pointcrossovermethodascrossoveroperator.ThecrossoverpointsarechosenatthetransitionsiftheycanreachthesamemarkinginthePetrinetmodel.Astothemutationoperatorauthorschooseamutationpointrandomlyfromthechro2mosomeandapplyamutationalgorithmwhichissimilartothePetrinetreachabilitytreealgo2rithm.Becausetheselectionoperator,thecrossoveroperatorandthemutationoperatordon’tdealwiththeelementsintheproblemspace,withtheelementsofPetrinetmodel,theaboveal2gorithmcomparedwithotherschedulingalgorithms,canbeusedinawiderrange.Besides,theeffectofthealgorithmisprovedbytheexperimentgiveninthepaper.

Keywords　scheduling;Petrinet;GAalgorithm;flexiblemanufacturingsystem

收稿日期:2004204228;修改稿收到日期:2004210210.本课题得到国家自然科学基金(60125205,90412013)、国家“八六三”高技术研究发展计划项目基金(2004AA014340)、国家“九七三”重点基础研究发展规划项目基金(2003CB316902)、上海高校网络技术E2研究院

(200306)、上海市重大计划项目基金和上海重点计划项目基金资助.郝　东,男,1978年生,硕士研究生,主要从事Petri网理论、FMS调

度优化、网格技术方面的研究.E2mail:donhoffh@163.com.蒋昌俊,男,1962年生,博士,教授,博士生导师,研究方向为并发理论、软件形式化技术、网格计算等.林　琳,女,1980年生,硕士研究生,主要从事Petri网理论、并行计算、网格技术方面的研究.

202计　　算　　机　　学　　报2005年

GA算法对一个WaferProbeCenter进行了建模和

1　引　言

随着时代的发展,传统的单一品种、大批量生产

制造方式已经逐渐不适应市场的要求,多品种、小批量的生产方式得到更广泛的应用.与传统方式相比,多品种、小批量的生产方式由于采用了柔性制造技术,能够及时确定客户需求,并按照订单调整生产计划和流程,进行生产.因此,这种生产方式更加适应市场多变的要求.

在这种多品种、小批量的生产方式中所采用的制造系统就是柔性制造系统(FlexibleManufacturingSystem,FMS).它由数控加工设备和设备间完成加工接续的自动材料传输系统组成,系统并存着异步推进的不同工艺流.并发、共享和加工路径的多样性等特点在提高系统生产力的同时,也为系统管理提出了很多新的挑战.在一定条件的制约下,如何统筹安排系统的制造行为,以获得优化的系统运行效率,这就是所谓的FMS制造调度优化问题.

Petri网是Petri博士于1962年提出的一种系统描述和分析的工具,它适于描述并发、资源共享、加工途径多样性等离散事件动态系统的许多特征,因此非常适用于FMS制造的调度优化[1].同时,作为一种形式化的工具,应用Petri网的相关理论,可以有效地解决系统中的死锁问题.

目前,关于这方面的研究,主要可以分为两大类.一类是基于构造Petri网可达图的启发式搜索算法.例如,Shih和Sekiguchi[2]在利用Petri网仿真FMS功能的过程中,利用局部调度解决冲突,Lee和DiCesare[3]用人工智能的算法给出了一个解决生产调度问题的框架;Sun和Cheng[4]对Lee的方法进行了改进,提出了有限扩展的A*算法;薛雷和郝跃[5]则利用增强确定时间Petri网(下文简称增强DTPN)和类A*算法进行了多目标优化,并在模型上弥补了前人在模型中没有考虑的柔性制造系统中存在的一些重要因素,如设备故障、定期维护、设备优先级和操作优先级等.这些方法在优化上起到了一定的作用,但是,由于启发函数往往和具体应用有关,而Petri网又存在众所周知的状态爆炸问题,因此,这些方法往往最终变成一种类似的广度查找算法,执行效率不高.

另一类主要是依靠遗传算法(简称GA算法)来实现调度优化.在这方面,Muth和Thompson[6]最早使用遗传算法对一个10×10的Job2Shop问题进行了优化;Lin和Fu[7]等使用着色时间Petri网和

调度;Chung和Fu[8]等使用TPPN和基因算法对一个FMS系统进行了建模和调度;Huang[9]等使用QCPN(QueueingColoredPetriNet)和GA对Wafer制造进行了建模和调度;Xu和Wu[10,11]也使用了Petri网和GA对FMS系统进行了建模和调度,并先后提出两个算法.这些方法对于快速有效地优化FMS调度起到了较好的作用.但是,总的来说,这些方法有以下不足:一是没有充分发挥Petri网的作用,如文献[10,11]中Petri网仅被用来检验是否有死锁;二是在染色体的编码上,这些方法与具体问题结合较亲密,这有利于获得较好地优化结果,但是也牺牲了一定的通用性.例如文献[6,10,11]中的算法主要适合解决Job2Shop类型的问题,并不适合解决FMS系统中的调度,因为这类调度存在多加工路径、有时需要考虑对机器的维修或者每个Job要加工多个产品的情况,这时,这些方法就显得通用性不足.此外,Lin和Fu[7]及Huang[9]的算法是对循环加工过程的调度,更适合于对大批量生产的调度.

针对上述不足,本文从以下两方面来解决问题:(1)在文献[5]的基础上,提出了简化的Petri网加工模块,用这些模块建立的FMS模型不仅保证无死锁,而且这些模块对FMS系统具有足够的描述能力;(2)运用GA算法为FMS系统进行调度优化,其中染色体编码使用FMS系统的Petri网模型的激发序列作为染色体,而交叉和变异也只是对Petri网模型中的元素进行操作,没有直接对问题空间中的元素进行操作,因此,只要所要调度的问题可以用Petri网模型描述出来,就可以用这个算法进行调度,提高了算法的通用性.

本文第2节介绍增强时间Petri网(简称DTPN)以及为FMS系统建模的模块;第3节详细介绍本文中遗传算法的编码方法、交叉方法、变异方法等;第4节用本文算法对一个IC制造例子进行实验;第5节进行总结.

2　增强DTPN模型与模块

2.1　增强DTPN[5]的定义

增强DTPN,即增强确定时间Petri网,是Petri网的子类,本文用它来对FMS建模.定义如下:

增强DTPN是一个七元组N=(P,T,I,O,H,Λ,m0),其中,

P={P1,P2,…,Pm}是有限的Place集合,m>0;T={T1,T2,…,Tn}是有限的Transition集

2期郝　东等:基于Petri网与GA算法的FMS调度优化203

合,n>0,满足P∪T≠󰂡且P∩T=󰂡;

I:P×T→N是Place集合P到Transition集合T的输入函数;

O:T×P→N是Transition集合T到Place集合P的输出函数;

H:P×T→N是Place集合P到Transition集合T的测试函数;

Λ:T→R+∪{0}是给Transition集合T的每个元素定义一个操作时间的时间函数;

+

m0:P→N∪{0}是从Place集合P到正整数集合的初始标记函数.

运行规则:t∈T在标记m被使能,当且仅当　(Πp∈P,m(p)ΕI(p,t))∧(Πp∈P,H(p,t)≠0,m(p)(p)=m(p)-I(p,t)+O(p,t).Πp∈P,m′

2.2　建模模块2.2.1　死锁情况的出现与解决

在FMS系统中,死锁情况的出现主要表现在资源分配的冲突上.例如,Job1和Job2的加工都需要机器1和机器2共同完成,Job1已经获得了机器1的使用权,等待机器2的使用权,同时,Job2获得了机器2的使用权,等待机器1的使用权,在这种情况下,如果两个Job都不是可以抢占的,就会发生死锁.如下图1的两个Job的加工过程,t2需要m2中的令牌才能激发,t6需要m1中的令牌才能激发,两个Job都只获得了完成加工所需要的一部分资源,另一部分被对方获得,形成死锁.

解决还可以通过添加表示缓冲区的Place来加以解决.例如上面两个Job的例子,添加缓冲区后的Petri网如图2所示,这时已经不会再发生如上所述的死锁了.文献[10]中在GA算法中通过嵌入查找虹吸结构的算法来解决死锁问题,文献[11]中在GA算法中通过嵌入动态添加缓冲区的算法来解决死锁问题,而本文通过下面小节所介绍的建模模块,使得所构造出的Petri网模型不含有可能会导致死锁的结构.因此,在算法中不必考虑死锁这一问题.该方法本质就是添加表示缓冲区的Place.

图2　无死锁的两Job加工过程

2.2.2　建模模块

图1　两Job加工过程

对于Petri网中死锁的解决,已经有许多人做

过研究,如文献[12]中通过计算Petri网中的虹吸结构来解决死锁问题.在FMS系统中对于死锁的

薛雷和郝跃在文献[5]中提出了使用Petri网模块为FMS系统建模的方法和几种加工模块.该方法建立的FMS模型不含有导致死锁的结构.本文在此基础上加以扩展,使用下图3所示5个模块及图4所示的4个简化模块,为FMS系统建模.

R

图3中Place和Transition的含义如下:Pk表示资源Rk;PiI,j表示作业Ji完成第j步操作,在缓冲区中等待下一步处理;POi,j,k表示作业Ji的第j步在资源Rk上进行加工;PMk,cnt表示资源Rk自从上次维修后至今已连续加工了多少个产品;PMk表示正在进行资源Rk的维护操作;tbi,j,k表示作业Ji使用资源Rk开始进行第j步的加工;tei,j,k表示作业Ji结束使用资源Rk的第j步加工;tMbk表示资源Rk的维修工作开始;tMek表示资源Rk的维修工作结束.

若不考虑设备优先级模块,其它模块可以进一步简化为图4,其中Place和Transition的含义与图3类似,这里不再赘述.与图3相比,这些模块精简掉一些Place和Transition,有利于简化FMS系统Petri网模型的结构.

204计　　算　　机　　学　　报2005年图3　建模模块

图4　简化的建模模块

　　使用图3和图4的9个模块,经过简单的拼接,

就可以对生产加工过程进行建模.这些模型即可以刻画Job2Shop问题,也可以对具有多加工路径、要求每个Job加工多个产品的FMS系统进行描述.

3　调度算法

正如前文所述,关于生产调度的算法主要分为两类.遗传算法具有全局搜索能力,目前得到了越来越多的应用,本文也采用遗传算法.文献[6,10]和文献[11]都尝试了用遗传算法来优化生产调度,并取得较好的结果.这些方法在对染色体的编码方面,基本上都是采用把各个Job的操作分配到各个机器上的编码方式,算法与所需解决的问题结合紧密.当问题的类型发生了变化时,例如需要考虑对设备的定期维护,或者需要考虑每个Job加工多个产品,这种编码方式就不再合适,需要改进.而改变编码方式,也就意味着改变算法,所以,这些算法在通用性方面受到.

本文充分利用Petri网模型,在对染色体编码时,不是对问题空间中的元素(如各个Job的操作)编码,而是对Petri网模型空间中的元素编码,提高了算法的通用性.具体的说,就是以Petri网中转移的激发序列作为染色体,每一个Petri网模型的激发序列就代表了一个可行的调度方案.这使得算法与Petri网模型结合紧密,而与所需解决的问题无

关.要解决的问题只需映射为对应的Petri网模型即可.本文第2节中给出的9个模块,对于各种类型的生产调度问题都能进行描述.3.1　染色体编码

对于一个Petri网(本文是其子类DTPN),若存在激发序列σ=t1t2t3…titj…tn-1tn,使得m0[σ>mf,则σ是一条染色体,其中m0是初始标记,mf是结束标记,t1,t2,t3,…,ti,tj,…,tn-1,tn∈T.3.2　适应度函数与定标

根据DTPN,可以计算每一个染色体σ的总时

).由于间,也就是整个加工调度的时间,记为time(σ

遗传算法要求越好的解有越大的适应度,因此取适应度函数为

σ),当time(σ)σ)=f(,

0,其它情况

其中,Cmax是一个合适的输入值.

由于乘幂标[6]的定标方法具有灵活简单、不会产生负适应度的特点,本文采用乘幂标的定标方法.即

(σ)=fK(σ),f′

其中K为一个输入参数,本文取为11005.3.3　选择算子

本文采用期望值方法[6]作为选择算子,即群体中每一个个体在下一代生存的期望数目为

(σf′i)M=・n,

(σf′i)∑

2期郝　东等:基于Petri网与GA算法的FMS调度优化205

其中,n为父代群体的数量.

3.4　交叉算子

交叉算子的操作如下:

(1)将群体中的染色体随机配对,设σ和σ′为配对的两条父染色体;

(2)按照σ和σ′所代表的激发序列对转移逐个激发,生成中间标记;

(3)在σ和σ′中查找具有相同标记的基因座,并将每一对具有相同标记的基因座记录下来;

(4)在查找到的具有相同标记的基因座对中,随机选取两对,将这两对之间的基因片断(即激发序列)进行交换.

图5展示了这一过程:父代染色体σ和σ′中,共有3对基因座对应的标记是相同的,即Ma=M′a,Mb=M′b,Mj=M′j,经随机选择,选择了(ta,t′a)和(tj,t′j)这两对基因座,然后交换这两对基因座之间的基因片断(即激发序列).

2.从染色体σ中随机选择一个基因座,将该基因座所

对应的Marking放入OpenTable;

3.如果OpenTable不空,转步4;否则转步8;

4.从OpenTable中取出一个标识m,放入CloseTable;5.找到标识m下所有使能的Transition;

6.激活每一个使能的Transition,产生m的子标识m′,

计算m′的到达时间,设置父亲标识为m;

7.对m的每个子标识m′,如果m′是结束标识,把m′放

入ResultTable;否则放入ChildTable,转步3;

8.若ChildTable不空,转步9;否则转步10;

9.从ChildTable中,按照标识的时间的大小选取前N(N为自然数,是算法的输入参数之一)个标识,放入Open2

Table,并丢弃其余标识,然后转入步3;

10.从ResultTable中取出时间最小的一个标识,得到

生成该标识的转移和父标识,如此递归得到一个激发序列;

11.将染色体σ的变异基因座之前的激发序列与步10

中得到的激发序列连接,得到新染色体σ′,该染色体即为变异后的染色体.

由于变异算子只是遗传算法迭代过程中的一步,上述变异算子中的N不宜取太大,否则影响遗传算法的效率.本文推荐N=10(在后面的实验中也设置N为10).

4　实　验

本文对一个实际IC生产线的光刻单元进行了调度.该问题可抽象如下:有两种Job,每种Job需加工3个产品,每个Job都有3个阶段,每个阶段有多台机器可以完成这一阶段的任务,如表1.要求优先选用排在前面的机器,例如,Job1的第2阶段,当

图5　染色体交叉过程

M2,M3,M4三台机器都可用时,优先选择M2,次选

择M3,最后选择M4.调度过程中要考虑对机器进行定期维护.对机器的维护时间为5,每个机器每加工两次必须维修一次,加工时间见表2.

表1　光刻单元加工过程

123Job1(lot=3)M1/M2M2/M3/M4M1/M2/M4Job2(lot=3)M1/M3/M4M1/M2/M3

M43.5　变异算子

遗传算法中,导入变异算子的目的在于使遗传算法具有局部随机搜索能力.“当遗传算法通过交叉算子已接近最优解邻域,利用变异算子的这种局部随机

(文献[6]第85页).搜索能力可以加速向最优解收敛”

由于本文采用激发序列作为染色体编码,若随机改变激发序列中的一个转移,极有可能会导致该染色体为不可行解.以前的研究主要有两类方法来解决这一问题:一是随机改变染色体,若生成了不可行解,再进行改正;第二类方法是在进行变异时保证不会产生不可行解.本文的变异算法属于第二类.下面是算法步骤:

1.初始化:OpenTable清空,CloseTable清空,ChildTable

表2　光刻单元加工时间

M1

Job1

M2

M3/

M4/

Job2

第1阶段第2阶段第3阶段第1阶段第2阶段第3阶段

15

/

201525

/

202020

/

25

/

25

/

2030

/

302525

/

30

清空,ResultTable清空,把初始标识m0放入Open2Table;

206计　　算　　机　　学　　报2005年

这个问题是一个典型的小批量、多品种的生产

加工调度问题.系统中存在多加工路径、需考虑设备优先级和设备维护等特点,因此需要把第2节中介绍的设备优先级模块和设备维护模块结合起来使用.图8～图13给出了该问题各个加工阶段的Petri网模型,图中具有相同名称的Place(或Transition)是同一个Place(或Transition),Place和Transition名称的含义可参见第2.2.2小节.用同样的Petri网模型,本文用文献[5]中的算法进行调度,得到了175的优化结果.

由于GA算法具有一定的随机性,本文做了20次实验,实验结果见表3,图6显示了其中一次优化过程.实验环境为曙光3000系统,操作系统为AIX41313,程序用C语言编写.实验中各参数设置为

代沟G=0185,交叉概率Pc=019,变异概率Pm=012,初始群体数量Q=100,迭代次数为GEN=100.

表3　优化结果

优化结果

135

140155产生的次数

1631图6　优化过程

图7　操作在机器上分配的Gantt图

图8　Job1第1阶段加工过程的Petri网模型

　　从表3可以看到,20次实验结果有16次获得了135的优化结果,3次获得140的优化结果,1次获得155的优化结果,全都优于175的优化结

果,平均每次优化耗时2min7s.因此,本文的算法对该问题给出了较好的调度效果,并且执行效率较高.

图7给出了其中一次实验结果在4台机器上分

图9　Job1第2阶段加工过程的Petri网模型

2期郝　东等:基于Petri网与GA算法的FMS调度优化207

图10　Job1第3阶段加工过程的Petri网模型

图12　Job2第2阶段加工过程的Petri网模型

图13　Job2第3阶段加工过程的Petri网模型

5　结　论

本文提出了一种应用遗传算法解决FMS系统

调度优化问题的新方法.以往应用遗传算法主要解决一些Job2Shop类型的调度问题,算法与问题结合紧密,通用性不足,难以用来解决FMS系统的调度.本文的算法由于以FMS系统Petri网模型的激发序列为染色体,算法中的选择、交叉和变异算子都是对Petri网模型中的元素进行操作,与问题空间中的元素无关,因此,只要所调度优化的问题能够用Petri网模型描述出来即可.本文给出的模块化建模方法,使得所建模型能够充分描述各种系统,又能保证无死锁.因此,将本文提出的算法和模块化建模方法相结合,提高了算法的通用性,既可以解决Job2Shop类型的问题,也可以解决FMS系统的调度问题.文中用实验验证了算法的有效性.

今后进一步的研究工作是结合曙光3000和AIX4.3.3的并行能力,研究用Petri网对FMS系

图11　Job2第1阶段加工过程的Petri网模型

配的Gantt图,其中符号含义如下:jobi.j.k表示Jobi的第j个工件的第k步操作;m表示对机器进行维修;

Mi表示第i台机器.对该结果进行瓶颈分析,可以看

出M4是瓶颈,即在4台机器中最后一个完成分配的任务,且不论如何重新组合机器间的调度,已经不可能把机器4的任务完成时间进一步提前,所以该调度即为一个最优调度,即minimalmakespan=135.

208计　　算　　机　　学　　报2005年

统调度优化的并行算法.

参考

1

(陈国良,王煦法等.遗传算法及其应用.北京:人民邮电出版

社,1996)

文献

7LinShun2Yu,FuLi2Chen,ChiangTsung2Che,ShenYi2Shiu2an.ColoredtimedPetri2netandGAbasedapproachtomodel2ingandschedulingforwaferprobecenter.In:Proceedingsofthe2003IEEEInternationalConferenceonRoboticsandAuto2mation,Taipei,2003,1:1434～1439ZhouM.C.,JengM.D..Modeling,analysis,simulation,scheduling,andcontrolofsemiconductormanufacturingsys2tems:APetrinetapproach.IEEETransactionsonSemicon2ductorManufacturing,1998,11(3):333～357

8

ChungYung2Yi,FuLi2Chen,LinMing2Wei.PetrinetbasedmodelingandGAbasedschedulingforaflexiblemanufacturingsystem.In:Proceedingsofthe37thIEEEConferenceonDeci2sionandControl,Tampa,Florida,1998,4:4346～4347

2ShihH.,SekiguchiT..AtimedPetrinetandbeamsearchbasedon2lineFMSschedulingsystemswithroutingflexibility.In:ProceedingsofIEEEInternationalConferenceonRoboticsandAutomation,Sacramento,1991,2548～25539HuangAn2Chih,FuLi2Chen,LinMing2Hung,LinShun2Yu.Modeling,scheduling,andpredictionforwaferfabrication:QueueingcoloredPetri2netandGAbasedapproach.In:Pro2ceedingsofthe2002IEEEInternationalConferenceonRoboticsandAutomation,WashingtonDC,2002,3:3187～3192

3LeeD.Y.,DiCesareF..FMSschedulingusingPetrinetsandheuristicsearch.IEEETransactionsonRoboticsandAutoma2tion,1994,10(2):123～1324SunTien2Hsiang,ChengChao2Weng,FuLi2Chen.APetrinetbasedapproachtomodelingandschedulingandschedulingforanFMSandacasestudy.IEEETransactionsonIndustrialE2lectronics,1994,41(6):593～601

10XuGang,WuZhi2Ming.Deadlock2freeschedulingmethodu2singPetrinetmodelanalysisandGAsearch.In:Proceedingsofthe2002InternationalConferenceonControlApplications,Glasgow,Scotland,2002,2:1153～1158

5XueLei,HaoYue.Petrinetbasedschedulingforintegratedcircuitsmanufacturing.ACTAElectronicaSinca,2001,29(8):10～1067(inChinese)

(薛　雷,郝跃.面向集成电路制造的基于Petri网的生产调度.

11XuGang,WuZhi2Ming.Deadlock2FreeSchedulingStrategyforAutomatedProductionCell.IEEETransactionsonSys2tems,ManandCybernetics,PartA,2004,34(1):113～122

12YuanChong2Yi.ThePrincipleofPetriNet.Beijing:PekingUniversityPress,1999(inChinese)

(袁崇义著.Petri网原理.北京:北京大学出版社,1999)

电子学报,2001,29(8):10～1067)

6

ChenGuo2Liang,WangXu2Faetal..TheTheory&Applica2tionofGeneticAlgorithm.Beijing:People’sPosts&Telecom2municationsPublishingHouse,1996(inChinese)

HAODong,bornin1978,M.S.candidate.HisresearchinterestsincludePetrinettheory,FMSschedulingalgo2rithm,andgridtechnology.

JIANGChang2Jun,bornin1962,Ph.D.,professor,Ph.D.supervisor.Hisresearchinterestsincludeconcurren2cytheory,softwareformalizationtechnology,andgridcom2puting.

LinLin,bornin1980,M.S.candidate.HerresearchinterestsincludePetrinettheory,parallelcomputing,andgridtechnology.

Background

NationalNaturalScienceFoundation(No160125205)isfocusedonthebehavioranalyzingtheoryandmethodofPetrinet.NationalNaturalScienceFoundation(No190412013)concentratesontheGridresourceorganizingandmanagingmodelandtechnique.NationalBasicResearchProgramofChina(973Program)(2003CB316902)makesresearchontheverificationtheoryandserviceintegrationofsemanticGrid.National863Plan(2004AA014340)researchesontheGridtechniqueinTransportationInformationSystem.ShanghaiScience&TechnologyResearchPlanworksonGridarchitec2

tureanditssupportingtechnology.ShanghaiCollegeGridTechniqueE2AcademyworksontheGrid2Qosbasedschedu2lingandchargingmiddleware.

Authors’workexploresPetriNet’smodelingandana2lyzingtheory,combinesthemwiththeGAalgorithmandap2pliesittosolvetheFMSschedulingproblem.

Authors’otherresearchworkincludes:ModelingofICManufacturingSystem,

GridQoSMiddlewareresearch

(mainlyfocusonGridresourcesscheduling).