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:

The SAN diagram has failed to display

Sources of Randomness:

  1. Task durations are exponentially distributed with mean \(\theta_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 \(\theta_i > 0\) for each \(i\), but there is an associated cost. In particular, we want to minimize \(ET(\theta) + f(\theta)\), where \(T(\theta)\) 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 \(\theta\). 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