Introduction to Simulation-based Scheduling

Simulation-based Scheduling

1. Richard A. Wysk
IE 551 – Computer Control in
Manufacturing
Simulation-based
Scheduling and Control

2. System vs. Simulation
Modeling
• Purpose of Modeling
• Fidelity: Level of Detail
• Constraints
Cost
Time
Skilled People
System
Simulation Model

3. Different Uses of
Manufacturing Simulation
Productio
n
Planning
Process Planning
Maintenance
Product Design
(DFM)
Production
Schedulin
gProduction
Control
System
Design &
Analysis
Facility
Planning
Sales
(cost/completion
time prediction)
MRP
(planning)

4. Most Analysis is for Processing Resources OnlyMost Analysis is for Processing Resources Only
Almost all Scheduling considers Processing Resource Almost all Scheduling considers Processing Resource
Constraints OnlyConstraints Only
There is no Material Handling PlanningThere is no Material Handling Planning
Factory Control -
Observations

5. Production
Schedulin
g
Production
Control
System
Design &
Analysis
Different Uses vs. Associated
Simulation Models

Chronological Uses of Simulation

More specific and detailed, and higher fidelity

More expensive and time-consuming to develop

Shorter horizon (from months to seconds)

6. Simulation for Design &
Analysis
Production
Schedulin
g
Production
Control
System
Design &
Analysis

Traditional Usage of Simulation

Before/after existence of a real system

In general, no or little material handling detail --
time/cost constraints

Results may not be always reliable when MHs are scarce
resources

Reference: Smith et al., 1999

7. •Conceptualization
•Preliminary Modeling
•Systems Analysis
•Detailing
Planning Manufacturing
Systems

8. •Aggregate Visualization of System
•No. of milling machines
•No. of turning machines
•...
•...
•Arrangement of Machines
•Layout
•Location
Conceptualization

9. Operations Routing SummariesOperations Routing Summaries
Preliminary Modeling

10. Master Production Schedule

11. j



i
j
MinutesinCapacity Weekly Required
ij
O
ij
D
jn
Min.Available
j
Capacity Required


A
Master Production Schedule

12. M
1
M
2
M
n
MH
P
M1
P
M2
P
Mn
Machine Requirements Analysis

13. NN
jj -- no. of machines of type j -- no. of machines of type j
QQ
jj -- Queueing character for machine j -- Queueing character for machine j
WW
jj -- Wait in j -- Wait in j
TT
ii -- Throughput time for part type i -- Throughput time for part type i
Traditional Simulation

14. Simulation for
Scheduling
Production
Scheduling
Production
Control
System
Design &
Analysis
•Traditionally after a real system has been designed (and typically
built)
•Used for schedule generation or schedule evaluation
•Depending on systems, scheduling results vary:
•Static Environments - Exact starting times and ending times
•Static/Dynamic Environments - “work to” schedules (lists)
•Dynamic Environments - scheduling strategies for each decision
points
•With MH: more expensive, but more accurate results
•Without MH: easier to model, but difficult to implement
schedules

15. Simulation for Control
Productio
n
Schedulin
g
Production
Control
System
Design &
Analysis
•Traditionally after a real system has been designed (and
typically built)
•Used for schedule generation or schedule evaluation
•Depending on systems, scheduling results vary:
•Static Environments - Exact starting times and ending times
•Static/Dynamic Environments - “work to” schedules (lists)
•Dynamic Environments - scheduling strategies for each decision
points
•With MH: more expensive, but more accurate results
•Without MH: easier to model, but difficult to implement
schedules

16. Material Handling (MH)Material Handling (MH)
MH affects schedulesMH affects schedules
MH is addressed every other processMH is addressed every other process
MH is frequently flexibility constraintMH is frequently flexibility constraint
MH devices

17. RapidCIM view to Illustrate
Control Simulation
Requirements
8
2
3
4 5
6
7
1
Task
Number
Task
Name
1 Pick L
2 Put M1
3 Process 1
4 Pick M1
5 Put M2
6 Process 2
7 Pick M2
8 Put UL
M1 M2
R
L UL

18. Some Observations about
this Perspective

Generic -- applies to any system

Other application specifics

Parts

Number

Routing

Buffers (none in our system)

19. Deadlock Related
References

General deadlock discussions

Wysk et al., 1994

Cho et al., 1995

Deadlock detection for simulation

Venkatesh et al., 1998

20. Johnson’s Algorithm (1954)

