Corporate Technology - Combinatorial Optimization at Work

Transcrição

Corporate Technology
Mathematical Optimization at Siemens
Michael Hofmeister
Siemens AG Munich, Corporate Technology
Copyright © Siemens AG 2008. Alle Rechte vorbehalten.
Outline
Siemens Company – a short introduction
Mathematics at Siemens Corporate Technology
Assembly of printed circuit boards
Water supply network planning
The internet of things
Outlook
Seite 2
07.07.2009
Michael Hofmeister
© Siemens AG, Corporate Technology
Siemens Company
Siemens' innovations have changed the world
Industry
Energy
Healthcare
Seite 3
07.07.2009
From the first electronic controls –
to fully automated factories
From the invention of the dynamo –
to the world's most efficient gas
turbines
From the first interior view of the body –
to full-body 3D scans
Michael Hofmeister
Logarithmic scale
Siemens Company
Milestones for Three Centuries
Innovation for:
Information and Communication
Energy
Industry Automation
Mobility
Healthcare
Lighting Technology
Household Appliance
1965: Integrated
circuits
1980: EWSD (digital
switching technology
1988: Megabit chip
2003: Maglev in
Shanghai
2004: Bio-lab on
chip
2005: Electronic
wedge brake
1993:
Electron
Microscope
1881: Electrical
streetcar
Employees in 2005:
461,000
2000: Piezo Injection
for diesel engines
1962: Thyristor
for energy
Sales in 2005:
75,445
Billion Euro
1974: Computer
tomography scanner
1881: Telephone
switchboard
1879: Electrical
railway
1935: Coax cable
1924: Traffic light
1953: Very clean silicon
1958: Heart
pacemaker
1984: Hicom
telephone
switchboard
1866: Dynamo
1905: Tantalum lamp
1847: Telegraph
1847: Werner
von Siemens
founded the
company
Seite 4
1905: First R&D
laboratory
07.07.2009
2005: Home
entertainment
1931: „Hot air shower“
(hair-dryer)
1985: High speed
train ICE (300 km/h)
2000: syngo GUI
2004: Full length
MR tomography
2004: 64 lines computer
tomography scanner
1906: Vacuum cleaner
1959: Transistor based
universal computer
1994: High temperature
fuel cell
1998: Terabit switch
1998: Most efficient
Power plant
Michael Hofmeister
Siemens Company
Almost 50.000 R&D Employees at 150 Locations
Issaquah
Sacramento
Chatham Peterboroug
Berkeley
h
Tilbury London
Drummondville
Mountain View Concord
Auburn
Danvers
San José Hoffman
Hills
Santa Clara
Burlington
San Diego
n
Piscataway
EstatesPittsburgh Princeton
ArlingtonJohnson City
Newport News
Austin
Norcross Knoxville
Guadalajara
Lake Mary
Orlando
Breda
Hengelo Mülheim
Amsterdam
Pandrup Göteborg
Oslo
Helsinki
Bracknell
St. Petersburg
Eynsham
Berlin
Moskau
Roke Manor
Dresden
Erlangen-Nürnberg
Brüssel
Karlsruhe
Regensburg Prag
Paris
Zürich
Toulouse
Budapest Bratislava
Wien
Madrid
München Zagreb Istanbul Timisoara
Porto
Athen
Lissabon
Graz
Netanya
Zaragoza
Mailand Linz
Neu-Delhi
Tel Aviv
Salzburg
Sophia
Treviso
Antipolis
Goa
Bombay
Nanjing Shanghai
Hong Kong
Chengdu
Sao Paulo
Curitiba
Taipei
Singapur
Pretoria
Melbourne
Buenos Aires
07.07.2009
Tokio
Kawasaki
Yokohama
Kakegaw
a
Bangalore
Penang
Bogota
Seite 5
Xi‘an
Changchun
Peking
Seoul
Tianjin
Ichon
Michael Hofmeister
Sydney
Innovation Network of the Integrated Company
Customers
Sectors / Divisions
Chief Technology
Officer (CTO)
Industry
Chief Technology
Office (CT O)
Direct support
of CTO
Energy
Healthcare
Regions
Evaluation of
innovation strategy
Technology based
support of synergies
assurance of
innovative power
Evaluation of
technologies
Guidance
Siemens IT Solutions and Services (SIS)
Siemens Financial Services (SFS)
Corporate Research and
Technologies (CT T)
Global Technology Fields with multiple impact
Pictures of the Future
Accelerators for new business opportunities
Corporate Intellectual Property
and Functions (CT I)
Intellectual Property Services & Strategy
Standardization, Environmental Affairs
Global Information Research
Corporate Technology (CT)
Seite 6
07.07.2009
Michael Hofmeister
Modeling, Simulation, Optimization
Smart Decision Support
Autonomous Learning,
Prognosis and Diagnosis
Value Chain Optimization
ng
ni
r
a
Le
m
te
s
Sy
s
Vi
rt
ua
lD
es
ig
n
Digital Product
Mathematical Engineering
Control Systems
Seite 7
07.07.2009
Discrete Optimization
Localization Technologies
Michael Hofmeister
Research and Innovation
The Mindset
Mathematics evolves its impact
most effectively if it appears as
a PARTNER together with other
sciences and technologies
Seite 8
07.07.2009
Michael Hofmeister
The Mindset
Giants …
• Bug Fixing
• GUI
• 100k LOC
• Middleware
• Incorrect inputs
Dwarfs and elves
• Commissioning
• Modeling
• External systems
• Theorems and proofs
• Algorithms
• Interfaces
• Data base
• Software Engineering
• Operating system
Seite 9
07.07.2009
… and Dragons
Michael Hofmeister
From Modeling to Application
Modeling
Realization
Integration
Seite 10
07.07.2009
Michael Hofmeister
Assembly of Printed Circuit Boards
Optimizing the automaton
Distribute components to all
stations in order to achieve a
well-balanced line
Select and configure
nozzles for each head
such that the number
of placement cycles
is minimized
Comp. Types
Nozzle Types
Arrange component
feeders for fast picking
sequences
Construct short paths on
the board for each head
for fast placement
Seite 11
07.07.2009
Michael Hofmeister
Coherence in Systems Hierarchy
Factory
Coherence of Models ÍÎ Semantic Coupling
Seite 12
07.07.2009

Layout
Dispatching and scheduling
Staff assignment
Material supply
Maintenance planning
Production Lines
Matched line configuration of machines
Optimum component feed along the line
Trade-off between set-up times and processing
times
Machine Level
Timing and spatial constraints of single
machines
Necessary resources behavior
Availability
Michael Hofmeister
Nozzle Selection
Given:
Nonlinear model:
min z
Bipartite Graph G = (U ∪ V , E ) such that
(u , v ) ∈ E
⇔
Component type u may be
placed through nozzle type v
For every node u ∈ U a component
number b
u
For every edge ( u,v ) ∈ E an integer
variable yuv
such that
∀ u ∈U :
∑
yuv = bu
∑
yuv ≤ zxv
v:( u ,v )∈E
∀ v ∈V :
u:( u ,v )∈E
∑x
v∈V
v
Minimize no. of
placement cycles
All components
have to be placed
Set up a sufficient
number of nozzles
at placement head
≤k
All variables nonegative
Upper limit for
nozzle segments
integers
Runtime requirement: At most 5 ms!
For every node v ∈ V an integer
variable xv
k = Number of nozzle positions at the
placement head
Variable z = Number of placement cycles
Seite 13
07.07.2009
Michael Hofmeister
Water Supply Network Planning
A Simple Network
Seite 14
07.07.2009
Michael Hofmeister
Inputs and Goals
Required: Fill levels for
the reservoirs
Required: Schedule for valves
Input: Demand forecast for consumers (districts)
Input: Contract with other water suppliers
Objectives:
1.
Safe operation
2.
Full supply of consumers
3.
Minimal costs for water and energy
4.
As few as possible pump switches
07.07.2009
Seite 15
Required: Schedule of pump
switches for the planning horizon (24h)
Michael Hofmeister
Input: Contract
with energy
supplier
© Siemens
AG, Corporate
Technology
Inputs and Goals
Required: Fill levels for
the reservoirs
Required: Schedule for valves
Input: Demand forecast
for consumers (districts)
Input: Contract with other
water suppliers
Objectives:
1.
Safe operation
2.
Full supply of consumers
3.
Minimal costs for water and energy
4.
As few as possible pump switches
07.07.2009
Seite 16
Required: Schedule of pump
switches for the planning horizon (24h)
Michael Hofmeister
General Setting for Optimization
• Demand forecast on a hourly basis;
Planning period: 24 h
• No consideration of pressure progression
Seite 17
07.07.2009
Michael Hofmeister
Subnets
Subnet 1
Subnet 2
Subnet 3
Seite 18
07.07.2009
Michael Hofmeister
Graph Model
Consumer 1
Feeder 1
Subnet 1
Consumer 2
Supplier
Subnet 2
Well
Spring
Subnet 3
Seite 19
07.07.2009
Michael Hofmeister
Creating pump switches
Min cost flow solutions
vB
t
fP
Schedules / fill levels
vB
t
Solutions of the model have to be
transformed into switching points of
time for the pumps and fill level curves
for the reservoirs
t
fP
t
Seite 20
07.07.2009
Michael Hofmeister
The Real Planning Cycle
Initialize planning:
Set current constraints
Optimization
Compute schedule:
Pump switches, fill level curves
Simulation
Evaluate schedule:
Pressure progression
Modify specifications
Activate schedule
Seite 21
07.07.2009
Michael Hofmeister
The Toolset
Siwa-Plan is a toolset for the
management of water supply
networks, including planning and
control functions.
Using Siwa-Plan, the first step is the
engineering of the water net under
consideration.
In addition to the implementation of
optimization and simulation routines,
the challenge is to generate an
appropriate optimizer and simulator.
Seite 22
07.07.2009
Michael Hofmeister
BEP
Pump
Optimization
OPTIM
Schedule
Administration,
Prognosis
SIM
TRAIN
Simulation
SEWER
Sewer
Control
LEAK
Leak Monitoring
VIM
Engineering
Tools
Integration Into Control Equipment
SIWACIS PLAN
Bürowelt / Office
Service
Internet/Intranet
OS Clients / Multi-Clients
@aGlance /
OPC-Server
O&M
Engineering
Station ES
Terminal Bus
Ethernet
OS-Server
Industrial Ethernet / System Bus
ET
200M
Ex-I/O
PROFIBUS-DP
OP
PROFIBUSPA
PROFIBUS-DP
OS
ET
200M
PROFIBUS-PA
ET
200iS
Seite 23
07.07.2009
Michael Hofmeister
The Internet of Things
Routing Goods Like Data
Mail distribution centers
Baggage handling at
Beijing airport
The Internet of Things –
A public funded project *)
*) German Federal Ministry of
Education and Research
Seite 24
07.07.2009
Michael Hofmeister
Hierarchical Structure of Commissioning Systems
Hardware
IT-Structure
Seite 25
07.07.2009
Michael Hofmeister
Basic Concepts
New controls architectures
Migration of “Intelligence" to field level (e.g.,
"intelligent drives")
Distributed controlling functions
Vernetzung of devices at field level ("industrial
ethernet")
Web based services for the level of controls
("one homepage for every motor")
New systems architectures
Distributed software systems
Decentralized controls (e.g., agent technology)
"Aware objects" (RFID, RF-based systems)
Pervasive computing
New material flow strategies
"Routing goods like data" (e.g., like e-mail)
Methods of network management (e.g., IP
routing) in physikal-logistic systems
Seite 26
07.07.2009
Michael Hofmeister
Negotiations of Local Agents
Ouuh, I am skeptic.
I have to work off the
main baggage stream
for Flight No. XYZ.
I decline.
OK, I have to be Xrayed next …
Auction
…
Well, I can do the job.
I expect you in five
minutes.
Seite 27
07.07.2009
Michael Hofmeister
Localization of Agents
Where to localize the agents?

At the field modules
¾ Module agents have to manage their own
workload in order to avoid congestion

At the material to be conveyed
¾ Baggage agents are responsible for their route
through the net
Seite 28
07.07.2009
Michael Hofmeister
State Space of Agent Systems
Available information
Much: global, up-to-date
Little: local, out-of-date
Available
information
Algorithmic complexity
High:
Complex computations
Low:
Simple conditional rules
Scenarios
Topology, dispatching, error
handling, etc.
Much
Little
?
Low
High
Algorithmic
complexity
Scenarios
Own space → difficult to formalize
E.g., density of topology network
Seite 29
07.07.2009
Michael Hofmeister
A Simple Scenario
Transfer
Check in
Sorter
Sorter
Seite 30
07.07.2009
Michael Hofmeister
Three Scenarios
For all scenarios:
Baggage agents plan their route exactly once, at Check In.
Congested edges will be ignored.
Scenario name
Baggage agent
Conveyor agent
Communication
Stupid
Algorithm: Dijkstra
Required edge information:
Lengths of edges
Knowledge about itself:
Length
B: What is your length?
C: x meters
Up-to-date
Algorithm: Dijkstra
Length of edges
Current workload
(-> Penality cost)
Length
Current workload
C: x meters
B: What is your current
workload?
C: y parcels
Anticipatory
Algorithm: Dijkstra
Lengths of edges
Expected workload at time t
(-> Dynamic penality cost)
Length
Expected work load
progression
C: x meters
B: What is your expected
workload at time t1?
C: y parcels
B: Expect me at time t2!
C: Well, I will update my
forecast.
Seite 31
07.07.2009
Michael Hofmeister
Stupid Routing – Situation Short After Dispatching
transfer
check in
sorter
sorter
Seite 32
07.07.2009
Michael Hofmeister
Anticipatory Routing – Situation Short After Dispatching
transfer
check in
sorter
sorter
Seite 33
07.07.2009
Michael Hofmeister
Conclusion
The rapid increasing complexity of industrial challenges
requires usage of mathematical methods of modeling,
simulation and optimization to a great extend.
Mathematicians and computer scientists are invited,
¾ To improve available tools and methods continuously, and
¾ To assist usage of such methods within projects along the
complete life cycle of products, plants and systems.
The tight, project related collaboration with engineers and users
is essential for the successful application of such methods.
Seite 34
07.07.2009
Michael Hofmeister
Thank you for your
attention!
Contact:
Michael Hofmeister
Siemens AG, CT PP 7
Otto-Hahn-Ring 6
D-81730 Munich
[email protected]
Seite 35
07.07.2009
Michael Hofmeister