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 the SupplyChainNetwork containing the instance. The tree need not already have been pre-processed using preprocess_tree() or relabel_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, and external_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

SupplyChainNetwork

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 is True, in which case performs the relabeling.

Does not modify the input tree. Fills original_label, larger_adjacent_node, and larger_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

SupplyChainNetwork

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, copies stockout_cost field from tree for nodes that have it, and does not fill stockout_cost for nodes that do not.

Returns

SSM_tree – SSM representation of tree.

Return type

SupplyChainNetwork