Optimal sequence: P1 - P3 - P4 - P2

Is the schedule actually optimal in reality?
Operations Routing Summaries for a family of parts (M1 – M2)
Part P1 P2 P3 P4
M1 2 8 4 7
M2 9 3 5 6

21. Traditional schedule v.s.
Realistic schedule (blocking
effects)
1
1
3 4 2
3 4 2
Make-span: 25
M1
M2
1
1
3 4 2
3 4 2
Make-span: 29
M1
M2
+ Material Handling
Can not begin 4
until 3 moves

22. Actual optimal sequence
1
1
3 4 2
3 4 2
Make-span: 29
M1
M2
Optimum by Johnson’s algorithm
1
1
2 3 4
2 3 4
Make-span: 28
M1
M2
Actual optimum

23. Things to be considered for higher
fidelity of scheduling
Deadlocking and blocking related issues
must be considered
Material handling must be considered
Buffers (and buffer transport time) must
be considered

24. Jackson’s Algorithm (1956)

Optimal sequence:

M1: P1 - P2 - P3

M2: P3 - P4 - P1

Is the schedule actually optimal in reality?
Operations Routing Summaries
Part # Sequence Times
1 M1 – M2 5 – 1
2 M1 4
3 M2 – M1 3 – 4
4 M2 2

25. Schedule Implementation

If no buffers exist, it is impossible to
implement the schedule as the optimum
schedule by Jackson’s rule

Even if buffers exist, several better
schedules may exist including the following
schedule:

M1: P1 - P2 - P3

M2: P1 - P3 - P4

26. Simulation specifics
Very detailed simulation models that
emulate the steps of parts through
the system must be developed.
Caution must be taken to insure that
the model behaves properly.
The simulation allocates resources
(planning) and sequences activities
(scheduling).

27. Why Acquire (seize) together?
To avoid deadlock

If we acquire robot and machine separately

the robot will be acquired by the P2

a deadlock situation will occur

If we acquire robot and machine at the same time

the robot will not be acquired until M2 becomes free
:part, done :part, being processed
M1 M2
P2 (M1-M2) P1 (M1-M2)
Legend:

28. Time advancement:
Simulation for Real-time Control

if runs in fast mode

time delay is based on the expected processing time (typically
a statistical distribution)

Move to the next event as quickly as possible

simulation time is based on the computer clock
time

time delay is based on the performance of a physical task
(subject to machining parameters)

task contains parameters: task_name, part_id, op_id

real-time system monitoring (animation)

Reference: Smith et al., 1994

29. Simulation can be used for
control

Traditionally run simulation in fast
mode

Can be coordinated to physical
system via HLA or messaging

30. Production Control View
Part Perspective
M1 M2
R
L UL
Controller determines
what to do next.

31. Simulation-based Scheduling:
methodologies

Combinatorial approach -- intractable

AI/Search algorithms

Simulated annealing

Tabu-search

Genetic algorithm

Neural networks (Cho and Wysk, 1993)

Extended dispatching heuristics

None of these guarantees optimization

32. Simulation-based Scheduling:
multi-pass simulation

Simulation

real-time simulation - task generator

fast simulation - schedule evaluator

Who does the schedule “generation” then?

Look ahead manager

Scheduling: come up with a good combination
of control strategies for the decision points

33. Example system and associated connectivity
graph
Part flow
Machine1 Machine3
Machine2
Robot
AS/RS
1
1
1
R
M2
M3
AS
1
Blocking
Attribute
1: allowed
0: not allowed
M1

34. Generated Execution model -- based on the rules, but
manual yet
1
1
1
R
M
2
M
3
A
S
1
Due to limited space,
these two arrows are
expanded in this
figure
part_enter@1_sb rm_asrs@1_sb rm@1_bk at_loc@1_kb
pick_ns#1@1_sb.......return_ok@1_bs
I I O I
II
at_loc@1_bs
O
pick_ns#1@1_br
O
mv_to_asrs@1_sb arrive@1_bk arrive_ok@1_kb loc_ok@1_bs
put_ns#1@1_sbput_ns#1@1_brclear_ok#1@1_rbput_ok#1@1_bs.......
I O I O
IOIO
T
delete@1
Robots Index
R 1
Stations Index
AS 1
M1 2
M2 3
M3 4
Blocking
attributes are set
to 1: must be
blocked
M
1

