See discussions, st ats, and author pr ofiles f or this public ation at : https:www .researchgate.ne tpublic ation225170760 [632233]

See discussions, st ats, and author pr ofiles f or this public ation at : https://www .researchgate.ne t/public ation/225170760
Petri Nets and Manufactu ring Systems: An Examples-Driven T our
Chapt er   in  Lecture Not es in Comput er Scienc e · July 2004
DOI: 10.1007/978-3-540-27755-2_21  · Sour ce: DBLP
CITATIONS
38READS
137
4 author s, including:
Some o f the author s of this public ation ar e also w orking on these r elat ed pr ojects:
Create ne w pr oject "Struct ural based appr oaches f or de adlock pr evention in c oncurr ent syst ems" View pr oject
On fluidiz ation, c ontr ollability and c ontr ol of timed c ontinuous P etri ne ts View pr oject
Manuel Silv a
Univ ersity of Z aragoza
281 PUBLICA TIONS    6,375 CITATIONS    
SEE PROFILE
All c ontent f ollo wing this p age was uplo aded b y Manuel Silv a on 23 Januar y 2016.
The user has r equest ed enhanc ement of the do wnlo aded file.

PetriNetsandManufacturing Systems:
AnExamples-Driv enTour?
L.Recalde, M.Silva,J.Ezpeleta, andE.Teruel
Dep.Inform aticaeIngenier adeSistemas, I3A
Universidad deZaragoza, MaradeLuna 1,E-50018 Zaragoza, Spain
flrecalde,silva,ezpeleta,eteruel [anonimizat]
Abstract. There exists ample literature onPetrinetsanditspoten-
tialinthemodelling, analysis, synthesis andimplemen tation ofsystems
inthemanufacturing applications domain (seeforexample [54,15,18];
besides, in[66]animportantbibliograph yispresen ted).Thispaperpro-
vides anexamples-driv enperspective.Nevertheless, notonlycomplete
examples from theapplication domain areconsidered. Manufacturing
systems arefrequen tlylarge systems, andconceptual complexit yoften
appearsbecause ofsome particular \local"constructions.
Theexamples considered inthisselected tourtrytointroduceinapro-
gressiv ewaysome applied concepts andtechniques. Thestarting point
isanassem blycell,forwhichmodelsconcerning severalphases ofthe
design life-cycle arepresen ted.Afterw ards, some pullcontrolandkan-
banmanagemen tstrategies aremodelled. Then, twocoloured modelsof
production linesarepresen ted.After that,amanufacturing system with
twocellsismodelled, andthedicult yofthepractical analysis isshown.
Forverypopulated manufacturing systems orsystems withhighcadence,
relaxation ofdiscrete eventmodelsleads tohybrid andcontinuousap-
proximations, anexample ofwhichwillbeshortly introduced.
1Motiv ation andobjectives
PetriNets(PNs) constitute awellknownparadigm forthedesign andoperation
ofmanysystems allowingadiscrete eventview[53].Thepurposeofthisworkis
topresen t,inatutorial style,someexamples inwhichmanufacturing systems are
modelled andanalysed. SeveralbooksaboutPNsandthedesign andoperation
ofmanufacturing systems havebeenpublished attheendofthelastcentury[17,
15,65,56,44,66].Inthesequel, thereader isassumed tobeintroduced tothe
mainconcepts inPetriNets[50,42].
Basically acasestudy drivenperspectiveisprovided inthiswork.Neverthe-
less,notonlyfullexamples fromtheapplication domain areconsidered. Man-
ufacturing systems arefrequen tlylargesystems, andconceptual complexit yap-
pearsbecause ofsomeparticular constructions thatappearinpartofthesystem.
?Partially supported byprojectsFEDER andCICYT TIC2001-1819, andDPI2003-
06376
1

Theexamples considered inthisselected tourtrytoprogressiv elypresen tsome
applied concepts andtechniques.
Thestarting point(Sect. 2)isamanufacturing cellinwhichsome convey-
orsmoveparts that, processed intotwodieren tmachines (M1andM2),are
assem bledandevacuated. Theinternal movementsoftheparts inthecellare
executed byanindustrial robot.Moreo ver,duetoarelativ elyhighrateoffail-
uresofamachine(M1),abuer allowsapartial decoupling withrespectto
theassem blymachine(hence, alsowithrespecttoM2).Thisstore (orbuer)
actslikecondensers inRCcircuits: ltering highfrequency perturbations (i.e.,
attenuating theeect offrequen tshort failures thatusually leadtomanysmall
unavailabilit yperiods).Fromanabstract perspective,thisintroductory exam-
pleshowssomeinteresting interleavingamong cooperation (here, theassem blyof
twodieren tkinds ofparts) andcompetition (fortheshared resource: therobot)
relationships. Ingeneral terms, theintricate interleavingofthese twokinds of
relationships leadstothekerneloftheconceptual complexit ytomaster thebe-
haviour ofdiscrete eventsystems (DES). Thepresen tation ofthisintroductory
example isfocused ontheadvantages ofusing dieren tmodelsofthesame PN
modelling paradigm inorder todealwiththedieren tphases ofthedesign and
operation thatappearduring thelifecycleoftheprocess.
Ingeneral terms, thecontrolofmanufacturing systems often usessome pre-
established strategies. Among them thepushstrategy (from theinput tothe
output: from therawparts tothenished products), pull(from theoutput
backwardstotheinput: fromthedemand totheinput ofrawparts) andkan-
ban,thatmayrepresen tmanydieren tkinds oftradeos betweentheabove
mentioned basic strategies, arespecially relevant.ThepurposeofSect. 3isto
showthatthiskindofcontrolmechanisms (ormanagemen tstrategies) canbe
appropriately modelled bymeans ofPNs(see,forexample, [11]). Analysis and
optimisation oftheobtained modelscanbedone, butthistopicisnotconsidered
indetail inthissection, sincethemainpurposeistoshowthepractical modelling
powerofthePNformalisms. Thispaperismainly devotedtoaspectsrelated to
modelling, analysis andcontroldesign, andnotonother topics, likesimulation
orimplemen tation issues, thatalthough interesting anduseful arenotdeveloped
here.However,simulation willbeusedinthisparticular section toillustrate the
comparison ofdieren tcontroltechniques.
Inmanymanufacturing systems asignican tpartoftheapparen tcomplexit y
mayderivefromtheexistence ofseveralsubsystems havingidentical(similar)
behaviours, orfrommanyparts havingsimilar processing plans. Under these
conditions (i.e.,havingsignican tsymmetries among components),theuseof
highlevelPNsmaybeofinterest. Forthispurposetwodieren texamples are
presen ted.Therstone(Sect. 4)concerns aFrenchmanufacturing lineforcar
assem bly.Thebasic modelisconstructed inaverysystematic way,bymerging
acoloured PNmodelofthestations where manufacturing operations areper-
formed andacoloured PNmodelforthetransp ortation system. Theproblem
withthisbasic modelisthatdeadlo cksmayappear.Aquite simple solution is
presen ted,beingdirectly implemen table inPNterms, justbyadding aplace
2

(i.e.,aconstrain t)appropriately marked.Astepfurther isdone through the
presen tation ofaclosed linecorresp onding toanovensproduction factory sited
inZaragoza (Sect. 5).
Inorder toapproac hthelimits oftheactual knowledge inthetheory andap-
plication ofPNstomanufacturing examples, twoadditional casesareintroduced
inSect.6.Intherstone(Sect. 6.1),amodelofaFlexible Manufacturing System
(FMS) (held intheDepartmen tofComputer Science andSystems Engineering
oftheUniversityofZaragoza) isestablished [25].Evenifmodelling canbedone
inthiscaseina\straigh tforward"way,analysis \requires", intheactual state
oftheart,somemanipulations allowingthecomputation ofsequen tialised views
forthedieren tprocessplans.Inother words, itisnotadirect application of
theory thatbrings some solutions, butanindirect-pragmatically orientedengi-
neering approac h.Going inthesamedirection, inSect.6.2modelling withobject
netsisdone: thisleads toapowerfulmodelling approac h[62].Unfortunately ,it
usually happensthatthehigher theabstraction leveltheformalism allows,the
more complicated itsanalysis becomes. However,itisalwayspossible toapply
simulation techniques, whichcangiveinsigh tofsome system behaviours.
Discrete event\views" maybeveryconvenientinmanycasesformanufactur-
ingsystems. Nevertheless, insome other cases, either because ofcomputational
complexit yproblems (duetostateexplosion) orbecause thesystem presen tsa
\regular" highcadence behaviour orishighly populated,
uidication orcon-
tinuisation maybeofinterest [3,51,52].Ahybrid (partially continuised) model
ofthiscategory ispresen tedinSect. 7.Forsystems inwhichsome parts are
\naturally perceiv edascontinuous", adieren tPNinterpretation leads tohy-
bridmodelling (PrTr-DAE).Inthepresen tstateofknowledge, thislastapproac h
usessimulation asthemainanalysis technique (besides theapplication ofstan-
dardanalysis techniques forthestudy oftheunderlying discrete model).Hybrid
modelsanalysis techniques should muchimpro veinthefuture. Finally ,some
concluding remarks closethiswork.
2Lifecycleandanintroductory example: Anassem bly
manufacturing cell
Thisintroductory example deals withasystem inwhichtheprocessplanis
quite easy: Parts\A"and\B"should beproduced (atmachinesM1andM2,
respectively)andlaterassem bled(arendez-vous )inmachineM3toobtain a
nalproductthatleavesthemanufacturing cell.Inthistrivial cooperativ esys-
tem,twoadditional elemen tsareintroduced. First, relativ elyimportantfailures
andrepairs aretakenintoaccoun tforM1.With theideainmind ofpartially
decoupling these acciden tswithrespecttotheoperation ofdownstream ma-
chines (hereM3),abuer (inventoryplace, deposit)isintroduced. IfM1fails,
thedownstream machine,M3,maycontinueworking forawhile consuming the
parts already inthebuer. Iftheupstream machineM1isrepaired beforethe
buer isemptied, thefailure willnotaect thedownstream line(hereM3,only).
SinceM3isanassem blymachine,itsstopping condition willpropagate tothe
3

upstream line(hereM2).Thebuer isapassiv eelemen t.Atthispoint,thefull
system onlyexhibits cooperativ eactivities. Atypical competition relationship is
introduced bymeans ofthemovementofparts inside thesystem. Inthiscasea
robotfeedsM1andM2(from theconveyorbelt),feeds thebuer (from M1),
andmovespartsA(from thebuer) andB(from M2)toM3.Therefore, all
theseactivities areinmutual exclusion (mutex ).Thusthisintroductory example
(Fig.1,thatwillbeexplained more indetail inSect.2.1)hascooperation and
competition relationships. Ifthecompetition fortheuseoftherobotisignored,
thecooperativ eparts canbedescrib edbyafree-choic enetsystem [57].The
addition oftherobot-idle place transforms thenetintoasimple orasymmetric
choice.
2.1Basic autonomous model:dealing withbasic relationships at
thenetlevel
ThenetinFig.1modelsboththeplant andtheworkplan,fromacoordination
viewp oint.Intheinitial state, allthemachines andtherobotareidle,andthe
buer isempty.Theonlyenabled transitions arethose thatrepresen tthestartof
theloading operation ofeither M1orM2,butonlyoneofthem canoccur(i.e.,
there isacon
ict situation). Theautonomous modelleavesundetermined which
onewilloccur,itonlystates thatthese arethepossibilities. Assume M1istobe
loaded, whatisrepresen tedbytheoccurrence oftransition t1.Then themarking
changes: onetokenisremovedfromeachinput placeofthetransition (Ridleand
M1idle)andonetokenisputintotheoutput place (M1loading).Notice that
tokenswererequired fromtwoinput places, meaning thattheloading operation
requires thatboththemachineandtherobotareready: itisasynchr onisation
ofboth.Nowtheonlyenabled transition istheonerepresen tingtheendofthe
loading operation, buttheautonomous modelleavesundetermined when will
thishappen,itonlystates thatitcanonlyhappenwhenev erloading isincourse
(whichallowstorepresen tsequencing ).Atthering, thetokenisremovedfrom
M1loading andtokensareputinM1working andRidle.Inthisnewmarking,
bothoutput transitions ofM1working areenabled incon
ict (itmayeither
complete theworkorfail),andalsothestartoftheloading ofM2isenabled.
Thislatter transition andatransition fromM1canoccursimultaneously ,or
inanyorder (their enabling isindependen t),what allowstofaithfully model
concurr ency.Notice thecorresp ondence ofsubnets andsubsystems (M1,M2,
M3,B1,andR),andthenatural represen tation oftheirmutual interactions. (It
goeswithout sayingthatoperation places could berened toshowthedetailed
sequence ofoperations ineachmachine,etc.)
Wehavedepicted asbarsthose transitions thatrepresen tcontrolevents ,
while transitions depicted asboxesrepresen ttheendofanoperation,orthe
occurrenceofafailure.Atthepresen tstage ofautonomous systems, these draw-
ingconventions, andalsothevarious labels,areliterature: thedynamics ofthe
modelisnotaected bythese details, whichareintended tomakeclearer the
\physical" meaning ofthemodel.
4

M3M2 M1
B1R
Nloadingt1
down
working
block ed
unloading
tbidle
slots
loading "A"
waiting "B" waiting "A"loading "B"
workingblock ed
t22workingloadingt21
R
idleM1
M2
B1ready
"A" parts
M3idle
free "A" free "B"
Fig.1.Anautonomous place/transition system thatformally describ esthelogicbe-
haviour ofamanufacturing cell.
Thisautonomous modelcanbeusedfordocumen tation/understanding pur-
poses,andalsotoformally analyse thenon-deterministic possible behaviours.
Classical PNanalysis techniques allowtoecien tlydecide thatthissystem
5

