Simulation Optimization

Source:http://bptrends.com/publicationfiles/01-05%20WP%20Simulation%20Optimization%20-%20April%20et%20al.pdf

Overview

• BPMS offers simulation capabilities
• Simulation is "a means to evaluate the impact of process changes and new processes in a model environment through the creation of “what-if” scenarios"
• decisions can be tested before going life
• simulation allow forecast with a level of uncertainty

Need for Simulation Optimization

• analyst wants to find a set of model optimal performance (parameters and structure)
• range of parameter values and the number of parameter combinations is too large for analysts to simulate all possible scenarios
• they need a way to find a good solutions

Mathematical methods vs Simulation

• many problems are too complex to be modelled in analytical way
• pure optimization models alone are incapable of capturing all the complexities and dynamics of the system
• simulation cannot easily find the best solutions
• Simulation Optimization combines both methods (analytical optimization of the simulation or vice versa)

Heuristic

• Greek: "Εὑρίσκω": find, discover
• technique designed for solving a problem more quickly when classic methods are too slow
• finding an approximate solution when classic methods fail to find any exact solution (by trading optimality, completeness, accuracy, and/or precision for speed)
• e.g. rule of thumb, an educated guess, an intuitive judgement

Metaheuristic

• designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality
• make few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions
• do not guarantee an optimal solution is ever found
• implement some form of stochastic optimization.

(Wikipedia)

Metaheuristics

Problems with Simulations

• Optimization models were thought to over-simplify the real problem
• this was improved by research in metaheuristics along with improved statistical methods of analysis

Metaheuristics

• Coined in 1986 by Dr. Fred Glover
• "describe a master strategy that guides and modifies other heuristics to produce solutions beyond those that are normally generated in a quest for local optimality"

• There are algorithms to guide a series of simulations towards good results in the absence of tractable mathematical structures
• Quality of different solutions can compared
• commercial products use discrete-event or Monte Carlo simulation to performs search for optimal values of input parameters
• tool for commercial simulation software, employs metaheuristics (scatter search, tabu search, neural networks)

Optimization of Simulation Models

1. develop simulation model for a system or a process
2. set performance measure (for possible set of choices)
3. find a configuration that produce good results

Extreme Methods

1. trial-and-error
2. enumeration of all possible configurations

Applications

• configuration of machines for production scheduling
• layouts, links, and capacities for network design
• investment portfolio for financial planning
• utilization of employees for workforce planning
• course scheduling

Black-box Model

Input

• input parameters and/or structural design that lead to optimal performance (factors/levels, decision variables)

Output

• performance measures (responses - used to model an objective function and constraints)

Goal

• find out which factors have the greatest effect on a response
• combination of factor levels that minimizes or maximizes a response
• subject to constraints imposed on factors and/or responses

Constraints

• constraint for both: decision variables and responses need to be formulated

Example

manufacturing facility

factors - number of machines of each type, machine settings, layout, and the number of workers

responses - cycle time, work-in-progress, and resource utilization

goal - reduce cost, minimize cycle time, minimize resource utilization (subject to constraints)

Simulating Result

• "Changes proposed to business processes can be simulated"
• "Sensitivity of making the changes on the ultimate objectives can be examined and quantified, reducing the risk of actual implementation"

Changes

• adding, deleting, and modifying processes
• process times
• resources required
• schedules
• skill levels
• budgets

Performance objectives

• throughput
• costs
• inventories
• resources/capital utilization
• cash flow
• waste

Uncertaintiy

In BPM:

• simulation: a way to understand and communicate the uncertainty related to making the changes,
• optimization: provides the way to manage that uncertainty

Academic Approaches

1. Stochastic approximation (gradient-based approaches)
2. (sequential) response surface methodology
3. random search
4. sample path optimization (also known as stochastic counterpart)

Pragmatic Approach

• Commercial simulation software employs metaheuristics

Evolutionary Approaches

• commercial simulation uses evolutionary approaches
• Evolutionary approaches: builds and evolves population of solutions
• e.g. Genetic Algorithms and Scatter Search.

• a simulation model can be thought of as a

“mechanism that turns input parameters into output performance measures” (Law and Kelton, 1991)

• simulation model is a function that evaluates the merit of a set of specifications, typically represented as set of values
• Looking at simulation model as a function encouraged family of approaches to optimize simulations based on response surfaces and metamodels.

Constraints

• speciying constraints is important feature of simulation optimization
• constraints define the feasibility of trial solutions
• specified as mathematical expressions or as logic statements
• usually formulated with input factors or/and responses

Constraints and Feasability

• constraints in a simulation optimization model depend only on input parameters -> new trial solution can be checked for feasibility before running the simulation
• infeasible trial solution may be discarded or may be mapped to a feasible one when its feasibility depends only on constraints formulated with input parameters
• constraints depend on responses -> feasibility of a solution is not known before running the simulation