e2 e3 e4
e5
e6
time
17
Comparison with a CVDS Trajectory
Discrete state
dx/dt = f(x,u,t)
time Hybrid System: each state can hide CVDS behavior 18
Modeling Ingredients
• Discrete States: combinatorial explosion • Stochastic Effects: unavoidable uncertainty • Continuous time and performance measure • Dynamical: • Hierarchical: • Computational vs conceptual
Untimed Timed
Finite State
Machines & Petri Nets
Finitely Recursive Processes
Min-Max Algebra
Generalized Semi-Markov
Processes
GOAL: Finite representation. Qualitative properties, Quantitative Performance
New
Generate
state
lifetime of
new event
Place the event in the future event list
Search for next event to occur
Transition to next state
22
Ingredients and Models
• Weeks if not days to run a 3D extrusion simulation with the finite element methodology.
6
What can we do?
• Most of the above systems are discrete event dynamic systems (DEDS).
(yes) yes
no
Petri Nets
graphical yes
Language &
Processes
no yes
yes not really
yes
no
yes
no
yes
no
GSMP
yes yes yes yes yes yes
23
Model of DEDS
Logical Algebraic Performance
• Simulation-based optimization
1
How long to simulate a manufacturing system?
• 30 minutes to accurate evaluate a scheduling strategy using Monte Carlo simulations
Clock Mechanism (a two dimensional array of numbers)
cn() = the nth lifetime of the event
t(n) = the time of the nth occurrence of the event
Event type
September, 2010 Tsinghua University, Beijing, CHINA
Discrete Event Dynamic Systems — An Overview —
TOPICS:
• What are DEDS? • Models of DEDS • Tools for DEDS • Future Directions for DEDS
19
Mathematical Specification
m
• State Space Approach:
–X –A – G(x)
the state space, a finite set, xX. state: # in queue.
Event set, finite A.e.g. arrival(a), departure(d).
co.
• • The pervasive nature of DEDS in modern civilization
15
Nature of DEDS
• A set of tasks or jobs: parts to be manufactured,
messages to be transmitted, et HOLDING TIMES are deterministic/random EVENTS triggers state transition TRAJECTORY defined by (state, holding time) sequence
24
Performance Design & Evaluation
• Building Models • Validation and analysis • Evaluating the model • Optimization and tuning
– Score: # of occurrences of event types in a string
– Trace: sequence of state, event pair
20
Mathematical Specification (contd.)
Introduction of “TIME” for quantitative performance analysis purposes
• Thousands of hundreds of possible scheduling strategies.
2
How long to simulate a computer network?
• 1.5 hours to run a single simulation of the performance of a congestion control strategy in a 12000-node network.
• A set of resources: machines, AGVs, nodal CPUs,
communication links and subnetworks, etc
• Routing of job among resources: production
plans, virtual circuits, etc
• WWW Pages: /~ho/CRCD or DEDS with links to Boston University and U. of Mass. Amherst
10
What are Continuous Variable Dynamic Systems
What is complex system?
• An engineering viewpoint: A system is complex if the only way to accurately describe the system is to build an electronic copy, i.e., to run a simulation.
FSM (Markov Chains)
STATE
yes
EVENT input
FEASIBLE EVENT
yes
TIME
no
TRANSITION yes
RANDOMNESS
no/yes
Queuing Network
yes yes
yes
yes yes
yes
Min-Max Algebra
yes yes
yes
• Scheduling of jobs as they compete for resources: queues and event timing sequences
16
A Typical DEDS Trajectory
Discrete state x3
x4
x2 x5
x1 e1
Holding time
• Models of DEDS • Simulate DEDS • Evaluate the performance of DEDS • Optimize the performance of DEDS
7
Discrete Event Dynamic Systems — Lecture #1 —
by Y.C. Ho, Q.C. Zhao, Q.S. Jia
Enabled event set in x, G(x)A, if x≥1, G(x)={a,d}; if x=0, G(x)={a}.
–f
State transition function XxG(x)->X. Could write down
f∈{+1;0;-1}, because these are transitions possible.
9
Resources
• Books: – Y.C. Ho, Q.C. Zhao, Q.S. Jia, Ordinal Optimization: Soft Optimization for Hard Problems, New York, NY: Springer, 2007. – C. Cassandras & S Lafortune, Discrete Event Systems, Kluwer 1999, 2008 – Y.C. Ho, DEDS Analyzing Performance and Complexity in the Modern World, IEEE Press book, 1992