modelisbounded (i.e.,nite state space), live(i.e.,noaction canbecome
unattainable), andreversible (i.e.,fromanystate thesystem canevolvetoits
initial state).
Classical (andbasic) reduction rules[49]allowtotransform themodelinto
amarkedgraph:
1.Everypathstartloading !loading !endloading isamacrotransition .
Therefore itcanbereduced toasingle loadtransition, preserving the(pro-
jected) language, hence liveness, boundedness, reversibilit y,etc.
2.After theprevious step,placeRidleself-lo opsaround thefourloadtransi-
tions, andcanberemovedpreserving thelanguage (i.e.,itwasanimplicit
place).
3.Theplaces working anddown inM1andtheirconnecting transitions form
amacroplace.
Theresulting markedgraph isstrongly connected. Therefore, itisstructurally
bounded (i.e.,itisbounded foranyinitial marking, notjustfortheonethat
isshownhere), anditdoesnotcontainunmark edcircuits, soitisliveand
reversible.
2.2Theperformance evaluation model:stochastic T-timed
interpretation andanalysis
Ifthepurposeofthemodelistoevaluate theperformance ofthemanufacturing
cell,ortoinvestigate dieren tscheduling policies, thentiming information (e.g.,
duration ofoperations, mean timebetweenfailures, etc.)canbeincorp orated to
themodel,forinstance specifying thedelayinthering oftransitions. Diverse
timing specications arepossible (e.g., stochastic, deterministic, timeintervals,
etc.), eachonebestsuited foraparticular purposeordegree ofdetail required.
InFig.2thering delaysarespecied bytheirmean times.
Inapreliminary design stage, where theissueismachineselection anddimen-
sioning ofthesystem, astochastic timing specication, suchasthatofgeneralised
stochastic PNs[1],isbestsuited. Intheexample weassume thatthedistribu-
tionoftimedelayscorresp onding tooperations andmovementsisphase-typ e,
namely Erlang-3 ,while failures andrepairs followexponential distributions. All
other transitions areimmediate,theyreassoonastheyareenabled (sothey
areprioritary w.r.t. timed transitions). Con
icts betweentimed transitions are
solvedbyracepolicy,while con
icts betweenimmediate onesaresolvedina
probabilistic fashion).
ItwasseeninSect.2.1thatthissystem isreversible. Therefore, thereach-
abilitygraph isstrongly connected, andthisallowstodeduce ergodicityofthe
stochastic processandirreducibilit yoftheunderlying Markovchain.
Markovianperformance analysis canbeusedtoassist inthedimensioning
ofB1,ortoanalyse itsimpact. With givenfailure andrepair rates forM1,
throughput isplotted versus buer sizeinFig.3.
Economic considerations (interms ofthroughput, required investmen t,and
workinprogress) wouldallowtooptimise thebuer size.Theplots inFig.4
6

NTiming:
Operation: 6 t.u.
Robot movement: 1.6 t.u.
M1®B1 transfer: 0.6 t.u.
Synchronization: 0 t.u.
Failure: exp, mean 1/ lfail
Repair: exp, mean 0.15/ lfail
Fig.2.Atimed place/transition system thatallowsperformance evaluation andopti-
misation ofamanufacturing cell.
showhowtheeect ofthebuer variesdepending onthenature ofthefailures.
7

