Simulation Optimization

From Training Material
Revision as of 23:08, 23 November 2012 by Bernard Szlachta (talk | contribs) (→‎Heuristic)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

Metaheuristics classification.svg


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

png?inline&authkey=2dc1cf9f7f9d3bdcb96671c66fe0911b6c545adf282da7443bf344a9271822&.png


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