35. MPSG Summary
part_enter@1_sb
0
rm_asrs@1_sb pick_ns#1@1_sb
1 2 3
mv_to_mach@2_sb
4
put#1@2_sb process@2_sb
5 6 7
mv_to_mach@3_sb
8
put#1@3_sb process@3_sb
9 1
0
1
1
mv_to_mach@4_sb
1
2
put#1@4_sb process@4_sb
1
3
1
4
1
5
mv_to_asrs@1_sb
1
6
put_ns#1@1_sb return#1@1_sb
1
7
1
8
1
9
return@1_sb
pick#1@2_sb
pick#1@3_sb
pick#1@4_sb

36. MPSG
Summary
part_enter_sb remove_kardex_sb pick_ns_sb r
e
t
u
r
n
_
s
b
put_sb
move_to_mach_sb
move_to_kardex_sb
p
u
t
_
n
s
_
s
b
move_to_mach_sb
0 1 2 3
456
process_sb
pick_sb
7
8 9
return_sb

37. Traditional system development vs. Models automation
approach
Multi-pass
Simulation
Search-based
Scheduling
Heuristic-based
planning
A simple procedure
Manual generation
Manual generation
Shop level executor
Planner
Physical facility
Simulation (task generator)
Automatic generation
Automatic generation
(Connectivity graph & rules)
Formal modeling &
Database Instantiation
Shop level executor
Planner
Physical facility
Resource model
Simulation (task generator)
Scheduler
Associated with system development Associated with system operation
(a) Conventional Approach (b) Proposed Approach

38. Traditional Simulation Approach
For the manufacturing system
System to be simulated
Detailed specification
Simulation model
Manual Acquisition
Programming

39. Automation Modeling
Approach
System to be simulated
Detailed specification
Simulation model
Extraction Rules
Construction Rules
Domain
Knowledge
Target Language
Knowledge

40. System Description
(extraction)
Natural Language
Graphical Formalism
Dialog Monitor
Resource Model
Process Model
Resource Model
Execution Model
User
Detailed
Description

41. Information in Simulation

Static information

something like an experiment file

resource information, shop layout

Dynamic information

part arrival process

part flow and resource interaction

Statistics needed

resource utilization, throughput, etc

42. Penn State Simulation-based
SFCS
ARENA: real-time
(Shop floor
controller)
Big Executor (Shop Level)
Equipment Controllers
SL 20VF 0EABB
2400
PumaMan
MT
Kardex
Task
Output
Queue
Databas
e
Scheduler
Task
Input Queue
ABB
140

43. Simulation-based
Scheduling
D
y
n
a
m
i
c

L
i
n
k

L
i
b
r
a
r
y
Remote Procedure Call
Database
Statistical Analysis
Best Rule Selection
ARENA: Real-time
"fastmode.bat" file
ARENA: fast-mode
Visual Basic Application
Rule 1
Simulation
Rule n
Simulation
Process
plans
Look-ahead Manager
Operating
policy
Order
Details

44. Flow shop (m machines and m+1 robots)
- non-synchronous control
•If no buffers exist, then we must allow blocking happen
•If buffers exist, there are three possible policies when blocking
occurs:
•Not picking up
•Picking up and waiting until the next machine becomes
available,
•Picking up and moving it to the buffer
•Associated blocking control attributes are 1, 0, and 2,
respectively
•We can specify above blocking control strategies
•Refer to the simulation construction rules in the next page

45. For each part type
ID, operation code, description, resource_ID,
Robot_location, NC_file_name
Reference: Lee et al., 1994
Implementation
database representation
PSL (Process specification language)
IDEF 3 (ICAM Definition language)
etc
Information in Process Plans

46. Process Plan vs. Simulation

Simulation in simulation based control

Process plans reside externally

Simulation in design and analysis

Process plans reside within the simulation
model

Possible to include the alternative
routings within the model

47. Conclusion
Structure and information

Simulation model

Resource model

Execution model
Simulation model generation - resource
model and execution model (+blocking
attributes)
% to be generated

Depends on the types of system

Pretty much for nothing