Buffer cap acity (N)Throughput
Fig.3.Performance evaluation ofthecellinFig.1withrespecttobuer capacit y.
Throughput
Failure rate ( )lfail
Fig.4.Performance evaluation ofthecellinFig.1withrespecttofailure rate.
Keeping thefailure/repair ratio constan t(i.e.,the%ofunavailabilit yofthe
machineduetoafailure isconstan t),dieren tsituations canbeobserv ed:
{Veryunfrequen tfailures withverylongrepair times (leftsideoftheplot).
Thethroughput isreduced, andisinsensible tothebuer size,because the
repair timeexceeds largely thetimetoemptythebuer.
{Ontheother extreme, inthecaseofveryfrequen tslightfailures, arelativ ely
small buer isabletolteroutthehighfrequency perturbations represen ted
bythefailures, andthethroughput isequal tothethroughput inthecaseof
nofailures.
{When theorder ofmagnitude ofrepair times aresimilar tothetimere-
quired toemptythebuer, itssizeismostcritical inorder toincrease the
throughput.
Notice thatforthecaseN=0themodelinFig.1should bechanged,
removingB1.That is,the\unloading"operation should bemerged withthe
\loadingA "andplaceslotsremovedsinceitbecomes implicit. Then, M1becomes
essentiallyidenticaltoM2,except forthepresence offailures. Itresults inamore
tightcoupling ofthemachines thatleads toasignican tlylowerthroughput.
8

2.3Ontheoptimal scheduling: Performance control
Assume that, aftertheoptimisation ofthedesign thatinvolvedperformance
evaluation, thecapacit yofthebuer isxedtotwo.Although theplantparam-
etersarexed, theactual performance ofthesystem mayvarydepending on
howitiscontrolled. Thescheduler isincharge ofcontrolling theevolution by
enabling/disabling thetransitions thatinitiate robotloadoperations (i.e.,these
arethecontrollabletransitions here).
M1
M2
M3workingworkingworkingunloading
loading "A"
loading "B"loadingloading
Cycle: 9.2 t.u.Cycle: 10.8 t.u. (a)
(b)Ready "A" parts in B1
012
Ready "A" parts in B1
012
Fig.5.Eect ofdieren tscheduling policies inthemanufacturing cellofFig.1.
Fig.5showstheGanttcharts oftwopossible scheduling policies assum-
ingdeterministic timing anddisregarding failures. InFig.5(a)operations are
scheduled assoonaspossible, solving eventualcon
icts intheallocation ofthe
robotbyxedpriorities (M2isprioritary overM1).Aperiodicregime isquickly
reached,inwhich:
{Thecycletimeis10:8(i.e.,throughput without failuresis0:0926).
{Thebuer contains atmost onepart, soparts arenotaccum ulated tobe
usedintheeventofafailure.
TheGanttchartinFig.5(b)showsanevolution inwhichthescheduler
preventsinterrupting M1untilitgetsblocked,andpreventsinterrupting M2
andM3fromthenon.Thispolicyllsupthebuer tobeprepared foreventual
failures andachievesacycle timeof9:2(i.e.,throughput 0:1087) innormal
operation, thusthebuer allowstoincrease productivit yinmorethan11%.Let
uscheckthatthispolicycanbeprovedtobeoptimal.
Asalready mentioned, letusconsider thesystem without failures (i.e.,remov-
ingthefailure-repair loop).Onewayofreasoning toobtain anoptimal schedule
9

forthissystem isasfollows:theskeleton ofthesystem isclearly astrongly con-
nected markedgraph provided withamonitor place (idlestatefortherobot).
Thustheunique T-semi
o wisx=1(i.e.,avector of1s).Thismeans thatall
thetransitions, inparticular thefourimmediate inwhichtherobotstarts to
work,should beredinthesame proportion inany\long enough" sequence.
Evenmore, thesteady stateshould bedened byrepeating sequences inwhich
t1;tb;t21andt22(i.e.,allthetransitions beforethe\loading"places) appear
once. Since those transitions aretheonlyonesthatmaybeincon
ict, the
scheduling problem reduces tochoosing therelativ eorder inwhichtheyshould
bered. Giventherepetitivebehaviour ofthesteady state, inprinciple any
transition canbetakenastherst,thusthere existatmost3!=6possibilities
toexplore. Assume t22isredrst.Inthiscasenothing opposestotaket21
asthesecond onetore,because there isamarkedplace (M2idle)connecting
theendoftherstloading operation withthestartofthesecond one(inother
words,bychoosing t21asthesecond onenoconstrain tisadded). Therefore, the
question nowistochoosebetweent1andtb.Before going tothatquestion, let
usobserv ethatring anappropriate transien tsequence thebuer canbelled,
atleastpartially .Indoing that, thering oft1andtbare\decoupled" bya
nite sequence, i.e.,bothcanberedinanyorder, while keeping thegoalof
computing anoptimal schedule. If,aftert21,transition t1isred, thecycleof
useoftheshared resource (therobot)isnished byringtb(andlatert22for
anewcycle).
Ageneral upperbound ofthethroughput (lowerforthecycle time) ofthe
original system canbecomputed bymeans ofalinear programming problem [9].
Forthisparticular case,thelowerbound forthecycle timeis9.2timeunits.
Looking atFig.5(b)itisclearthatthislowerbound canbereachedwiththe
previous ordering. However,analternativ eprocedure canbeusedtoproveit.
Introducing places fp2;p3;p4gtoputanorder intheuseoftherobot:t21-
p2-t1,t1-p3-tb,tb-p4-t22(observ ethatp1,fort22-p1-t21,isequal toM2idle,
andsoitisalready presen tandmarked),theplace represen tingtheidlestateof
therobotbecomes concurren tlyimplicit [55],thusitcanberemovedforanytime
interpretation, andamarkedgraph isfound (seeFig.6).Under deterministic
timing theexact cycle timeforanymarkedgraph canbecomputed bymeans
ofthesame linear programming problem mentioned above[8].Theobtained
valueforthiscaseisonceagain 9.2,thusunder deterministic timing andno
failures, thesetofadded constrain ts,places fp2;p3;p4g,constitute anoptimal
scheduler. Thereason isthatadding thatconstrain ts(places p2;p3andp4)the
lowerboundforthecycletimeisnowknowntobereachable.
2.4Thecontroller: Themarking diagram interpretation and
fault-toleran timplemen tation
Controlling anexisting manufacturing system (MS) means constraining itsevo-
lution inorder toguaran teethedesired logicbehaviour or/and tooptimise its
performances atoperation. Iftheplanttobecontrolled ismodelled asaPN,the
10

N-1loadingt1
working
block ed
unloading
tbidle
slots
loading "A"
waiting "B" waiting "A"loading "B"
workingblock ed
t22workingloadingt21M1
M2
B1ready
"A" parts
M3idle
free "A" free "B"p2
p3
p4
Fig.6.Implemen tation ofascheduler thatleads totheminim umcycletime.
controldecides thering ornotofenabled transitions. Usually ,noteverytran-
sition canbedisabled (e.g., afailure, thecompletion ofanoperation, etc.), so
transitions canbeclassied ascontrollableoruncontrollable.Controllable points
11

arethose atwhichthedecision maker(e.g.,ascheduler) in
uences thebehaviour
ofthesystem.
Typically ,concerning thelogicbehaviour, itisimportanttoavoidundesirable
orforbidden states, suchasdeadlo cks,ortoguaran teecertain mutual exclusions,
while performance controlaimstomaximise throughput oramore general cost
function (e.g.,involving alsoworkinprogress, machineutilisations, etc.), byde-
termining thering epochfortransitions (scheduling). PNswithanappropriate
timed interpretation areverywellsuited tothemodelling ofscheduling problems
inparallel anddistributed systems. PNsallowtomodelwithin asingle formalism
thefunctional ,temporal,andresourceconstrain ts.These determine theenabled
transitions, andthenthescheduling problem isreducing theindeterminism by
deciding when torewhich transitions among theenabled ones. Inscheduling
theory [12]itisconventionally assumed thattasks aretobeexecuted onlyonce.
Periodicorcyclic schedules [34]areseldom treated bythetheory despite they
aboundinpractice. PNscheduling techniques allowtofacethese problems. The
sameasfortheanalysis, enumerativ e,net-driv en,andnet-based approac hescan
befound intheliterature. Thecomputational complexit yofscheduling problems
leadsinpractice tosub-optimal solutions obtained using heuristics, articial in-
telligence techniques, etc.
Usually ,thecontrolreceiv esinputs fromtheplant,besides ofemitting signals
toit,soitoperates inclosed loop(theplantandthecontrolarecomposedin
parallel, indiscrete eventsystems terminology). ThesameasPNcanbeusedto
modelandanalyse anMS,itscontrolcanoften berepresen tedwithin thePN
formalism, perhaps incorp orating anappropriate interpretation.
Coming backtothemanufacturing example, ifthemodelismeantasaspec-
ication foralogiccontroller, thering oftransitions mustberelated tothe
corresp onding external eventsorinputs, andtheoutputs thatmustbeemitted
havetobespecied. Theinputs, whichcondition theevolution ofthecontroller,
maycome fromplantsensors (e.g.,whenRnishes loading M2itemits asignal
loadedM2)orfromother levelsinthecontrolhierarc hy(e.g.,when thescheduler
decides |inviewofthestateofthesystem andtheproduction requiremen ts|
thatM1should beloaded, itsendsschedM1).Theoutputs maycommand the
actuators (e.g.,STARTM3initiates theassem blysequence inM3)orsendinfor-
mation toother levelsinthecontrolhierarc hy(e.g.,REPAIR! raises analarm to
calltheattentionofmaintenance sta,oraninterrupt thatactivatesautomatic
recovery;B1CONT(m) updates thenumberofready \A"parts intheproduction
database, etc.). ThePNmodelinFig.7captures thisinformation. Followingap-
propriate conventionsinthespecication (e.g., those imposedinthedenition
ofGrafcet [15]), amodelsimilar tothisonecould beuseddirectly asalogic
controller program.
Once asuitable PNmodelforacontroller hasbeenobtained ithastobe
implemente d.Basically animplemen tation isaphysical device whichemulates
thebehaviour expressed bythemodel.Oneadvantageofusing PNsasaspeci-
cation formalism istheirindependence w.r.t. theprecise technology (pneumatic,
electronic, etc.)andtechniques (hardwired, microprogrammed, etc.)ofthenal
12

loaded_M1
START_M1
Nsched_M1
LOAD_M1
sched_M2
LOAD_M2
TRANSFER
START_M3loaded_M2
START_M2
done_M3loaded_M3A loaded_M3Btransferred done_M2done_M1failrepaired
REPAIR!Signals:
inputs
(from sensors, scheduler, etc.)
OUTPUTS
(TO ACTUATORS, MONITORING, ETC.)
R_OFFM1_ON
M2_ON
M3_ONB1_CONT(m)
sched_M3A
LOAD_M3Asched_M3B
LOAD_M3B
Fig.7.Amarking diagram thatspecies thebehaviour ofthelogiccontroller ofa
manufacturing cell.
implemen tation. Presen tly,inMScontrol,programmed implemen tations arethe
mostusual, running onawiderange ofcomputer systems (e.g.,industrial PC's,
programmable logiccontrollers, etc.).
13

The(programmed) implemen tation isaected bytheselected PNformalism
(loworhighlevel,dieren tinterpretations ofthering rule), thealgorithmic ap-
proach(interpreted, where thePNmodelisadatastructure, orcompiled, where
aprogram isobtained fromthegivenPN;centralised orparallel/distributed
schemas), andthecomputer architecture(high orlowlevelprogramming lan-
guage; single ormultiprocessor).
Forthecaseoflocalcontrollers specied bylowlevelPNswithinput and
output signals (likethatshowninFig.7),ausual choice areinterpreted im-
plemen tations (\tokenplayers") [61,48].Thebasic schema isacyclic program
thatreads theinputs, computes theevolution ofthemarking, andgenerates the
outputs onceandagain. Amajorissueistheecien tcomputation ofenabled
transitions. Anexample ofanecien ttechnique forthispurposearerepresenting
places(see,forinstance, [13]).Theideaistoappropriately select oneinput place
pertransition (itsrepresenting place).Itisalwayspossible (perhaps aftersome
nettransformations) toclassify places aseither represen tingorsynchr onisation
places,where eachoftheformer istherepresen tingplace ofallitsoutput transi-
tions. Themarkedrepresen tingplaces arekeptinalist(weassume safeness for
simplicit y),thatisupdated ateachtransition ring. Ineachcycle, onlytheout-
puttransitions ofmarkedrepresen tingplaces aretested forenabledness, eventu-
allycheckingthemarking ofsomesynchronisation places. Apossible selection of
represen tingplaces forthenetinFig.7areallbutRidle,slots,ready\A"parts,
waiting \A",andfree\B"(thus,these wouldbethesynchronisation places).
Theinheren tparallelism captured byaPNmodelissomeho wdismissed in
centralised implemen tations. Diverseparallel anddistributed implemen tations
havebeenproposed(see,forinstance, [13]). Thestructure theory ofPNsallows
toidentifycertain componentsinagivennetthatareuseful fordistributing or
parallelising theimplemen tation. Particularly ,liveandsafestatemachinecom-
ponentsleadtocyclic sequen tialprocesses thatcanbedirectly implemen ted,for
instance, asAdatasks. Insuchcase,other places canberepresen tedasglobal
variables, semaphores, etc.Coming backtotheexample, weeasily identifyM1
andM2assequen tialtasks, M3canbedecomp osedintotwosynchronised se-
quentialtasks, slotsandready\A"partsaresemaphores, andRidleisamutual
exclusion semaphore.
Intheimplemen tation ofhigher controllevels,some convergence hasap-
peared betweentheelds ofPNsandarticial intelligence (see,forinstance,
[40],[60]). Inthissense, transitions playtheroleofrules while theworking
memory canbesplitintoseveralnodescorresp onding totherespectiveinput
places. With respecttoclassical PNsimplemen tations, thesearchforenabled
transitions iscarried outbythematching phase intherulesystem, whichcan
takeadvantagefromthepartition intolocalworking memories. Fortheselec-
tionphase transitions canbegroup edintocon
ict setsbyinspecting thenet
structure, andeachonecanbeprovided withaparticular resolution strategy .
Animportantissuewhen designing acontrolsystem isthatofsafety .Formal
modelling andanalysis toolsareneeded toengineer safecomputer-con trolled
systems. Forthistaskitisnecessary toconsider boththecontrolsystem and
14

itsenvironmen t,forwhichPNsareasuitable formalism [37].When faults can
happenthecontroller should beabletodetect themandevenreactappropriately
degrading system's performance aslittleaspossible.
Letusbrie
y concen tratehereonthedetection andrecoveryoffaults inthe
controller itself. Severaltechniques havebeenproposedtoproducesafeand/or
fault-toler antPNsbased controllers. Weillustrate nextoneofthese techniques
whicharesupported byPNstheory: thespy/observer schema.
OPCP
I Oerror
observer observation
reports
acknowledgements
OPCPIOPCP
O
votingerror
Version 1
Version 2
Fig.8.Duplication versus observ ation.
Ingeneral, N-version programming techniques, thatis,thecontroller isrepli-
cated andavoting mechanism isintroduced [4],canbeused. Alessexpensive
schema isbased ontheideaofanobserver [5]orspy[63],whichaccepts \normal"
behaviours seenthrough someobservable ,orcheck,points.InFig.8duplication
andobserv ation schemas arecompared. Theobserv ablepointsaretransitions
whose ring isreported tothespy/observ er(transitions areclassied asobserv-
ableornon-observ able,dually totheclassication intocontrollable anduncon-
trollable). Thespy/observ ercanbemodelled asaPNequivalenttotheoriginal
onew.r.t. observ abletransitions (nonobserv abletransitions areconsidered silent
andcanbereduced). Inthenalimplemen tation, thecodecorresp onding tothe
spyismerged withthecodeofthepropercontroller. Anobserv erisalsoemplo yed
in[19]forformal validation.
Coming backtotheexample, considering asobserv ableallthesynchronisa-
tiontransitions inthenet(i.e.,those corresp onding totheinitiation ofrobot
operations, initiation ofatransfer fromM1toM2,andinitiation ofanassem bly
inM3)thecorresp onding spyisshowninFig.9.(Notice thatthisspyisobtained
applying thesame reduction rulesthatwereapplied fortheanalysis.)
15

LOAD_M1
LOAD_M2 TRANSFER
START_M3LOAD_M3A LOAD_M3BN
Fig.9.AspyforthenetinFig.1.
3Modelling some classical managemen tstrategies in
manufacturing: pullcontrolandkanban
Theprimary goalofmanymanufacturing systems canbeexpressed interms of
themaximisation oftheproduction rate,theminimisation ofthework-in-pr ocess
(WIP) inventory,andminimisation ofthedelivering delay(dierence between
thedateofademand andthedateofserving it).Theabovecriteria usually
leads tosome contradictory situations. Forexample, minimising WIP usually
leadtohigher delivering delays,what mayevenrepresen tlosing some selling
opportunities (impatien tclients).
Among themanyimaginable strategies forthemanagemen tofproduction
systems, pushcontrolisbased ontheideaof\advancing" tasks relativ etopro-
duction asmuchaspossible. Thusthebehaviour oftheproduction plantis
\externally" constrained bytherawmaterials available, andbythecapacit yof
buers forstoring nished products. Under thisstrategy ,rawmaterials \push
theproduction", anddelivering delaysareminimised attheexpenseof,even-
tually,importantWIPcosts. Inmanycases push-t ypebehaviours usedemand
forecasts togenerate theproduction plans. Onthecontrary,under thebasic
pullcontrolstrategy ,thecustomers demands trigger theproduction, i.e.,\pull
theproduction". ThustheWIPcostisreduced toaminim um,attheexpense
ofmore importantdelaysfordelivering, i.e.,attheexpenseofdecreasing the
qualityofcustomer service.
Inthemanufacturing arena, itiswellknownthatjustintime(JIT) ap-
proachesleadtolowWIPcosts. Inorder toconciliate theabovementioned con-
tradictory performances, manyhybrid push/pull controlalgorithms havebeen
proposedintheliterature. Kanbansystems allowtodealwithdieren tkinds of
those strategies, trying tosmoothandbalance material
owsbyusing severalap-
16

propriately controlled intermediate inventories. Inessence kanbansarecards that
circulate betweenamachine(orsequence ofmachines) andadownstream buer.
When awithdra waloperation liberates aposition ofanintermediate buer, a
cardisrecirculated inorder toallowtheproduction ofanewparttocompen-
sate\theprevious loss"intheinventorysite.Thenumberofkanbansaround a
machine(s)-buer subsystem determines thebuer size.Inakanbancontrolled
system, production ofparts istriggered inresponseto\intermediate demands".
Asalready mentioned inthecellmanufacturing example ofSect.2,theparts in
anyintermediate buer tryto\protect" theoperation ofdownstream machines
frompossible interruptions ofupstream machines. Iftherepairing timeofthe
machineunder failure is\nottoobig",thebuer willnotemptyandthefailure
willnotaect thedownstream machine.Therefore intermediate buers \canbe
perceiv ed"ascondensers inelectrical circuits orresorts inmechanical systems,
allowingrelativ elyuncoupled behaviours onproduction linessubsystems. Acer-
tainnumberofquestions ariseinorder tooptimise theproduction: Where to
puttheintermediate buers?, Howlarge?, Whichstrategies should beusedfor
control?, etc.
Thepointhereisthatatageneral level,Petrinets{with some timed in-
terpretation, forexample, Generalised Stochastic PetriNets[1]{canbeused
tomodeldieren tdesigns andcontrolstrategies. Byusing appropriate perfor-
mance evaluation models,theoptimisation ofthestrategy usedtocontrolthe
material
ow(i.e.,making themore appropriate decisions), eventhetuning of
itsparameters, canbeformally studied.
Single-output assem blymanufacturing systems haveusually ,fromtheoutput
pointofview, atree-lik etopology.Inthemanufacturing domain, itisusual to
represen tmachinesascircles andbuers astriangles (Fig.10).The(output) root
ofthetreerepresen tsthenished goodsbuer. Inorder tosimplify thepresen ta-
tion,letusassume asingle levelassem blystage andtwoprevious manufacturing
stages (Fig.11).
Fig.10.Topology ofanassem blymanufacturing system: machinesareshownascircles
andbuers astriangles.
Thebasicschema ofaproduction stage canbeeasily describ edinPNsterms
bymeans oftheconnected markedgraph inFig.12(a). According tothat,pro-
17

stage 1
stage 2assembly
stage
Fig.11.Twomanufacturing stages (with theirbuers) followedbyanassem blystage
(with thenished products buer).
duction stages arecomposedofarawparts container (raw)synchronised with
ademand forproduction (demand ),followedbythewaiting queue andmachine
working place (dr),andtheplace represen tingthesingle machine(machine );
andnally itsoutput buer ofnished parts (f).Thetransition intheself-lo op
ofthemachineistimed (processing timeofapart). Thustheutilisation rateof
themachineisgivenbytheprobabilit yofnonnullmarking inplacedr(atleast
onepartneeds tobeprocessed).
raw
demanddrmachine
f (finished)
(a)drmachine
f
(b)
Fig.12.Basic schema ofaproduction stage.
Itiscommon incertain cases toassume thatthere arealwaysenough raw
parts. Thismeans thatplacerawcanberemovedbecause itisnotaconstrain t
anymore (itisimplicit: i.e.,itisnevertheunique thatforbids thering ofits
output transition). Indoing so,because thetransition betweenplaces demand
anddrisimmediate, bothplaces canbemerged intoasingle one(wekeepthe
name dr).InFig.12(b), thesimplied modelispresen ted.Itwillbeabasic
building blockforthemodelsofthissection. Inorder tosimplify thedrawingof
nets,inthesequel placemachine willberemoved,while itisassumed thatthe
ring seman ticsofthecorresp onding transitions issingle server [8].Transitions
withsingle serversseman ticswillbegraphically denoted hereasdashed timed
transitions. Observ ethatatthislevelitisassumed thatthemachines donot
fail.
18

Abasicpullcontrolsystem (basestockcontrolsystem ,BSCS [11])ispresen ted
inFig.13.Itconsists oftwoproduction stages (with k1andk2parts nished in
dr1machine1
f1 q1k1
dr2machine2
f2 q2k2dr3 machine3 f3
q3k3delivering
customers
demandsdemand
Fig.13.Production ofparts AandB(stages 1and2)andnalassem bly(stage 3),
withabasicstock(pull) controlsystem (BSCS) andassuming single serverseman tics.
stage 1andstage 2,respectively),feeding anassem blystage (initially withk3
nished parts). When acustomer's demand appears,places dr1anddr2receiv ea
(new) token,inorder toproduceanother partforeachstage. Customers demand
allowstoservenished parts, represen tedbytokensinplacef3,initially marked
withk3tokens.Amain problem inthisbasic schema isthatthelimitation of
theWIPisnotassured inanyofthethree stages (twoforproduction andone
forassem bly,inthepresen tcase). Itisnotdicult toseethatunder saturation
ofcustomers demands (i.e.,under thehypothesis thatthere exists aninnite
numberofcustomers demands), theproduction cycle time(theinverseofthe
throughput) isbounded bytheslowerofthethree machines:
=maxf1;2;3g
Simultane ouskanbancontrolsystem (SKCS)andindependent kanbancontrol
system (IKCS)aremodelled inFig.14andFig.15.Ashappenedbefore, in
bothcasestwoproduction stages arefollowedbyanassem blystage. Evenunder
saturation ofcustomers demands, thecapacit yofthestages arek1;k2andk3,
respectively,while theproduction cycletimeunder deterministic timing isonce
again ,i.e.,dened bytheslowermachine(because allkiaregreater thanzero).
Under stochastic timing, isalowerbound forthecycle time(i.e.,1=isan
upperboundforthethroughput).
Thedierence among SKCSandIKCSisthattherstonefeedssimultane-
ously theassem blystage andthenewproduction order forthe(two)previous
stages. Inthesecond case,separate kanbansfeedstages 1and2,while feeding
theassem blystage isautomatic, when appropriate parts exists (inb1andb2).
19

dr1 f1 q1k1
dr2 f2 q2k2dr3 f3
q3k3delivering
customers
demandssimultaneous
kanban
demand
Fig.14.Simultaneous kanbancontrolsystem (SKCS).
dr1 f1 q1k1
dr2 f2 q2k2dr3 f3
q3k3delivering
customers
demandsb1
b2independent kanban 1
independent kanban 2demand
Fig.15.Indep enden tkanbancontrolsystem (IKCS):Kanbansareindependen tlygen-
erated formachine1andmachine2.
Obviously ,intransien tbehaviours, theindependen tcasecanbebetterthanthe
simultaneous one.
Amore elaborated kanbansystem ispresen tedinFig.16.Itisthesocalled
independent extende dkanbancontrolsystem (IEKCS)[11].Under saturation of
customers demands itbehavesexactly liketheaboveschemes (SKCSandIKCS).
Nevertheless, inthiscasedieren tkanbanssendsimultaneously requests forthe
production ofprimary parts (instage 1andstage 2),foranassem blytobe
done, andforthedeliveryofanished part.Thismayleadtosome interesting
20

sisfdelivering
customers
demandsbiautorization
for assembly i
ki-sikanban i
demand ikf-sf
demand
for assembly if3
q3
demand
Fig.16.Indep enden textended kanbancontrolsystem (IEKCS).
behaviours, potentially reducing theWIP,while keeping agoodreactivit yto
demands.
These controlpolicies havebeensimulated assuming inallcases that1=
0:5,2=1,3=0:4,k1=1,k2=1,k3=2and,forIEKCS,s1=s2=0and
s3=1.Aburst of5simultaneous demands issimulated at15t.u.Theresults
forthedieren tcontrolsystems inFigs.13-16 arerepresen tedinFig.17,where
(a)showsthemarking ofplacedemand (unsatised demand), (b)showsthe
marking ofplacef3(complete products instock),and(c)showsthethroughput
oftheassem blystation. Because the\deliv ering" transition isimmediate, the
unsatised demand at15t.u.isequal to5minustheproducts instock:2for
BSCS, 3forSKCSandIKCS,and4forIEKCS.Inthiscase,BSCS, SKCSand
IKCSneedmoreorlessthesametimeto\satisfy thedemand" (themarking of
theplacedemand returns tozero), while IEKCSisthelastone.However,the
stockofcomplete products inabsence ofdemand ismuchlarger under BSCS
(3),thanunder IEKCS(1).With respecttothethroughput, SCKS, IKCSand
IEKCSworkondemand, sothethroughput iszerobeforethedemand. Under
BSCS, arstoutburst oftheproduction appears,sincetheintermediate stocks
f1andf2areusedtoproducethenalassem bly.Inother words,thesystem tries
tocomplete asmuchproducts asitcan,instead ofkeeping stocksofintermediate
elemen ts.Thatisthereason whyalthough thestockunder BSCS is3andunder
IEKCSisonly1,itdoesnottakethree moretimes tosatisfy thedemand inthe
latter case.
Manyother schemes ofthistypecanbeimagined. Theimportantpointatthis
levelisthatmodelling withPNsisfrequen tlyquite straigh tforward(ifcontrol
strategies donotdependtoomuchonparticular data), andanalysis canprovide
useful information aboutthebehaviour oftheintended controlstrategy .
21

0 10 20 3001234BSCS
SKCS
IKCS
IEKCS
(a)Demand0 10 20 3000.511.522.53BSCS
SKCS
IKCS
IEKCS
(b)Stock(marking off3)
0 10 20 3000.511.522.5
BSCS
SKCS
IKCS
IEKCS
(c)Throughput oftheassem bling station
(labelledwith3)
Fig.17.Simulation ofthedieren tcontrolpolicies inFigs.13-16.
4Acoloured modelforacarmanufacturing line
Arelativ elyfrequen tcharacteristic ofproduction systems istheexistence of
symmetries duetothepresence ofsubsystems thatbehave\inasimilar way".
Coloured PNsallowtoexploit these symmetries andgenerate amore compact
model.Coloured Petrinetscanalsobeextended, asin[30,31],orabstraction
ontheformalism (i.e.,theunderlying PNmodel)canbedoneinapplication
orientedinterfaces, asin[64].Herejustbasiccoloured Petrinetswillbeusedto
modelsome examples.
4.1Acarmanufacturing system
Thefollowingexample showsacoloured PNmodelofarealistic MS(part ofa

exible workshop ofacarfactory), takenfromacasestudy [39].
TheFMSshowninFig.18consists of:
22

Si
P
U LS1 Sn
T1 Ti TnLP
U FUFP
FL
load unload
input
outputnextT
FT(n,x,out)
1(1,x,in)
nx(x,x,in)(x,x,out)
xx xx xxx x
x
x x
xx
x x+1Stations
Transport(y,x,z)(y,x+1,z)
Fig.18.A
exible workshop thatprocesses carbodiesinseveralstations, andits
coloured PNmodel
{Severalworkstations (S1toSn).Alltheworkstations behaveinasimilar
way:carbodiestobeprocessed areloaded intableL(input buer ofcapacit y
one), thentransferred totableP(actual processing), andthentransferred
totableUforunloading (output buer ofcapacit yone). Forsimplicit y,we
disregard thenature oftheprecise operations performed inthestation, and
therefore, werepresen tamodelofageneric workstation. Astation behavesas
apipelinewiththree stages: L,P,andU,represen tedbythecorresp onding
places, whichcanbeactivesimultaneously .Thecomplemen taryplaces FL,
FP,andFUrepresen t,when marked,thattherespectivestage isfree.The
colour domain ofallthese places isf1;:::;ngforthestations. Atokenof
colour iinplacePrepresen tsthatworkstation Siisprocessing. Transferring
aprocessed partfromtablePtotableUinworkstation Sirequires one
i-tokeninPandFU,andputsonei-tokeninUandFP.
{Anunidirectional transp ortsystem, consisting ofseveralroller tables (T1
toTn).Carbodiesenterthesystem intableT1andleaveitfromTn,
afterbeingprocessed inonestation (theonedecided bythescheduler). The
modelforthistransp ortsystem consists oftwoplaces, TandFT,forthe
occupied andfreetables, andtransitions torepresen ttheinput oroutput
ofacarbody,amovementtothenexttable, andtheloadorunload of
astation. Thecolour domain ofFTisf1;:::;ngforthetables, andthe
colour domain ofTis(f1;:::;ng;f1;:::;ng;fin;outg),where thersteld
identiesthetable, thesecond onethedestination station ofthecarbody,
andthethird onethestatus ofthecarbody(inwhen notyetprocessed
andoutwhen ready toleavethecell).Notice that,atthering oftransition
input,adestination station isassigned totheincoming carbody.Innet
23

terms, thismeans solving acon
ict among thedieren tring modesofthe
input transition. Thedestination isdetermined bythescheduler, possibly
taking intoaccoun tthestateofthesystem andtheproduction requiremen ts.
That is,thescheduler (placed atahigher level)controlsthebehaviour of
thecoordination modelrepresen tedbythecoloured PN.
Thecomplete netmodelisobtained merging theloadandunloadtransitions
ofthesubmo delsfortheworkstations andthetransp ortsystem. Theloading of
SifromTiisrepresen tedbythering oftransition loadinmodei:itconsumes
atoken(i;i;in)fromTandani-tokenfromFLandputsi-tokensinLandFT.
Similarly fortheunloading, where the\status" colour ofthetokendeposited
inTisoutindicating thatthecarbodyinthecorresp onding table hasbeen
processed.
4.2Onthecontroloftheproduction line
Besides avoiding deadlo cks,letusconsider acontrolpolicytoimpro vetheper-
formance.
i i+12
31
4
i i+11
2
3
Fig.19.(a)Complete deadlo ck(b)Temporary deadlo ck.
Analysis ofthissystem provestheexistence ofdeadlo cks:when allthetables
inagivenstation areoccupied andacarbodyiswaiting inthecorresp onding
table ofthetransp ortsystem toenterthisstation, adeadlo ckisreached,see
Fig.19(a). Thedeadlo ckcanbeavoided bymaking surethatnomore than
three carbodiesscheduled forthesamestation arepresen tinthesystem atany
time. Thiscanbeenforced bylimiting thenumberofrings ofinput inagiven
modew.r.t. thenumberofrings ofoutput inthatmode.Thisisimplemen ted
byplaceO(fororders) inFig.20(a), whose colour domain isf1;:::;ngforthe
destination stations, markedwiththree tokensofeachcolour.
Notice that,ifOismarkedwithtwotokensofeachcolour instead ofthree,
unnecessary stoppages inthetransp ortsystem, thatcould reduce thethrough-
put,areavoided. These stoppages appearwhen acarbodywaitsinfrontof
itsdestination station because thisstation isprocessing andtheloadtable is
24

LP
U FUFP
FL
load unloadx xx xxx x
x
x x
xx
inputoutput
nextT
FT(n,x,out)
1(1,x,in)
nx(x,x,in)(x,x,out)
x
x x+1(y,x,z)(y,x+1,z)
xx
O(a) (b)LP
U FUFP
FL
load unloadx xx xxx x
x
x x
xx
inputoutput
nextT
FT(n,x,out)
1(1,x,in)
nx(x,x,in)(x,x,out)
x
x x+1(y,x,z)(y,x+1,z)
xx
Ox
Fig.20.Adding placeOtothenetmodelinFig.18,withasuitable marking, avoids
deadlo cksandstoppages.
occupied, seeFig.19(b). Wecannot proceedtoloadthethird carbodyuntil
processing iscompleted, theprocessed carbodyistransferred tothetable U,
andthecarbodyintable Listransferred totable P.Inthemeanwhile, other
carbodiesmaybepreventedfromadvancing totheirdestination beyondthat
station.
Therstcolumns inTable1(observ etheoutput) compare thesteady state
throughput ofthese twocontrolpolicies fordieren tprocessing times inathree
cellsworkshop. Allthecellsareassumed tobeequal, andthecarbodiesare
senttoallofthem withthesame probabilit y.Thetransitions areassumed to
followexponentialdistributions, ofmean oneforallthetransp ortoperations
(bothinside andoutside thecells). Itcanbeseenthat, iftheprocessing is
fastwithrespecttothetransp ort,thetwopolicies aremore orlessequivalent.
However,iftheprocessing takes\muchtime", thethroughput isbetterunder
themost restrictiv epolicy.Intuitively,since theprocessing needs more time
thanthetransp ortation, itisbettertobesurethattheparts canadvancetill
theprocessing station.
Finally ,intheabovecontrolitwasassumed thatthescheduler controlstran-
sition input andobserv esjusttransition output .Ifalsotheoccurrences oftran-
sition unloadwereobserv ed,itmightbepossible toimpro vetheperformance
ofthecontrolpolicybyallowingalimited numberofunprocessedorders inthe
system (seeFig.20(b)).
Table1compares theresults ofbothcontrolpolicies fortheprevious example.
Itshowsthatifthenumberoforders allowedinthesystem foreachmachine
25

Mean Observ etheoutput Observ etheunload
processing Throughput Throughput
time Three orders Twoorders Increase Three orders Twoorders Increase
1 0.2971 0.2984 0.45% 0.2969 0.3002 1.11%
5 0.2434 0.2763 13.54 % 0.2378 0.2809 18.14%
10 0.1669 0.2173 30.24 % 0.1617 0.2210 36.66%
15 0.1227 0.1671 36.17 % 0.1189 0.1690 42.12%
20 0.0964 0.1331 38.07 % 0.0935 0.1341 43.45%
50 0.0418 0.0578 38.51 % 0.0406 0.0579 42.70%
Table1.Throughput comparison forthesystem inFig.20(a), ifplaceOismarked
withtwoorthree tokensofeachcolour.
is2,thethroughput increases slightlywhen theunloadtransition isobserv ed.
However,ifthree orders areallowed,thethroughput decreases. Intuitively,with
atmost three orders foreachmachinethesystem wasalready saturated, and
allowingagreater numberofcarbodiesonlymakesitworse.
5Onaproduction lineforovens
Thissection describ esanewmanufacturing system where thesetofproduction
orders competeforasetofphysical resources. Thesystem isquite similar to
theoneintheprevious section. Here, theattentionisfocused onhowtoobtain
thecoloured Petrinetmodel,byrstmodelling theplantlayouttaking into
accoun tthepossible waysparts can
owthrough thesystem andthenimposing
toeach
owingparttheexecution ofitsassociated processplan,whichneeds of
modelrenemen t.Finally ,itwillbeshownhowtopreventdeadlo cksandhow
thedeadlo ckrelated controlapproac hcanbeimpro vedtaking amore abstract
pointofview.
5.1System description
Fig.21(a) depicts thestructure ofa
exible manufacturing cellfortheproduction
ofmicrowaveovens(amore detailed description canbefound in[24]). The
cellhasanentrystation,EntryStation ,anexitstation,ExitStation andn
workstations, w0;w1;:::;wn1.These workstations areloaded andunloaded by
acircular conveyorbeltwithacontinuous movementinaunique direction.
Themanufacturing ofeachovenismade according toitsprocessplan. There
areseveralscales andmodelsofovenswiththeirrespectiveprocessplans. The
componentsofanovenarriveatEntryStation afterhavingbeenpreviously
pre-assem bled;onceanovenreachesthatpoint,itisxedtoapallet thatwill
beinserted intothetransp ortsystem when possible. Oneofsuchloaded pallets
mustvisitasetofworkstations, according totheprocessplanofthepartit
contains, andthenleavethesystem through theExitStation .Thepallet goes
thentothepallet store, tobereused. Thesystem hasatotalofKpallets.
26

Input
BufferOutput
BufferSection AiSection Bi Section Bi-1
wsiSensor Ri Sensor Li
Input
BufferOutput
BufferSection AiSection Bi Section Bi-1
wsiSensor Ri Sensor Li
(b)EntryS tation
(a)ExitS tationpallet store
Bn-1wsn-i-1
wsiBk Expallet store
Bn-1wsn-i-1
wsiBk Ex
Fig.21.a)General plantrepresen tation ofacellforthemanufacturing ofmicrowave
ovens.b)Detailed viewofthestructure ofaworkstation anditsrelated sections.
Asdetailed inFig.21(b), eachworkstation wihasaninput buer Iiandan
output buer Oi.Both consist oftworoller tables, eachwithcapacit yforone
pallet. Thepallets ineachbuer followaFIFOpolicy.Aworkstation canoperate
withonepallet atatime. Inorder tocontrolthesystem, theconveyorbelthasa
setofsensors distributed asshowninFig.21(b): R0;L0;:::;Rn1;Ln1andEx.
Associated tothesedetection pointstherearemechanisms that,under thecontrol
oftheworkshop coordination system, allowtocarry outthefollowingtransfer
operations, schematised bymeans ofarrowsinFig.21:introduction ofapallet
fromEntryStation ,exitofapallet fromtheExpointtowardsExitStation ,
loading ofapallet inworkstation wibytransferring itfromposition Ritothe
input buer ofwi,Ii,unloading ofapallet fromtheoutput buer ofwi,Oi,to
pointLioftheconveyorbelt.EachAiorBisection willhaveitsowncapacit y,
whichcorresp ondstothenumberofpallets thesection canhold.
5.2Acoloured Petrinetmodelofthecoordination system
Arstapproac htothemodelling ofmaterial
owisshowninFig.22.Letus
explain themainelemen tsinthemodel.
Thetransp ortsystem: Thesetofstates apallet canbeinthetransp ort
system ismodelled bymeans ofplaces B;R;A;L.Place Bmodelstheset
ofBsections. Place AmodelsthesetofAsections, while places Rand
Lmodelsensor pointsbetweensections Bi1andsection Aiandbetween
sections AiandBi,respectively.Thecolour domain ofallthese places is
WS=fw0;:::;wn1g,thesetofworkstations. Theinitial marking ofeach
oneofthese places isthemulti-set 0,whichmeans that,attheinitial state,
nopallet isinside thesystem. Transitions tinandtoutmodeltheactions
bywhichapallet withanewovenentersthesystem andapallet witha
27

terminated ovenleavesthesystem, respectively.Ordinary (non-coloured)
place APmodelsthesetoffreepallets, whose initial marking isK,the
numberofavailable pallets. Inthesystem, itisassumed thatEntryStation
loads pallets intosection Bn1andthatExitStation unloads pallets from
section Bk.
Places BCandAC,whose colour domain isalsoWS,modelthecapacities
ofBiandAisections, respectively.Theinitial marking ofBCisthemulti-
setPn1
i=0bi
wi,beingbithecapacit yofsection Bi.Analogously ,theinitial
marking ofACisthemulti-setPn1
i=0ai
wi,beingaithecapacit yofsection
Ai.Places CRandCLrepresen tthatonlyonepallet canbeinsensor points
RiandLi,respectively.Theinitial marking ofbothplaces isPn1
i=01
wi.
Transition tbrmodelsapallet reachinganRisensor (thefunction labelling
thearc(tbr;R),w@1,represen tstheaddition of1,modulothenumberof
sections, n).Transition tramodelsapallet entering anAisection, transition
talmodelsapallet reachinganLisensor. Finally ,transition tlbmodelsthat
apallet reachesaBisection.
Transition tls(tus)modelsapallet beingloaded into(unloaded from) a
workstation.
Thesetofworkstations: Apallet loaded intoaworkstation, bymeans ofthe
ring oftransition tls,must,successiv ely,visitthetwoinput buer positions
(places IP1andIP2),tobeprocessed intheworkstation (place W),and
visitthetwooutput buer positions (places OP1andOP2).Theinitial
marking ofanyofthese places isthemulti-set 0:there isnopallet inany
workstation.
Places IC1;IC2;WC;OC1andOC2imposethecapacit yconstrain tsofbe-
ingabletohaveatmost onepallet ineachoneofthecomponentsofa
workstation. Theinitial marking ofanyofthese places isAW=Pn1
i=01
wi.
Itisimportanttonotice that,evenifallthetransitions inthemodelrepresen t
system actions thatchange thesystem state, fromthecontrolpointofviewtwo
kinds oftransitions areconsidered:
{Transitions whose ring isobserv ablebutnotcontrollable. Thisisthecase
offtbr;tra;tal;tlb;ti12;to12g.Since theconveyorhasacontinuousmovement
thering ofoneofsuchtransitions willberealised when apallet reaches
orleavesthecorresp onding sensor. Theeventscanbenoticed andthusthe
system statecanbeupdated inthemodel.
{Transitions whose ring isdecided andexecuted bythecontrolsystem (con-
trollable transitions). These arethetransitions thatcanbecontrolled inor-
dertoensure thateveryincoming partwillbeprocessed according toitsasso-
ciated processplan,andalsotoimposesomecontrolpolicyinorder toensure
some desired properties, asdeadlo ckfreeness ortoimposesome scheduling
policies. Thissetoftransitions iscomposedofftls;tus;tin;tout;tiw;towg.
5.3Inclusion oftheprocessplans
Eachoventhatentersthesystem mustexecute itsassociated processplan,which
consist ofasequence ofoperations tobeexecuted inthesystem workstations.
28

IC1
W
OC1IP1 IP2
OP1 OP2ti_12
to_12ti_wIC2
to_wBAP
t_lbt_outt_br R
Lt_alt_in w w w w
w
w
w w w wwww w
w
w
w w wWCw@1
wA Kw
w
w
wwn-1
w
w
wkt_raw
w
ww
ww
wt_ust_lsw
ACBC
n-1
kworkstations transport system
OC2www ww@1
wwwCR
CLw
Fig.22.Acoloured Petrinetmodelof
owofpallets inthesystem inFig.21.
Thissequence isdescrib edbymeans ofasequence ofpairs(o;w),where ode-
nestheoperation tobeexecuted, andwtheworkstation where suchoperation
mustbedone. Thesequence ofoperations foranovenhasbeenpre-established
bythesystem controller beforeloading theovenintothesystem. Inthespeci-
cation levelconsidered here,whichconcen trates onthematerial
owcontrol,it
ispossible tomakeabstraction oftheoperations tobeexecuted, describing the
processplanastheordered sequence ofworkstations tobevisited bytheoven.
Therefore, aprocessplanwillhavethefollowingform: p=(w1
p;w2
p;:::;wnpp),
where eachwi
p;i2f1:::npg,belongs toWS.
There exists asetofpredened processplans PPWS+.Eachpartthat
entersthesystem hasanassociated processplanbelonging toPP.Therstele-
mentintheordered sequence ofworkstations intheprocessplancorresp ondsto
therstworkstation tobevisited. Inorder toidentifythestateintheprocessing
ofapartinthesystem, tuples oftheform(p;i)2PPNwillbeused:pidenties
theprocessplan, while iidentiestheposition intheprocessplansequence of
thenextworkstation tobevisited. Forinstance, when anovenwhose associated
processplanisp=(w1
p;w2
p;:::;wnpp)entersthesystem, itwillbeidentied by
means ofthetoken(p;1),meaning thatw1
pisthenextworkstation tobevisited.
When theovenisprocessed inw1
p,thetuple identifying theovenwillbe(p;2);
when terminated, itwillbeidentied bymeans of(p;np+1).
According tothiscodication oftheprocessing stateofanoveninthesystem,
themodelinFig.22mustbetransformed. Since thesystem layoutisstillthe
same, onlycolour domains andfunctions inthearcshavetobechanged. Ifinthe
initial modelatokeninplace A,forinstance, wasoftheformw,justindicating
theconcrete A-section where thepallet was,nowatokeninsuchplace willbeof
theform(p;i;w)indicating thatthere isapallet inwA-section, containing an
ovenwhose associated processplanispandthathastonextvisitworkstation
29

wi
p.Accordingly ,thecolour domain ofplaces modelling physical locations that
cancontainpallets withovensisPPNWS.
Notice that, inorder toforbid apallet toenteraworkstation thatisnot
itsnextdestination, predicate [wp
i=w]hasbeenassociated totransition tls.
Also, predicate [i=np+1]hasbeenassociated totransition toutsothatonly
pallets containing ovenswhose processplanhasbeencompletely executed canbe
unloaded fromthesystem. Notice alsothatthering oftransition towtransforms
atokenoftheform(p;i;w)into(p;i+1;w),whichcorresp ondstochanging the
nextdestination workstation fortheconsidered oven.
Theresulting modelisshowninFig.23,whereplacesmodellingresource
capacityconstraintshavenotbeenrepresented,forthesakeofclarity.Inany
case,theyareexactly thesame asinFig.22.
WIP1 IP2
OP1 OP2ti_12
to_12ti_w
to_wBAP
t_lbt_br R
Lt_alt_in (p,i,w) (p,i,w) (p,i,w) (p,i,w)
(p,i,w) (p,i,w) (p,i,w)
(p,i,w)A K
t_us(p,i,w)(p,i,w)
(p,i,w)
(p,i,w)(p,i,w@1)
(p,i,w)(p,i,w)
(p,i,w)p
i[w =w]
t_ls
t_out
[i=n +1]p(p,1,w )n-1
(p,i,w )k(p,i,w)
(p,i,w)(p,i+1,w)t_ra
(p,i,w)
Fig.23.Acoloured Petrinetmodelofthesystem inFig.21oncetheprocessplans
areconsidered (capacit yconstrain tshavenotbeenrepresen ted,forthesakeofclarity).
5.4Preventingdeadlo cks.Arstsolution
IfthecontrolmodelinFig.23isdirectly implemen ted,thesystem canreach
deadlo cksituations. Letusconsider, forinstance, areachable stateinwhicha
workstation wiisfull(input andoutput buers arefullandtheworkstation is
alsoprocessing anoven)andalsothetransp ortsystem isfullofpallets thatmust
enterworkstation wi.Inthissituation, nonewpallet canenterthesystem, no
pallet intheconveyorcanbeloaded intoworkstation wiandnopallet canleave
itsincetheconveyorisfull.Allthedeadlo cksituations arerelated tostates in
whichfullstations require tounload pallets tothetransp ortsystem, whichis
fullofpallets thatmustenterafullworkstation.
Aneasywayofpreventingsuchsituations consists inensuring thatnomore
thanvepallets inside thesystem needtovisitagivenworkstation. Thisisthe
30

deadlo ckcontrolimplemen tedinthefollowing. Theimplemen tation isbased on
thefollowingfunction, called workstation requirements ,anddened asfollows.
Letp=(w1
p;w2
p;:::;wnpp)beaprocessplan, andleti2f1;:::;np+1gbean
index associated top.Forthetuple (p;i)thefollowingmulti-set ofworkstations
isdened: wr(p;i)=Pn1
j=0j
pi
wj,where j
piis1ifwj2fwi
p;wi+1
p;:::;wnppg
(inthecaseofi=np+1theaddition ismade overanemptysetofworkstations,
anditisassumed tobetheemptymulti-set). Notice that,infact,wr(p;i)isthe
characteristic function oftheworkstations tobevisited bytheovenfromthe
index iuntiltheassociated production planisterminated. Notice alsothatif
i1<i2,thenwr(p;i1)wr(p;i2).
DPSt_in
t_uswr(p,1)
wr(p,i-1)-wr(p,i)
Fig.24.Theimplemen tation ofadeadlo ckpreventionsolution fortheconsidered sys-
tem.
Inorder toimplemen tsuchcontrolpolicyinthePetrinetmodelplace DPS
(Deadlo ckPreventionSolution) isadded, whose colour domain isWSandwhose
initial marking isthemulti-setPn1
i=05
wi(Fig.24showsthePetrinetelemen ts
tobeadded tothemodelinFig.23).Forapallet thatentersthesystem (ring
transition tin)withanovenwhose associated processplanisp,thesetofpossible
workstations thepallet mustvisitis\reserv ed".Thisisimplemen tedbymeans of
thefunction wr(p;1)labelling thearc(DPS;tin).Moreo ver,eachtimeapallet
leavesaworkstation, ifthisovendoesnotneedtovisitthatworkstation again
inthefuture, thereserv ation mustbereleased. Thisisimplemen tedbymeans
ofthearc(tus;DPS).Asnoticed previously ,thelabelwr(p;i1)wr(p;i)
isproperlydened since i1<i.Notice alsothatthecontrolisrelated to
transitions tinandtus,whicharebothcontrollable.
5.5Preventingdeadlo cks.Amore accurate solution
Thesolution fordeadlo ckpreventionjustproposedisofthesame typeasin
Sect.4.However,taking adetailed lookatanabstract viewoftheunderlying
non-coloured modelamore accurate solution canbeadapted. Letus,forin-
stance, consider aprocessplanp=(w1;w2).Taking intoaccoun tthatwithan
adequate controleverypallet inthetransp ortsystem canreachanyworkstation
31

andalsothateveryfreeposition inthetransp ortsystem canbeusedforthe
downloading ofanyworkstation, theordinary PetrinetinFig.25isanabstract
viewoftheprocessing ofapartwhose processplanisp.
t_ls,p,1 t_us,p,2 t_ls,p,2 t_us,p,3t_out,p t_in,pAP
TSBRAL,p,2 BRAL,p,3 BRAL,p,1K
Mw_2,p,2
IWO_1 IWO_25 5w_1,p,1
Fig.25.Anabstract pointoftheprocessing ofapartwhose associated processplan
isp=(w1;w2).
Themeanings ofthedieren telemen tsinthemodelarethefollowing. Place
TSinanabstraction ofthewhole transp ortsystem; itsinitial marking isM=Pn1
i=0ai+bi,thetotalnumberofavailable locations forparts intheconveyor.
Place IWO1,whose initial marking is5,modelsthetotalcapacit yofworkstation
w1,considering inittheinput buer, theoutput buer andtheworkstation itself.
Places \BRAL;p;"modelthedieren tstates ofapartoftypepinthetransp ort
system. Transitions \tls;p;"modelthedieren trings oftransition tlswhen the
processing ofapartoftypepadvances. Analogously fortransitions \tus;p;".
Transition tin;p(tout;p)modelstheloading (unloading) ofpartoftypepinto
(from) thesystem. Considering themodelsofalltheinvolvedprocessplans, a
nalmodelwillbeobtained bymeans ofthefusion oftheplaces inthemodels
oftheprocessplans corresp onding tothecapacities oftheresources theyshare.
Theresulting Petrinetbelongs toaclass ofresource allocation systems
(RAS) whichhavebeenintensiv elystudied intheliterature, andforwhicha
widesetofdieren tapproac hesfordeadlo ckpreventionandavoidance havebeen
developed.[23,58]useanstructure-based approac htosynthesise thedeadlo ck-
freeness related control.Inbothcases, thePetrinetstructure (siphons) isusedto
characterise deadlo ckproblems andalsotoobtain generalised mutual exclusion
solutions thatforbid deadlo ckrelated stated. These mutual exclusion constrain ts
areimplemen tedbymeans oftheaddition totheformer uncon trolled modelof
newplaces andarcs.Anyofthesolutions canbeusedtocontrolthesystem here
considered. Theimplemen tation canbedoneasin[22],inananalogous wayas
intheprevious subsection, bymeans oftheaddition ofacontrolplace (asisthe
caseofplace DPSpreviously used) andsome related labelledarcs.
32

Theuseofanyoftheselastapproac heswillyield, ingeneral, morepermissiv e
solutions thanusing theapproac hinsection 5.4(thelessstates oftheuncon-
trolled system acontrolpolicyallows,thelesspermissiv eitis).However,they
havethedrawbackthatsincethecontrolisbased onadeepuseoftheabstract
unfolded modelandthecompetition relations among theinvolvedprocessplan
models,theaddition ofnewprocessplans willrequire there-computation of
thenecessary control,making theapproac hlessadaptable tochanges inthe
production thanusing theapproac hinsection 5.4.
6Additional examples: onmodelling andanalysis
Among theadvantages offormal modelling areprimarily therational, non-
ambiguous, \complete" description ofbehaviour andthecapabilit yofanaly-
sis.Intheactual state oftheart,analysis isnotalwaysstraigh tforward,even
\ecien t"techniques maynotbeknown.
Insomecases, analysing the\natural" modelanengineer produces isnotan
easytask.Thisisduetothefactthattheresulting modelcanbecomplex. Anal-
ysistechniques (mainly those techniques thatdonotusethereachabilit ygraph
orsimulation, suchasstructure-based techniques ortransformation techniques,
forinstance) havesomelimitations forgeneral Petrinetmodels,becoming more
dicult when using highlevelPetrinets.Inthissection twonewpractical cases
aredescrib ed.Therstoneusesordinary Petrinetmodels,butthere arenot
techniques abletocontrolthenatural model(deadlo ck-freeness related control
isonceagain theobjective).Thisproblem isthensolvedbythetransformation
oftheinitial modelintoonewithanequivalentbehaviour, andforwhichcontrol
techniques exist. Thesecond caseusesadieren tmodelling approac h,based
ontheNets-within-Nets paradigm asusedin[62].Thisparadigm fallsintothe
object-orien tedmodelling approac h.
6.1Modelling anddeadlo ckavoidance foratwocellsmanufacturing
system
Theobjectiveistomodelandcontrol,avoiding deadlo ckstates, themanufac-
turing system intheDepartmen tofComputer Science andSystems Engineering
oftheUniversityofZaragoza. Todothat,ordinary Petrinetshavebeenselected
asthemodelling tool.Itcould havebeenmodelled alsousing coloured PNs,as
theprevious examples. However,sincethetechnique thatisbeingusedforthe
controlneeds anon-coloured model,ithasbeendecided touseordinary nets
instead ofbuilding acoloured modelandunfolding itafterw ards.
Thesystem andthemodelling approac hFigure 26depicts theplantof
themanufacturing cell,consisting ofsixmachines (M1toM6)thatprocessthe
components,onebuer withplace tostoreupto16intermediate products, and
tworobots(R1andR2).Theprocessisorganised intworings, withthebuer
connecting them. Analproduct(Fig. 27)iscomposedofabaseonwhich
33

three cylinders areset.Thebasemaybeblackorwhite, andthere arethree
typesofcylinders: cylinders thatarecomposedofacase, apiston, aspring,
andacover(called \complete" cylinders), cylinders withjustacaseandacover
(called \hollo w"cylinders), andcylinders inonepiece(called \solid" cylinders).
Thecases andthesolidcylinders maybered,blackormetallic. Bases, pistons,
springs, covers,cases, andsolidcylinders areconsidered astherawmaterials.
Anunbounded amoun tofrawmaterial isassumed tofeedthesystem. Asetof
330dieren tproducts canbecomposedusing these materials.
Fig.26.Aplanofthephysical system.
Theprocessing goesasfollows:machineM1takesacasefromafeeder, and
veries thatitcorresp ondstotheorder, thatis,ifthecolour iscorrect and
whether itisacaseorasolidcylinder. Ifitisnotcorrect, thenitisdiscarded,
otherwise, itisputonapallet, andthekindofprocessing thatthepartneeds
iswritten onthepallet. Ifitisasolidcylinder, aswitchisactivatedtocarry it
directly toM4.Otherwise itgoestoM2.MachineM2putsthepiston andthe
spring, ifthecylinder needs them, andthenthepartgoestoM3,whichadds
thecover.InM4theparts areveried, thepallets arereleased andtheparts
areputonaconveyorthatmovesthem totheentrance ofthebuer. Machine
M5cantemporarily storethecylinders inthebuer. When needed toassem ble
thenalproduct, M5putsthem inaconveyorthattakesthem torobotR1.
MachineM6putsabaseoftherightcolour onapallet, anditiscarried torobot
R1.Therobottakesthethree cylinders onebyoneandputsthem onthebase.
Theproductisthencomplete, andgoestorobotR2,whichtakesitoutofthe
system.
Theadopted modelling approac hisasfollows.Eachpossible production order
(corresp onding toatypeofproduct) hasbeenmodelled bymeans ofaPetrinet.
Then, asetofplaces, modelling thecapacit yconstrain tsofthephysical resources
involvedintheproduction process(robots,intermediate store, pallets, etc.),have
beenmodelled.
Figure 28showsthePetrinetmodelofoneoftheproducts inthesystem
hereconsidered: aproductmade ofthree complete cylinders isshown.Place
34

Fig.27.Thekindofproducts thatthesystem inFig.26produces.
M1
C1_2M2
C2_3M3
C3_4
INPUT_M4M4 C_INPUT_STORE
STORE
C_OUTPUT_STOREFREE_STORE16M5

M6 C6_R1
R1
LOAD CL_U
I_O_POSITION
IDLEPALLETS_1
PALLETS_2R2Orders

_4
Fig.28.Anon-sequen tialRASmodelling theassem blyofaproductmade ofthree
complete cylinders andabase.
IDLErepresen tsthestate inwhichtheproduction order hasnotbeenstarted,
therestof\tagged" places modelthesystem resources (resource places), while
the\non-tagged" places modelthedieren tstates ofthecomponentelemen ts
inside thesystem (state places). Intheexample theresources areoftwokinds.
Ontheonehand there aremachines, robots,andspace intheintermediate
buer (i.e,physical constrain ts).Ontheother, there areconstrain tsthatarenot
strictly necessary butareadvisable forthecorrect evolution ofthesystem, for
example nottoallowmorethanonepallet oneachconveyorsegmen t,thatmake
theconveyorsegmen ttobeconsidered asaresource withcapacit yone.Thenal
modelwillbeobtained bymeans ofthecomposition, byfusion ofthecommon
places modelling system resources, ofthemodelscorresp onding tothewhole set
ofproducts.
Deadlo ckavoidance controlInorder tohaveacompletely automated sys-
tem,theobjectivenowistosynthesise thecontrolnecessary toensure thatno
35

deadlo ckscanappear.AsinSect.5.4,thesystem fallsintotheclassofResource
Allocation Systems: itiscomposedofasetprocesses whichintheirexecution
mustcompeteforthesetofsystem resources. Thecomplexit yofdealing with
deadlo cksstrongly dependsonthesystem structure. Dieren tclasses ofRAS
systems havebeendened intheliterature. Thefeatures thatdistinguish these
classes refertotheprocessstructure (wether theprocessissequen tialorcon-
curren tandwhether routing
exibilit yisallowedornot,mainly) andtheway
inwhichresources areallowedtobeusedandallocated/released (one-b y-one
orasmulti-sets). These characteristics dene theclassofPetrinetsthemodel
belongs to.Inthecaseofaprocesswithasequen tialnature (sequen tialRAS),
astatemachinecanbeusedtomodelit(places modelling constrain tscapacities
imposedbythephysical orlogical resources havethentobeadded); inthecase
ofnonsequen tialprocesses, moresophisticated Petrinetmodelsareneeded, in-
cluding fork/join ttransitions (non-sequen tialRAS). Insystems where resources
areallowedtobeallocated/released asmulti-sets, weightswillappearinthearcs
related toplaces modelling resources, whichmeans thatthemodelwillbelong
totheclassofgeneralised Petrinets.These elemen tswilldirectly in
uence the
analysis andsynthesis capabilities ofthePetrinetmodel.
An\easy" wayofapplying deadlo ckrelated controlisbased onthecom-
putation ofthereachabilit ygraph ofthesystem model,todetect thedeadlo ck
states andthentoforbid them someho w.However,computing thereachabilit y
graph ofthewhole system wasnotpossible, because ofitsenormous size(for
instance, thereachabilit ygraph ofjustoneproduction order astheoneinFig.28
has2442states, while thereachabilit ygraph withtwoproduction orders being
concurren tlyexecuted had241951 states; computing thereachabilit ygraph in
thecaseofthree production orders wasnotpossible). Therefore, some dead-
lockprevention/a voidance strategy based onthemodelstructure instead ofthe
reachabilit ygraph isneeded.
Inthecaseofsequen tialRASmanydieren tsolutions canbefound inthe
literature, adopting dieren tpointsofview. See,forinstance, [23,35,43,26]asa
veryshort listofsolutions. However,inourconcrete case,there existtransitions
withmore thanoneinput stateplace (seeFig.28),whichmakeoursystem to
belong tothenon-sequen tialRASclass. Adopting aPetrinetperspective[47,
28]proposedeadlo ckavoidance solutions forsub-classes ofassem blysystems.
However,thepresen tsystem fallsoutofthese classes.
Inthesequel, adieren tengineering strategy isadopted: totransform the
problem intoonewithknownandapplicable solutions. Ifadeadlo ckavoidance
strategy isadopted, anyresource-related state change inthesystem mustbe
controlled insuchawaythatonlyifthereachedstateisprovedtobesafe(safe
means thatitcanbeensured thatalltheactiveprocesses canbeterminated) the
change isallowed,otherwise itisforbidden. Thismeans thattheapplication ofa
deadlo ckavoidance metho dimposesakindof\sequen tialisation" inthesystem
behaviour. Therefore, andconcen trating ontheexecution ofaproduction order,
substituting itsmodelbythestate machinecorresp onding tothereachabilit y
graph oftheproduction modelitselfisjustachange inthemodel,butnotin
36

thebehaviour. Notice thatdoing soasequen tialRASmodelforthesystem is
obtained. Resource places oftheinitial modelareadded tothisstatemachine
(they areimplicit places andcanbeadded without changing thebehaviour)
andthenalsystem modelisobtained bymeans ofthecomposition byfusion
oftheplaces modelling system resources ofthesequen tialmodelsoftheset
ofproducts. Theconsidered modelbelongs totheclassofsystems forwhicha
deadlo ckavoidance metho disproposedin[26],whichcanbe,then, applied to
controltheconsidered system.
Thecontrolisbased onanadaptation oftheBanker'salgorithm [20,33].
Inorder toconsider agivenstate assafe,theBanker'salgorithm looksforan
ordering inthesetofactiveprocesses suchthattherstprocesscanterminate
using theresources grantedtoitplusthefreeones, thesecond processcan
terminate using theresources itholds plustheonesfreeuponthehypothetical
termination oftherstprocess,andsoon.Thebasic stepistoknowifagiven
processisabletoterminate using agivensetofavailable resources. Thesolution
in[26]isatwostepsalgorithm. First, markthose stateplaces ofthestatemachine
modelling theconsidered processandthatrequire nomore resources thanthe
freeonesplustheonesinusebytheprocessitself. Second, lookforapathof
markedstateplaces joining theplace corresp onding tothestatetheprocessis
inandthenalstate.
Oneimportantissue when applying deadlo ckavoidance approac hesisthe
timeusedtodecide whether agivenstate issafe,since theprocedure must
becalled everytimeastate change engages newresources. Implemen tingthe
controlmetho dthefollowingresults havebeenobtained. Inthecaseofthenon-
sequen tialRASinFig.28,thecorresp onding sequen tialmodel(thereachabilit y
graph ofthenetinthatgure) has2442state places, 7814transitions, using
eachstate upto22typesofresources. Checkingifanactiveprocesswasable
toterminate using thefreeresources hasbeenimplemen ted.Itstakesabout
0.003 CPU seconds using aPentium(4) processor at1.7GHzunder Microsoft
Windo ws2000operating system (thiscomputation usesaDepth First Search
algorithm, whichislinear inthesizeoftheunfolded system). Ifthewhole system
isconsidered, andgiventhatnomorethan26componentscanstayatthesame
timeinthesystem (considering the10pallets plusthe16storage places in
Fig.27)andthatadirect implemen tation ofthealgorithm in[26]growsina
quadratic waywithrespecttothenumberofactiveproduction orders, thetime
toknowifasystem stateissafetakesabout2CPU{seconds intheworstcase.
Inorder toobtain more ecien tsolutions some approac hesarecurren tly
beingstudied trying tosolvetheproblem fornon-sequen tialRASusing directly
theinitial modelstructure. Asolution foraclassnon-sequen tialRAS, where
processes musthaveatree-lik estructure canbefound in[27].
6.2Beyondthestateoftheartfortheanalysis: Modelling with
objectnets
Theaimofthissection istoshowadieren tapproac hforthemodelling of
production systems. Itisbased ontheclearandintuitivecharacteristic thatina
37

production system, among other elemen ts,there aretwomain components.On
theonehand, thesystem architecture,whichcorresp ondstothedistribution of
thephysical elemen tsintheplant.Usually ,thisstructure israther static, and
noteasily changeable. Ontheother hand, thesetofprocessplans corresp onding
tothedieren ttypesofproducts tobeproduced inthesystem. These plans
canbeseenaslogical constrain tstobeimposedtothefree
owofparts inthe
system. Inmanycasesthesetofprocessplans canchange (newprocessplans are
required tofacedemands ofnewproducts, while others disapp ear,corresp onding
toproducts withverylowdemand). Therefore, doing aseparated consideration
ofthatelemen tswhen designing thesystem controlsoftwaremakeseasier to
adapt ittochanges inthesetofproducts thesystem isabletodealwith.
Awayofdoing thatwasproposedin[22],where thenalmodelwasa
coloured Petrinetinwhichthesystem architecture provided thenetskeleton
(thesetofplaces, transition andarcs) while thesetofpart
owrestrictions
imposedbytheprocessplans weremodelled bymeans ofthecolour domains of
places andtransitions andthefunctions labelling thearcs.Thishasalsobeenthe
approac hfollowedintheprevious sections. Inthissection adieren tapproac his
going tobeadopted. Itisbased ontheNets-within-Nets paradigm, asused, for
instance in[62],whichsupportamodelling ofsystems byPetrinetsfollowing
theparadigm ofObjectOrientedModelling. Applications oftheparadigm tothe
caseofmanufacturing systems canbeseenin[29,41,38].
Roughly speaking, oneofsuchmodelsiscomposedofaSystem Netandone
ormoreObjectNetswhichcanbeseenastokenobjectsofthesystem net.Both,
thesystem netandtheobjectnetsarePetrinets.Atokeninthesystem net
canbeeither areference toanobjectnetorablacktoken.Eachobjectnet
state represen tsthestate oftheelemen titmodels.Changes insuchstate can
beproduced byitsowninternal dynamics (autonomous occurrences), butcan
alsobeduetosome interactions withthesystem net.Ontheother hand, some
transitions inthesystem netcanin
uence theinternal state ofobjectnets,
butothers justmoveobjectnetsbetweendieren tlocations ofthesystem nets
(transportoccurrences).
Therefore, inthedenition ofanelemen taryobjectsystem, besides thesys-
temnet,thesetofobjectnetsandtheinitial marking, asetofinteractions must
beconsidered. Theinteractions dene howthesystem netandtheobjectnets
mustsynchronise theiractivities. These concepts directly apply forthemodelling
ofmanufacturing systems. Themodelofthephysical system willcorresp ondto
thesystem net,while eachpartwillbemodelled bymeans ofanobjectnet.
Theobjectiveofthissection isnottheintroduction oftheNets-within-Nets
paradigm, butjusttoshowthatitisverywelladapted tomodelproduction
systems. Todothat,letusapply ittothesameexample usedin[23,62].Figure 29
depicts amanufacturing cellcomposedoffourmachines, M1;M2;M3andM4
(eachonecanprocesstwoproducts atatime) andthree robotsR1,R2andR3
(eachonecanholdaproductatatime). There arethree loading points(named
I1;I2;I3)andthree unloading points(named O1;O2;O3).Theaction areafor
38

(M1,op1)
(M3,op1)(M2,op2)
(M4,op2)rootG1
(M4,op4) (M3,op3) rootG3(M2,op5) rootG2M1R1
R3I2
I3 O1O2O3
M2M3
M4R2I1
Fig.29.Amanufacturing cellcomposedoffourmachines andthree robots.Blackdots
represen tthepossibilit yofpart
owbetweentworesources.
robotR1isI1;O3;M1;M3,forrobotR2isI2;O2;M1;M2;M3;M4andfor
robotR3isM2;M4;I3;O1.
Everyrawproductarriving tothecellbelongs tooneofthethree following
types:W1,W2andW3.Thetypeofproductcharacterises theprocesstobe
made inthecellasfollows:1)arawproductoftypeW1istakenfromI1and,
onceithasbeenmanufactured, ismovedtoO1.Thesequences ofoperations
forthistypeareeither (M1;op1);(M2;op2)(execute op1inM1andthenop2
inM2)or(M3;op1);(M4;op2)(execute op1inM3andthenop2inM4).2)
arawproductoftypeW2istakenfromI2,manufactured inM2(operation
op5)andthenrouted towardsO2.3)arawproductoftypeW3istakenfrom
I3,manufactured inM4(operation op4)andtheninM3(operation op3)and,
nally ,routed towardsO3.Figure 30represen ts,bymeans ofdirected acyclic
graphs, thepossible operation sequences forsuchsetoftypesofparts.
(M1,op1)
(M3,op1)(M2,op2)
(M4,op2)rootW1
(M4,op4) (M3,op3) rootW3(M2,op5) rootW2
Fig.30.Three directed acyclic graphs specifying three dieren ttypesofparts tobe
processed inthecelldepicted inFig.29.
Analogously asintheexample in5.3,the(uncon trolled) PetrinetinFig.31
represen tsthepossible
owofparts intheconsidered system. Inorder tobe
39

abletoensure thateachpartinthesystem willbeproduced according toits
corresp onding processplan,somecontrolhastobeadded tothisskeleton model,
whichwillcorresp ondtothesystem netintheNets-within-Nets model(the
meaning ofplaces named W1r;W2r;W3randW1t;W2t;W3twillbeexplained
later).
R1M1
M1R1
R2M1
M1R2R1M3
M3R1
R2M3
M3R2
R2M4
M4R2
R3M4
M4R3R3M2R2M2
M2R2
M2R3pi_R1
pi_M1
pi_R2
pi_M2pi_M4pi_M3I1 O3
I2O2
I3O1pi_R3rc_R1rc_M3rc_M1
rc_R2
rc_M2rc_R3
rc_M4X
XXXX X
X
X X
XXX
X
XX
XX
X
XX
X
X XX
X
XXX
X
XX
XXXX
XXX
XX
XX
XX
XXX XX XW1r
W1t W3rW2t W2rW3t
K1
K2
K3
Fig.31.Petrinetmodelofthepart
owinthecelldepicted inFig.29.
Figure 32showsthree objectnetscorresp onding tothethree typesofparts
tobeproduced intheconsidered system (since inthisexample allthetransitions
intheobjectnetsmustinteract withthesystem, transition names inFig.32
arenotrepresen ted,justtheinteractions, forthesakeofclarity).Letusexplain
oneofthese models.ThePetrinetlabelledW2inFig.32corresp ondstoa
parttypeW2(infact,eachW2-typepartwillbemodelled byoneinstance
ofsuchnet).Thetokeninplace p21modelstherawmaterial foroneofsuch
40

products beforebeingloaded intothesystem. Thisstateischanged when that
rawmaterial entersthesystem. According tothesystem netinFig.31,this
isdonebythering oftransition I2.Therefore, ring such(system) transition
mustalsomakethetokeninp21tomovetoplace p22,whichisimposedbythe
interaction hi11i.Place p22modelsapartoftypeW2inside thesystem and
thatmustbeprocessed inM2.Thetransition joining p22andp23isusedto
modelthefactthatsuchpartentersM2,whichinthesystem netcorresp onds
totransition R2M2.Interaction hi13itakesthatintoaccoun t.Interaction hi15i
isusedtomovethepartfromM2totherobotR2.Finally ,interaction hi12iis
needed tomodeltheunloading ofsuchpartfromthesystem.
<i10>
<i15> <i11> <i13>
<i16> <i21> <i18>p1_2p1_3 p1_5
p1_1
p1_6
p2_4 p2_3 p2_2
p3_2 p3_3 p3_4 p3_5p2_1
p3_1 <i8>
W3)W2)W1)p1_4 <i13>
<i4> p1_8p1_9 p1_10
p1_7 <i14> 20t1_9<i22><i19> <i9> <i3>
<i12> p2_5
p3_6 <i6> <i2> p3_7<i1>
Fig.32.Three objectnetsmodelling thethree typesofparts tobeprocessed inthe
system inFig.29.Transition names arenotpresen ted,onlytheinteractions withthe
system net.
Inthesystem netinFig.31tokensinplace W1rareinstances ofobjectnet
W2inFig.32,andcorresp ondtorawparts oftypeW2(there areK2ofsuch
netinstances). Once terminated, these objectnetswillbeinplace W1t,which
\collects" terminated products oftypeW2.
Anyfurther renemen tinthemodeliseasytobedone. Letussupposealso
thedieren toperations eachmachineisabletodoneedtobeconsidered. For
instance, machineM3isabletocarry outoperations op1andop3.Figure 33(a)
showshowplacepiM3inthenetinFig.31could berened inorder toconsider
theoperations itisabletodo(capacit yofM3isnotrepresen tedforthesake
ofclarity).Ontheother hand, Fig.33(b) showshowtheplace p35oftheobject
netcorresp onding totheprocessing ofparts oftypeW3inFig.32could be
rened sothattheprocessplanitmodelstakesintoaccoun tthattheoperation
op3hastobedoneinM3forsuchparts (notice thattransitions M31andM32
corresp ondtotransp ortoccurrences).
HighlevelPetrinet-based formalisms provideveryuseful toolsforthemod-
elling, analysis andcontrolofcomplex concurren tsystems. However,thehigher
theabstraction leveltheformalism allows,themore complicated itsanalysis
becomes. Thisisthecaseofcoloured Petrinets,forinstance (structure-based
techniques arenotasgeneral asinthecaseofordinary Petrinets) andalsothe
41

R1M3
M3R1
R2M3
M3R2M3op1 M3op3xx
xx
x
xx
x
xxxx
M3_1<i6> <i24> p3_5 p3_5' <i8>
(a) (b)<i24>
M3_2<i23><i4>
<i6>
<i8>
<i10>
Fig.33.Arened modelformachineM3andhowitaects theobjectnetmodelling
W3parts.
caseforNets-within-Nets models.Itisalwayspossible toapply simulation tech-
niques, whichcangiveinsigh tofsome system behaviours allowingthesystem
designer toeasily testdieren tsystem congurations inorder tohaveargumen ts
tochooseoneoranother. InthecaseofNets-within-Nets, thetoolRenew [36]
isagoodenvironmen tformodelling andsimulation.
7Fromdiscrete eventmodelstowardshybrid models
Inthelastyearsanewkindofmodelsbased onPetrinetshasappeared. They
dier fromtheprevious onesinthattheyarenotdiscrete eventmodels,but
hybrid models.That is,thestateisnotonlyrepresen tedbydiscrete variables,
butitispartly relaxed intocontinuousvariables (intheextreme case,evenall
thevariables maybecontinuousinpiecewise continuoussystems).
These hybrid modelshavebeendened inmanydieren tways.Forexample,
(discrete) Petrinetsmaybecombined withdieren tialalgebraic equations asso-
ciating them either toplaces (Pr/T rPetrinets)[10]ortomarkings (DAEPetri
nets)[59].Another possibilit yistopartially relaxtheintegralit ycondition inthe
ring ofthetransitions, i.e.,continuiseor
uidify thering, asinHybrid Petri
nets[3,52].Thismeans thatthemarking oftheplaces around these transitions
isnolonger guaran teedtobeinteger (with thepossible exception ofself-lo op
arcs). When atotal
uidication isdonetheresult isaContinuousPetrinet[14,
51].Thiskindofhybrid modelscanbeusedbothtorepresen tsystems whose
\more reasonable view" ishybrid, orasanapproximation ofdiscrete systems
under hightrac conditions. Theideaofcontinuisation ofdiscrete modelsis
notnewandhasbeenemplo yedinmanydieren telds, forexample, popula-
tiondynamics [46],manufacturing systems [16,32],comm unication systems [21],
etc.Inthefollowingwewillconcen trate onHybrid Petrinets.Thisisnotthe
placetopresen tthestateoftheartoftheanalysis ofcontinuousandhybrid PNs
(seeforexample [45,51]),butjusttopointoutthat(partial)
uidication ofthe
42

Table2.Thefourcases forpossible continuisation ofatransition [52]
ClientsServersSeman ticsofthetransition
few(D) few(D) Discrete transition
few(D) many(C)Discrete transition (serversbecome implicit places)
many(C)few(D) Continuousnite serverseman tics(bounds toring speed)
many(C)many(C)Continuousinnite serversseman tics(speedisenabling-driv en)
untimed modeldoesnotpreserv eingeneral liveness properties ofthediscrete
model.
Intimed models,inorder toassociateatimeseman ticstothe
uidication
ofatransition, itshould betakenintoaccoun tthatatransition islikeanstation
inQueuing Networks,thus\themeeting point"ofclientsandservers.Assum-
ingthatthere maybemanyorfewofeachoneofthem,
uidication canbe
considered forclients,forserversorforboth.Table2represen tsthefourtheoret-
ically possible cases. Iftherewerefewclients,thetransition should beconsidered
discrete.
Basically ,theideaistousearstorder (ordeterministic) approximation of
thediscrete case[45],assuming thatthedelaysassociated tothering oftransi-
tionscanbeapproximated bytheirmean values. Asimilar approac hisused, for
example, in[6].Thismeans thatincontinuoustransitions thering isapproxi-
mated byacontinuous
ow,whose exact valuedependsontheseman ticsbeing
used. Thetwobasic seman ticsdened forcontinuoustransitions (seeTable2)
areinnite servers (orvariable speed)andniteservers (orconstant speed)[3,
45].Under nite serversseman tics,the
owoftihasjustanupperbound, [ti]
(thenumberofserverstimes thespeedofaserver).Thenf()[ti][ti](know-
ingthatatleastonetransition willbeinsaturation, thatis,itsutilisation will
beequal to1).Under innite serversseman tics,the
owthrough atimed tran-
sition tistheproductofthespeed,[t],andtheenabling ofthetransition, i.e.,
f[t]=[t]
enab(t;m)=[t]
minp2tfm[p]=Pre[p;t]g.
Itshould bepointedoutthatniteserverseman tics,equationally modelled by
bounding thering speedofcontinuised transitions, corresp ondsatconceptual
leveltoahybrid behaviour:
uidication isapplied onlytoclients,while servers
arekeptasdiscrete, i.e.,countedasanite number(thering speedisbounded
bytheproductofthespeedofaserverandthenumberofserversinthestation).
Ontheother hand, innite serversseman ticsreally relax clientsandservers,
beingthering speeddrivenbytheenabling degree ofthetransition. Inthis
case,evenifthe
uidication istotal, themodelishybrid inthesense thatitisa
piecewise linear system, inwhichswitchingamong theembedded linear systems
isnotexternally drivenasin[7],butinternally through theminim umoperators.
Thefollowingexample istakenfrom[2,3].Itmodelsastation inaMotorola
production system. Thisstation canproducetwokinds ofparts, c1andc2,
whose processing corresp ondstotheleftandrightpartofthegure, respectively.
Theparts arriveinbatchesof30000 and20000 parts attimes 0and1000. After
thearrivalofabach,parts aredownloaded intoabuer ataspeedof1partper
43

timeunit.Theprocessing doesnotstartimmediately ,butwaitsuntilatleast
500parts oftypec1or600parts oftypec2)havebeendownloaded. Atthat
pointsome setupisdoneonthemachine,whichtakes300timeunits forparts
c1and360forc2,beforetheprocessing starts. When alltheparts inthebatch
havebeenprocessed, themachineisliberated. Pieces areremovedinbatchesof
theinput size.
p11p1
t1
p2
p3t2
t3p4
p5d1=0
V2=1
d4=300
d5=0t4
t530000
500
500
V3=0 .5
30000p6
t6
p7
p8t7
t8p9
p10d6=1000
V7=1
d9=360
d10=0t9
t1020000
600
600
V8=0.33
20000
Fig.34.Hybrid Petrinetmodelling thebehaviour ofaproduction system.
Amodelofthissystem canbeseeninFig.34.Although itisadiscrete system,
themodelisnotdiscrete, buthybrid. Thetransitions represen tedasbarsinthe
gure arediscrete (theusual transitions inPetrinets), while those represen ted
asboxesarecontinuous. Analogously ,thecircles drawnwithasimple lineare
discrete, while those withthedouble linearecontinuous.
Inthisexample, since thesizeofthebatchesisquite large, thering of
transitions t2;t3;t7andt8canbeapproximated byacontinuous
ow.Thiskind
ofapproximation (when applicable) maysimplify thestudy ofthesystem. For
example, in[2]itisreported thatforthissystem thesimulation timereduces
from454sec.to0.15,thatis,itisdivided by3000!
Basic understanding ofhybrid systems, andanalysis andsynthesis techniques
needmuchimpro vementbeforetheycanbeeectiv elyused[51,52].Moreo ver,
itshould bepointedoutthatthere existsome\natural" limits totheproperties
thatcanbestudied. Forexample, mutual exclusion (inthemarking ofplaces orin
thering oftransitions), andthedierence betweenhome space andreversibilit y
44

cannot bestudied ingeneral [51].Additionally ,basic properties likedeadlo ck-
freeness oftheautonomous continuised modelisneither necessary ,norsucien t
forthediscrete case[51].However,theuseofhybrid modelsaspartial relaxations
ofdiscrete modelsisaquite newandpromising approac h.
References
1.M.Ajmone Marsan, G.Balbo,G.Conte,S.Donatelli, andG.Francesc hinis. Mod-
ellingwithGeneralizedStochastic PetriNets.Wiley,1995.
2.H.Alla,J.B.Cavaille,M.LeBail,andG.Bel.Lessystemesdeproduction parlot:
uneappro chediscret-con tinuutilisan tlesreseaux dePetriHybrides. InProc.of
ADPM'92 ,Paris,France, January1992.
3.H.AllaandR.David.Continuousandhybrid Petrinets. Journal ofCircuits,
Systems, andComputers ,8(1):159{188, 1998.
4.A.Avizenis andJ.P.Kelly.Faulttolerance bydesign diversity:Concepts and
experimen ts.Computer ,17(8):67{80, 1984.
5.J.M.Ayache,P.Azema, andM.Diaz. Observ er,aconcept foronlinedetection for
controlerrors inconcurren tsystems. InProc.9thIEEE Int.Sypm. Fault-Tolerant
Computing ,pages 79{86, Madison, WI,USA, June1992.
6.F.Balduzzi, A.Giua, andG.Menga. First-order hybrid Petrinets:Amodelfor
optimization andcontrol.IEEE Trans.onRoboticsandAutomation ,16(4):382{
399,2000.
7.A.Bemp orad, A.Giua, andC.Seatzu. Aniterativ ealgorithm fortheoptimal
controlofcontinuous-time switchedlinear systems. InM.Silva,A.Giua, andJ.M.
Colom, editors, WODES 2002: 6thWorkshop onDiscreteEvent Systems ,pages
335{340, Zaragoza, Spain, 2002. IEEE Computer Society.
8.J.Camp os,G.Chiola, J.M.Colom, andM.Silva.Properties andperformance
bounds fortimed markedgraphs. IEEE Trans.onCircuitsandSystems-I: Funda-
mental TheoryandApplic ations ,39(5):386{401, 1992.
9.J.Camp os,G.Chiola, andM.Silva.Ergodicityandthroughput bounds ofPetrinet
withunique consisten tring countvector. IEEE Trans.onSoftwar eEngine ering,
17(2):117{125, 1991.
10.R.Champagnat, R.Valette, J.C.Hochon,andH.Pingaud. Modeling, simula-
tionandanalysis ofbatchproduction systems. DiscreteEvent Dynamic Systems:
TheoryandApplic ation,11(1/2):119{136, 2001.
11.C.Chaouiy aandY.Dallery .Petrinetmodelsofpullcontrolsystems forassem bly
manufacturing systems. InProcs.ofthe2ndInt.Workshop onManufacturing and
PetriNets,ICATPN,pages 85{103, Toulouse, France, 1997.
12.P.Chretienne, E.G.Coman, J.K.Lengstra, andZ.Liu,editors. Wiley,1995.
13.J.M.Colom, M.Silva,andJ.L.Villarro el.Onsoftwareimplemen tation ofPetri
netsandcolored Petrinetsusing high-lev elconcurren tlanguages. InProc.7thEu-
ropeanWorkshop onApplic ationandTheoryofPetriNets,pages 207{241, Oxford,
England, July1986.
14.R.DavidandH.Alla.ContinuousPetri nets.InProc.ofthe8thEuropeanWork-
shoponApplic ationandTheoryofPetriNets,pages 275{294, Zaragoza, Spain,
1987.
15.R.DavidandH.Alla.PetriNetsandGrafcet.Prentice-Hall, 1992.
16.R.David,X.Xie,andY.Dallery .Properties ofcontinuousmodelsoftransfer lines
withunreliable machines andnite buers. IMAJournal ofMathematics Applie d
inBusiness andIndustry ,6:281{308, 1990.
45

17.A.Desro chersandR.Y.Al-Jaar. Applic ations ofPetriNetsinManufacturing
Systems .IEEE Press, 1994.
18.AlanA.Desro chersandRobertY.Al-Jaar. Applic ations OfPetriNetsInMan-
ufacturing Systems. Modeling, Control,AndPerformanc eAnalysis .IEEE Press,
1995.
19.M.Diaz, G.Juanole, andJ.P.Courtiat. Observ er|aconcept forformal on-
linevalidation ofdistributes systems. IEEE Trans.onSoftwar eEngine ering,
20(12):900{913, 1994.
20.E.W.Dijkstra. Cooperating sequen tialprocesses. InF.Genuys,editor, Program-
mingLanguages .Academic Press, 1968.
21.E.I.ElwadiandD.Mitra. Statistical multiplexing withlosspriorities inrate-based
congestion controlofhigh-sp eednetworks. IEEE Transactions onCommunic a-
tions,42(11):2989{3002, 1994.
22.J.EzpeletaandJ.M.Colom. Automatic synthesis ofcolored Petrinetsforthe
controlofFMS. IEEE Transactions onRoboticsandAutomation ,13(3):327{337,
June1997.
23.J.Ezpeleta, J.M.Colom, andJ.Martnez.APetrinetbased deadlo ckprevention
policyfor
exible manufacturing systems. IEEE Trans.onRoboticsandAutoma-
tion,11(2):173{184, April 1995.
24.J.EzpeletaandJ.Martnez. Formal specication andvalidation inproduction
plants.InProceedingsofthe3th.International Confer enceonComputer Integrated
Manufacturing ,pages 64{73, Rensselaer Polytec hnicInstitute, Troy(New York),
May1992. IMACS.
25.J.EzpeletaandL.Recalde. Adeadlo ckavoidance approac hfornon-sequen tial
resource allocation systems. IEEE Trans.onSystems, Man,andCybernetics ,2004.
Accepted.
26.J.Ezpeleta, F.Tricas, F.Garca-Valles,andJ.M.Colom. ABanker'ssolution
fordeadlo ckavoidance inFMSwithrouting
exibilit yandmulti{resource states.
IEEE Transactions onRoboticsandAutomation ,18(4):621{625, August 2002.
27.J.EzpeletaandR.Valk.Apolynomial solution fordeadlo ckavoidance inassem-
blysystems modelled withpetrinets. InProceedings oftheMultic onferenceon
Computational Engine eringinSystems Applic ations (CESA2003) ,pages 1{8,Lille
(France), July,9{112003.
28.M.P.Fanti,B.Maione, andB.Turchiano. Design ofsupervisors toavoiddeadlo ck
in
exible assem blysystems. TheInternational Journal ofFlexible Manufacturing
Systems ,14:157{175, 2002.
29.B.Farwer,D.Moldt, andF.Garc-Valles.Anapproac htomodelling fmswith
dynamic objectpetrinets. InProceedingsoftheIEEE International Confer ence
onSystems, ManandCybernetics ,Hammamet (Tunisia), Octob er2002.
30.J.C.Gentina,J.P.Bourey ,andM.Kapusta. Coloured adaptiv estructured Petri
nets.Computer-Inte gratedManufacturing ,1(1):39{47, 1988.
31.J.C.Gentina,J.P.Bourey ,andM.Kapusta. Coloured adaptiv estructured Petri
nets(II).Computer-Inte gratedManufacturing ,1(2):103{109, 1988.
32.S.B.Gersh win.Manufacturing Systems Engine ering.Prentice-Hall, 1994.
33.A.N.Habermann. Preventionofsystems deadlo cks.Communic ations oftheACM,
12(7):373{385, July1969.
34.C.Hanen andA.Munier. Cyclic scheduling problems: Anoverview. InChretienne
etal.[12].
35.YiSheng Huang, MuDer Jeng, andXiaolan Xie.Adeadlo ckpreventionpolicyfor

exible manufacturing systems using siphons. InProc.ofthe2001IEEE Inter-
46

national Confer enceonRoboticsandAutomation ,pages 541{546, Seoul (Korea),
May2001.
36.O.Kummer andF.Wienberg.Renew. thereference networkshop. PetriNet
Newsletter ,(56):12{16, 1999.
37.N.G.LevesonandJ.L.Stolzy .Safetyanalysis using Petrinets.IEEE Trans.on
Softwar eEngine ering,13(3):386{397, 1987.
38.E.Lopez-Mellado andJ.G.Morales-Mon telongo. Agent-based distributed con-
trollers fordiscrete manufacturing systems. InProceedingsoftheMultic onference
onComputational Engine eringinSystems Applic ations (CESA2003) ,pages 1{7,
Lille(France), July,9{112003.
39.J.Martnez,P.Muro, andM.Silva.Modeling, validation andsoftwareimplemen ta-
tionofproduction systems using highlevelPetrinets.InM.SilvaandT.Murata,
editors, InvitedSessions: PetriNetsandFlexible Manufacturing. IEEE Int.Conf.
onRoboticsandAutomation ,pages 1180{1185, Raleigh, NC,USA, April 1987.
40.J.Martnez,P.Muro, M.Silva,S.F.Smith, andJ.L.Villarro el.Merging arti-
cialintelligence techniques andPetrinetsforrealtimescheduling andcontrolof
production systems. InR.Huberetal.,editors, Articial IntelligenceinScientic
Computation ,pages 307{313. ScienticPublishing Co.,1989.
41.D.Moldt andJ.Ezpeleta. Aproposalfor
exible testing ofdeadlo ckcontrol
strategies inresource allocation systems. InProceedings oftheInternational
Confer enceonComputational IntelligenceforModellingControlandAutomation
(CIMCA'03) ,pages 586{595, Vienna, Austria, February 2003.
42.T.Murata. Petrinets:Properties, analysis andapplications. Proceedingsofthe
IEEE,77(4):541{580, 1989.
43.J.ParkandS.Reveliotis. Deadlo ckavoidance insequen tialresource allocation sys-
temswithmultiple resource acquisitions and
exible routings. IEEE Transactions
onAutomatic Control,46(10):1572{1583, Octob er2001.
44.J.M.Proth andX.Xie.PetriNets.AToolforDesign andManagement ofMan-
ufacturing Systems .Wiley,1996.
45.L.Recalde andM.Silva.Petri Nets
uidication revisited: Seman ticsandsteady
state. APII-JESA ,35(4):435{449, 2001.
46.E.Rensha w.Asurveyofstepping-stone modelsinpopulation dynamics. Adv.
Appl.Prob.,18:581{627, 1986.
47.E.Roszk owskaandR.Wojcik. Problems ofprocess
owfeasibilit yinFAS.In
K.Leivisk a,editor, IFACCIMinProcessandmanufacturing Industries ,pages
115{120, Espoo,Finland, 1992. Oxford: Pergamon Press.
48.M.Silva.LasRedesdePetri: enlaAutomaticaylaInform atica.AC,1985.
49.M.Silva.Interleavingfunctional andperformance structural analysis ofnetmodels.
InM.Ajmone Marsan, editor, Applic ationandTheoryofPetriNets1993,volume
691ofLectureNotes inComputer Scienc e,pages 17{23. Springer, 1993.
50.M.Silva.Introducing Petrinets.InPracticeofPetriNetsinManufacturing ,pages
1{62. Chapman &Hall,1993.
51.M.SilvaandL.Recalde. Petrinetsandintegralit yrelaxations: Aviewofcontinuous
Petrinets.IEEE Trans.onSystems, Man,andCybernetics ,32(4):314{327, 2002.
52.M.SilvaandL.Recalde. On
uidication ofPetrinetmodels:fromdiscrete to
hybrid andcontinuousmodels. InIFACConfer enceonAnalysis andDesign of
Hybrid Systems, ADHS03 ,pages 9{20, Saint-Malo, France, June2003.
53.M.SilvaandE.Teruel. Asystems theory perspectiveofdiscrete eventdynamic
systems: ThePetrinetparadigm. InP.Borne, J.C.Gentina,E.Craye,and
S.ElKhattabi, editors, Symposium onDiscreteEvents andManufacturing Sys-
tems.CESA '96IMACSMultic onference,pages 1{12, Lille, France, July1996.
47

54.M.SilvaandE.Teruel. Petrinetsforthedesign andoperation ofmanufacturing
systems. EuropeanJournal ofControl,3(3):182{199, 1997.
55.M.Silva,E.Teruel, andJ.M.Colom. Linear algebraic andlinear programming
techniques fortheanalysis ofnetsystems. InG.Rozen bergandW.Reisig, editors,
LecturesinPetriNets.I:Basic Models,volume 1491ofLectureNotes inComputer
Scienc e,pages 309{373. Springer, 1998.
56.M.Silva,E.Teruel, R.Valette, andH.Pingaud. Petrinetsandproduction systems.
InG.Rozen bergandW.Reisig, editors, LecturesinPetriNets.II:Applic ations ,
volume 1492ofLectureNotes inComputer Scienc e,pages 85{124. Springer, 1998.
57.E.Teruel, J.M.Colom, andM.Silva.Choice-free Petrinets: Amodelforde-
terministic concurren tsystems withbulkservices andarrivals.IEEE Trans.on
Systems, Man,andCybernetics ,27(1):73{83, 1997.
58.F.Tricas, F.Garca-Valles,J.M.Colom, andJ.Ezpeleta. Aniterativ emetho dfor
deadlo ckpreventioninFMS. InR.BoelandG.Stremersc h,editors, DiscreteEvent
Systems: Analysis andControl.Proc.oftheWorkshop OnDiscreteEvent Systems
2000,pages 139{148, Ghent,Belgium, Aug2000. KluwerAcademic Publishers.
59.C.Valentin-Roubinet. Modeling ofhybrid systems: DAEsupervised byPetrinets.
theexample ofagasstorage. InProc.ofADPM'98 ,pages 142{149, Reims, France,
March1998.
60.R.Valette andM.Courv oisier. Petrinetsandarticial intelligence. InR.Zurawski
andT.Dillon, editors, ModernToolsforManufacturing Systems ,pages 385{405.
Elsevier, 1993.
61.R.Valette, M.Courv oisier, J.M.Bigou, andJ.Albuk erque. APetri netsbased
programmable logiccontroller. InIFIP1stInt.Conf. onComputer Applic ations
inProduction andEngine ering,Amsterdam, Holland, April 1983.
62.R.Valk.Petrinetsastokenobjects-anintroduction toelemen taryobjectnets.
LectureNotes inComputer Scienc e:19thInt.Conf. onApplic ationandTheoryof
PetriNets,ICATPN'98, Lisbon,Portugal, June1998,1420:1{25, June1998.
63.S.VelillaandM.Silva.Thespy:Amechanism forsafeimplemen tation ofhighly
concurren tsystems. InRealTimeProgramming 1988, 15thIFAC/IFIP Workshop ,
pages 95{102, Valencia, Spain, May1988. Pergamon.
64.J.L.Villarro el,J.Martnez,andM.Silva.GRAMAN: Agraphic system formanu-
facturing system design. InS.Tzafestas, A.Eisinberg,andL.Caroten uto,editors,
IMACSSymp. onSystem ModellingandSimulation ,pages 311{316. Elsevier, 1988.
65.N.Viswanadham andY.Narahari. Performanc eModeling ofAutomate dManu-
facturing Systems .Prentice-Hall, 1992.
66.Mengc huZhou andKurapati Venkatesh. Modeling, Simulation, andControlof
Flexible Manufacturing Systems :APetriNetApproach,volume 6ofSeries in
Intelligent ControlandIntelligent Automation .WorldScientic,1999.
48
View publication statsView publication stats