san.rst

Model: Stochastic Activity Network (SAN)

Description:

Consider a stochastic activity network (SAN) where each arc i is associated with a task with random duration X_i. Task durations are independent. SANs are also known as PERT networks and are used in planning large-scale projects.

An example SAN with 13 arcs is given in the following figure:

Sources of Randomness:

1. Task durations are exponentially distributed with mean θ_i.

Model Factors:

• num_nodes: Number of nodes.

  • Default: 9

• arcs: List of arcs.

  • Default: [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 6), (4, 5),

    (4, 7), (5, 6), (5, 8), (6, 9), (7, 8), (8, 9)]

• arc_means: Mean task durations for each arc.

  • Default: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Responses:

• longest_path_length: Length/duration of the longest path.

References:

This model is adapted from Avramidis, A.N., Wilson, J.R. (1996). Integrated variance reduction strategies for simulation. Operations Research 44, 327-346. (https://pubsonline.informs.org/doi/abs/10.1287/opre.44.2.327)

Optimization Problem: Minimize Longest Path Plus Penalty (SAN-1)

Decision Variables:

• arc_means

Objectives:

Suppose that we can select θ_i > 0 for each i, but there is an associated cost. In particular, we want to minimize ET(θ) + f(θ), where T(θ) is the (random) duration of the longest path from a to i and $f(\theta) = \sum_{i=1}^{n}\theta_i^{-1}$ where n is the number of arcs.

The objective function is convex in θ. An IPA estimator of the gradient is also given in the code.

Constraints:

We require that theta_i > 0 for each i.

Problem Factors:

• budget: Max # of replications for a solver to take.
  • Default: 10000
• arc_costs: Cost associated to each arc.
  • Default: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Fixed Model Factors:

• N/A

Starting Solution:

• initial_solution: (8,) * 13

Random Solutions:

Sample each arc mean uniformly from a lognormal distribution with 2.5- and 97.5-percentiles at 0.1 and 10 respectively.

Optimal Solution:

Unknown

Optimal Objective Function Value:

Unknown