Tutorial on Bounds for PN
36 Pages
English
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Tutorial on Bounds for PN's

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer
36 Pages
English

Description

Properties and Bounds on P/T NetsJavier CamposUniversidad de Zaragoza (Spain)Tutorial of PNPM’99 – PAPM’99 – NSMC’99Zaragoza (Spain), September 6-10, 1999Preliminary comments (1)• Interest of bounding techniques– preliminary phases of design• many parametersexactare not known accuracysolutionaccurately• quick evaluation andboundsrejection of thoseclearly badcomplexityProperties and Bounds on P/T Nets Javier CamposTutorial of PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999 p. 2Preliminary comments (2)• Net-driven solution technique– stressing the intimate relationship betweenqualitative and quantitative aspects of PN’s– structure theory of net modelsefficient computation techniquesProperties and Bounds on P/T Nets Javier CamposTutorial of PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999 p. 3Outline• Introducing the ideas: Marked Graphs case• Generalization: use of visit ratios• Improvements of the bounds• A general linear programming statementProperties and Bounds on P/T Nets Javier CamposTutorial of PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999 p. 4Introducing ideas: MG’s case (1)t2 p4p2p1 t1 t4 generally distributed service times (random variables X with mean ) s [t ] it3 j p5p3 we assume infinite-server semanticsexact cycle time (random variable): X = X + max{X , X }+ X 1 2 3 4 average cycle time: G = s [t ]+ E[max{X , X }]+ s [t ] 1 2 3 4 but (non-negative variables): X ...

Subjects

Informations

Published by
Reads 19
Language English

Exrait

Properties and Bounds on P/T Nets Javier Campos Universidad de Zaragoza (Spain)
Tutorial of PNPM99 – PAPM99 – NSMC99
Zaragoza (Spain), September 6-10, 1999
Preliminary comments (1)
• Interest of bounding techniques –preliminary phases of design • many parameters are not known accurately • quick evaluation and rejection of those clearly bad
accuracy
bounds
Properties and Bounds on P/T Nets Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999
exact solution
complexity
Javier Campos p. 2
Preliminary comments (2)
Net-driven solution technique –stressing the intimate relationship between qualitative and quantitative aspects of PN’s –structure theory of net models
efficient computation techniques
Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999p. 3
Outline
Introducing the ideas: Marked Graphs case Generalization: use of visit ratios Improvements of the bounds A general linear programming statement
Properties and Bounds on P/T Nets Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999
Javier Campos p. 4
Introducing ideas: MGs case (1)
p1 t1 p2
p3
t2 t3
p4 t4generally distributed service times (random variablesXiwith  n  m aes  [t  j] )       p5we assumeinfinite-server semantics
exact cycle time (random variable):X=X1+max{X2,X3}+X4     average cycle time:G =s[t1]+E[max{X2,X3}]+s[t4]       but (non-negative variables):X2,X3£max{X2,X3}£X2+X3     therefore:s[t1]+max{s[t2],s[t3]}+s[t4] ££ Gs[t1]+s[t2]+s[t3]+s[t4]       
Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999p. 5
Introducing ideas: MGs case (2)
Thus, the lower bound for the average cycle time is computed looking for the slowest circuit
æ ås[ti]ö G ³maxçt iÎC÷ CÎ{circuitsç in# tokensC÷ of the net}è ø       
Interpretation: an MG may be built synchronising circuits, so we look for the bottleneck
Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999p. 6
Introducing ideas: MGs case (3)
(s is the vector of   average service times)
• Computation:G ³maximumy×Pre×s subject toy×C=0  y×m0=1 y³0     (the proof of this comes later for a more general case)
solving a linear programming problem (polynomial complexityon the net size)
Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999p. 7
Introducing ideas: MGs case (4)
Even if naïf, the bounds are tight! • Lower bound for the average cycle time
max{s[t2],s[t3]}£E[max{X2,X3}]       –it is exact for deterministic timing –it cannot be improved using only mean values of r.v. (it is reached in a limit case for a family of random variables with arbitrary means and variances)
Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999p. 8
Introducing ideas: MGs case (5)
ïìm a 1with probability-e2 Xm,s(a)ïî=í  mçæè  a+1-aeö ø÷ with probabilitye  e =m2(m12-(1a-)2a)+s2     (0£a£1)   
E[Xm,s(a)]=m; Var[Xm,s(a)]=s2     
max(m,m)  ¢ 
lim E[max(Xm,s(a),Xm¢,s¢(a))]= a®1     E[Xm,s(a)+Xm  ¢,s¢(a)]=m+m  ¢," 0£a<1     
they behave “as deterministic” for the ‘max’and ‘+’operators in the limit (1)
Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999p. 9
Introducing ideas: MGs case (6)
• Upper bound for the average cycle time
G £ ås[t] tÎT       
 
–it cannot be improved for 1–live MG’s using only mean values of r.v. (it is reached in a limit case for a family of random variables with arbitrary means)
Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999p. 10
Introducing ideas: MGs case (7)
0 wit Xim(e)ï=ì  1h probability-ei ïîíe  miwith probabilityei     (0<e<1)   
m2 EéXiù ëm(e)û =m; E éë Xim(e)2ù =û ei     
IfXj=Xsj [-tj1](e),"tjÎT for varying (decreasing) values of, thene:
      
E[max(Xi,Xj)]=s[ti]+s[tj]+o(e)
Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM99 – PAPM99 – NSMC99, Zaragoza (Spain), Sep. 6-10, 1999p. 11