48. References
Cho, H., T. K., Kumaran, and R. A. Wysk, 1995, ”Graph-theoretic deadlock detection
and resolution for flexible manufacturing systems". IEEE Transactions on Robotics and
Automation, Vol. 11, No. 3, pp. 413-421.
Cho, H., and R. A. Wysk, 1993, "A Robust Adaptive Scheduler for an intelligent
Workstation Controller". International Journal of Production Research, Vol. 31, No. 4,
pp. 771-789.
Drake, G.R., J.S. Smith, and B.A. Peters, 1995, "Simulation as a planning and
scheduling tool for flexible manufacturing systems". Proceedings of the 1995 Winter
Simulation Conference. pp. 805-812.
Ferreira, Joao C. and Wysk, R. A., “An investigation of the influence of alternative
process plans on equipment control”, Journal of Manufacturing Systems, Vol. 19, No. 6,
pp. 393 – 406, 2001.
Ferreira, J. C. E., Steele, J., Wysk, R. A., and Pasi, D. A., “A Schema for Flexible
Equipment Control in Manufacturing Systems”, International Journal of Advanced
Manufacturing Technology, Vol 18, 410 - 421.
 Lee, S., R. Wysk, and J. Smith, 1994, “Process Planning Interface for a Shop Floor
Control Architecture for Computer-integrated Manufacturing," International Journal
of Production Research, Vol. 9, No. 9, pp. 2415 - 2435.
Smith, J. and S. Joshi., 1992, “Message-based Part State Graphs (MPSG): A Formal
Model for Shop Control”, ASME Journal of Engineering for Industry, (In review).
Smith, J., B. Peters, and A. Srinivasan, 1999, “Job Shop scheduling considering
material handling”, International Journal of Production Research, Vol. 37, No. 7, 1541-
1560

49. References

Son, Young-Jun and Wysk, R. A., “Automatic simulation model generation for simulation-based,
real-time control”, Computers in Industry, vol. 45, pp 291 - 308, 2001.

Steele, Jay W., Son, Young-Jun and Wysk, R. A., “Resource Modeling for Integration of the
Manufacturing Enterprise”, Journal of Manufacturing Systems, Vol. 19, No. 6, pp 407 – 426, 2001.

Moreno-Lizaranzu, Manuel J., Wysk, Richard A., Hong, Joonki and Prabhu, Vittaldas V., “A Hybrid
Shop Floor Control System For Food Manufacturing”, Transactions of IIE, Vol. 33, No. 3, 193 –
2003, March 2001.

Hong, Joonki, Prabhu Vittal and Wysk, R. A., “Real-time Batch Sequencing using arrival time
control algorithm”, International Journal of Production Research, Vol 39, No. 17, pp 3863 – 3880,
2001.

Ferreira, J. C. E. and Wysk, R. A., “On the efficiency of alternative process plans”, Journal of the
Brazilian Society of Mechanical Sciences, Vol. XXIII, No. 3, pp 285 – 302, 2001.

Smith, J. S., Wysk, R. A., Sturrok, D. T., Ramaswamy, S. E., Smith, G. D., and S. B. Joshi., 1994,
“Discrete Event Simulation for Shop Floor Control” Proceedings of the 1994 Winter Simulation
Conference, pp. 962-969.

Son, Y., H. Rodríguez-Rivera, and R. Wysk, 1999, “A Multi-pass Simulation-based, Real-time
Scheduling and Shop Floor Control System," (Accepted) Transactions, The quarterly Journal of
the Society for Computer Simulation International.

50. 
Steele, J., S. Lee, C. Narayanan, and R. Wysk, 1999, “Resource Models for Modeling Product,
Process and Production Requirements in Engineering Environments," submitted to
International Journal of Production Research.
•Venkatesh, S., J. S. Smith, B. Deuermeyer, and G. Curry, 1998, ”Deadlock detection for discrete
event simulation: Multiple-unit seizes". IIE Transactions, Vol. 30 No. 3, pp. 201-216
•Wu, S.D. and R.A. Wysk, 1988, "Multi-pass expert control system - A control / scheduling
structure for flexible manufacturing cells". Journal of Manufacturing Systems, Vol. 7 No. 2, pp.
107-120
•Wu, S.D. and R.A. Wysk, 1989, "An application of discrete-event simulation to on-line control
and scheduling in flexible manufacturing". International Journal of Production Research, Vol. 27,
No. 9, pp. 1603-1623.
•Wysk, R.A., Peters, B.A., and J.S. Smith, 1995, “A Formal Process Planning Schema for Shop
Floor Control” Engineering Design and Automation Journal, Vol. 1, No. 1, pp. 3-19
•Wysk, R. A., N. Yang, S. Joshi, 1994, "Resolution of deadlocks in flexible manufacturing
systems: avoidance and recovering approaches". Journal of Manufacturing Systems, Vol. 13, No.
2, pp. 128-138.
References