Tutorial on Bounds for PN's

Javier Campos

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 ...

Informations

• Publié par: Curah
• Nombre de lectures: 21
• Langue: English

Extrait

Properties and Bounds on P/T Nets Javier Campos Universidad de Zaragoza (Spain)

Tutorial of PNPM’99 – PAPM’99 – NSMC’99

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 PNPM’99 – PAPM’99 – NSMC’99, 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 PNPM’99 – PAPM’99 – NSMC’99, 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 PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999

Javier Campos p. 4

Introducing ideas: MG’s case (1)

p1 t1  p2

p3

t2 t3

p4 t4 generally distributed service times (random variablesX i with  n  m ae s     [t    j ]   )        p5 we assumeinfinite-server semantics

exact cycle time (random variable):X = X 1 + max{X 2 ,X 3 } + X 4        average cycle time: G = s[t 1 ] + E[max{X 2 ,X 3 }] + s[t 4 ]        but (non-negative variables): X 2 ,X 3 £ max{X 2 ,X 3 } £ X 2 + X 3        therefore: s[t 1 ] + max{s[t 2 ],s[t 3 ]} + s[t 4 ]  ££ G s[t 1 ] + s[t 2 ] + s[t 3 ] + s[t 4 ]       

Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999p. 5

Introducing ideas: MG’s case (2)

Thus, the lower bound for the average cycle time is computed looking for the slowest circuit

æ  å s[t i ] ö 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 PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999p. 6

Introducing ideas: MG’s case (3)

(s is the vector of    average service times)

• Computation: G ³ maximumy × Pre × s subject toy × C = 0   y × m 0 = 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 PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999p. 7

Introducing ideas: MG’s case (4)

•Even if naïf, the bounds are tight! • Lower bound for the average cycle time

max{s[t 2 ],s[t 3 ]} £ E[max{X 2 ,X 3 }]        –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 PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999p. 8

Introducing ideas: MG’s case (5)

ï ìm   a  1with probability -e 2 X m , s ( a ) ï î = í     m ç æ è     a+ 1 -a e ö  ø ÷   with probability e     e   = m 2 ( m 1 2 - (1 a - ) 2 a ) +s 2        (0 £a£ 1)   

E [ X m , s ( a ) ] =m ; Var [ X m , s ( a ) ] =s 2       

max ( m , m )   ¢  

lim E [ max ( X m , s ( a ),X m¢ , s¢ ( a ) ) ] = a® 1      E [ X m , s ( a ) + X m    ¢ , s¢ ( a ) ] =m+m    ¢ , "  0 £a< 1     

they behave “as deterministic” for the ‘max’and ‘+’operators in the limit (a®1)

Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999p. 9

Introducing ideas: MG’s 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 PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999p. 10

Introducing ideas: MG’s case (7)

0 wit X i m ( e ) ï = ì    1h probability -e i   ï î í e     m i with probability e i      (0 <e< 1)   

m 2 E é X i ù ë m ( e ) û  =m ; E  é ë  X i m ( e ) 2 ù  = û  e i       

IfX j = X s j   [ - t j 1 ] ( e ), " t j Î T for varying (decreasing) values of, then e :

      

E[max(X i ,X j )] = s[t i ] + s[t j ] + o( e )

Properties and Bounds on P/T Nets Javier Campos Tutorial of PNPM’99 – PAPM’99 – NSMC’99, Zaragoza (Spain), Sep. 6-10, 1999p. 11