gsm_tree
Module¶
Overview¶
The gsm_tree
module implements Graves and Willems’s (2000, 2003) dynamic programming (DP)
algorithm for multi-echelon inventory systems with tree structures.
Note
The terms “node” and “stage” are used interchangeably in the documentation.
The primary data object is the SupplyChainNetwork
, which contains all of the data
for the GSM instance.
Note
The notation and references (equations, sections, examples, etc.) used below refer to Snyder and Shen, Fundamentals of Supply Chain Theory (FoSCT), 2nd edition (2019).
See Also
For an overview of multi-echelon inventory optimization in Stockpyl, see the tutorial page for multi-echelon inventory optimization.
References
S. C. Graves and S. P. Willems. Optimizing strategic safety stock placement in supply chains. Manufacturing and Service Operations Management, 2(1):68-83, 2000.
S. C. Graves and S. P. Willems. Erratum: Optimizing strategic safety stock placement in supply chains. Manufacturing and Service Operations Management, 5(2):176-177, 2003.
API Reference¶
- optimize_committed_service_times(tree)[source]¶
Optimize committed service times using the dynamic programming (DP) algorithm of Graves and Willems (2000, 2003).
tree
is theSupplyChainNetwork
containing the instance. The tree need not already have been pre-processed usingpreprocess_tree()
orrelabel_nodes()
; this function will do so.Output parameters are expressed using the original labeling of tree, even if the nodes are relabeled internally.
- Parameters
tree (
SupplyChainNetwork
) – The multi-echelon tree network. Current node labels are ignored and may be anything.- Returns
opt_cst (dict) – Dict of optimal CSTs, with node indices as keys and CSTs as values.
opt_cost (float) – Optimal expected cost of system.
Example (Example 6.5):
>>> from stockpyl.instances import load_instance >>> tree = load_instance("example_6_5") >>> opt_cst, opt_cost = optimize_committed_service_times(tree) >>> opt_cst {1: 0, 3: 0, 2: 0, 4: 1} >>> opt_cost 8.277916867529369
References
S. C. Graves and S. P. Willems. Optimizing strategic safety stock placement in supply chains. Manufacturing and Service Operations Management, 2(1):68-83, 2000.
S. C. Graves and S. P. Willems. Erratum: Optimizing strategic safety stock placement in supply chains. Manufacturing and Service Operations Management, 5(2):176-177, 2003.
- preprocess_tree(tree)[source]¶
Preprocess the GSM tree. Returns an independent copy.
If tree is already correctly labeled, does not relabel it.
Fill node-level attributes:
net_demand_mean
,net_demand_standard_deviation
,larger_adjacent_node
,max_replenishment_time
.Fill missing data for
demand_bound_constant
,external_inbound_cst
, andexternal_outbound_cst attributes
.Fill
max_max_replenishment_time
network-level attribute.- Parameters
tree (
SupplyChainNetwork
) – The multi-echelon tree network. Current node labels are ignored and may be anything.start_index (int, optional) – Integer to use as starting (smallest) node label.
- Returns
new_tree – Pre-processed multi-echelon tree network.
- Return type
- relabel_nodes(tree, start_index=0, force_relabel=False)[source]¶
Perform the node-labeling algorithm described in Section 5 of Graves and Willems (2000).
If tree is already correctly labeled, returns the original tree, unless
force_relabel
isTrue
, in which case performs the relabeling.Does not modify the input tree. Fills
original_label
,larger_adjacent_node
, andlarger_adjacent_node_is_downstream
attributes of nodes in new tree, whether or not original tree was already correctly labeled.- Parameters
tree (
SupplyChainNetwork
) – The multi-echelon tree network. Current node labels are ignored (unless the tree is already correctly labeled) and may be anything.start_index (int, optional) – Integer to use as starting (smallest) node label.
force_relabel (bool, optional) – If
True
, function will relabel nodes even if original tree is correctly labeled.
- Returns
relabeled_tree – The relabeled tree network.
- Return type
- is_correctly_labeled(tree)[source]¶
Determine whether tree is already correctly labeled.
Tree is correctly labeled if all labels are consecutive integers and every stage (other than the highest-indexed one) has exactly one adjacent stage with a greater index.
- Parameters
tree (
SupplyChainNetwork
) – The multi-echelon tree network.- Return type
True
if tree is already correctly labeled.
- gsm_to_ssm(tree, p=None)[source]¶
Convert GSM tree to SSM tree:
Convert local to echelon holding costs.
Convert processing times to lead times.
Include stockout cost at demand nodes (if provided).
Tree must be pre-processed before calling.
- Parameters
tree (
SupplyChainNetwork
) – The multi-echelon tree network.p (float or dict, optional) – Stockout cost to use at demand nodes, or dict indicating stockout cost for each demand node. If
None
, copiesstockout_cost
field from tree for nodes that have it, and does not fillstockout_cost
for nodes that do not.
- Returns
SSM_tree – SSM representation of tree.
- Return type