- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
• 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.
• 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
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).
cn()
t(1)
t(2)
t(n-1) t(n)
time
21
Time Evolution of a DEDS
One event delay
Event enabling
Life time
x G(x)
generation
Minimum of* State
lifetimes
transition
cn()
Simulation of a DEDS
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
• 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: www.hrl.harvard.edu/~ho/CRCD or DEDS with links to Boston University and U. of Mass. Amherst
10
Leabharlann Baidu
What are Continuous Variable Dynamic Systems
• Thousands of simulations are needed for accurate evaluation.
• Thousands of hundreds of control strategies to compare.
3
How long to simulate a turbine blade in the aircraft engine?
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
– 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
• Simulation-based optimization
1
How long to simulate a manufacturing system?
• 30 minutes to accurate evaluate a scheduling strategy using Monte Carlo simulations
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.
(CVDS)?
11
12
What are Discrete Event Dynamic Systems (DEDS)?
13
An Airport
14
More Examples of DEDS
• Manufacturing Automation - a SC Fab • Communication Network - the Internet • Military C3I systems • Traffic - land, sea, air • Paper processing bureaucracy - insurance
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
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
STATES are piecewise
constant HOLDING TIMES are deterministic/random EVENTS triggers state transition TRAJECTORY defined by (state, holding time) sequence
(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
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
• 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).
• Input/output Approach:
– String: sequence of events s =bg....
– Language: all possible event sequences in a DEDS
– Operations: defined on strings,e.g., “shuffle”
STATE:
EVENT: EVENT FEASIBILITY: STATE TRANSITION: TIMING: RANDOMNESS:
not inherent for in/out, not necessarily complete
fundamental, instantaneous, marks state transition basic to control basic to dynamics essential for performance evaluation facts of life
24
Performance Design & Evaluation
• Building Models • Validation and analysis • Evaluating the model • Optimization and tuning
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, etc
Untimed Timed
Finite State
Machines & Petri Nets
Finitely Recursive Processes
Min-Max Algebra
Generalized Semi-Markov
Processes
GOAL: Finite representation. Qualitative properties, Quantitative Performance
• Discrete States: combinatorial explosion • Stochastic Effects: unavoidable uncertainty • Continuous time and performance measure • Dynamical: • Hierarchical: • Computational vs conceptual
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
• 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
