Tutorial on Bounds for PN's

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