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:¶
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