ssm_serial Module

Overview

The ssm_serial module contains code to solve serial systems under the stochastic service model (SSM), either exactly, using the optimize_base_stock_levels() function (which implements the algorithm by Chen and Zheng (1994), which in turn is based on the algorithm by Clark and Scarf (1960)), or approximately, using the newsvendor_heuristic() function (which implements the newsvendor heuristic by Shang and Song (2003)).

Note

The terms “node” and “stage” are used interchangeably in the documentation.

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

  1. Chen and Y. S. Zheng. Lower bounds for multiechelon stochastic inventory systems. Management Science, 40(11):1426–1443, 1994.

    1. Clark and H. Scarf. Optimal policies for a multiechelon inventory problem. Management Science, 6(4):475–490, 1960.

    1. Shang and J.-S. Song. Newsvendor bounds and heuristic for optimal policies in serial supply chains. Management Science, 49(5):618-638, 2003.

API Reference

optimize_base_stock_levels(num_nodes=None, node_order_in_system=None, node_order_in_lists=None, echelon_holding_cost=None, lead_time=None, stockout_cost=None, demand_mean=None, demand_standard_deviation=None, demand_source=None, network=None, S=None, plots=False, x=None, x_num=1000, d_num=100, ltd_lower_tail_prob=3.167124183311998e-05, ltd_upper_tail_prob=3.167124183311998e-05, sum_ltd_lower_tail_prob=3.167124183311998e-05, sum_ltd_upper_tail_prob=3.167124183311998e-05)[source]

Chen-Zheng (1994) algorithm for stochastic serial systems under the stochastic service model (SSM), which in turn is based on Clark and Scarf (1960).

Problem instance may either be provided in the individual parameters num_nodes, …, demand_source, or as a SupplyChainNetwork in the network parameter.

By default, the nodes in the system are assumed to be indexed num_nodes, …, 1, with node 1 at the downstream end, but this can be changed by providing either the node_order_in_system or network parameter.

The node-specific parameters (echelon_holding_cost, lead_time) must be either a dict, a list, or a singleton, with the following requirements:

  • If the parameter is a dict, then the keys must contain the node indices and the values must contain the corresponding attribute values. If a given node index is contained in node_order_in_system (or in 1, …, num_nodes, if node_order_in_system is not provided) but is not a key in the dict, the attribute value is set to None for that node.

  • If the parameter is a singleton, then the attribute is set to that value for all nodes.

  • If the parameter is a list and node_order_in_lists is provided, node_order_in_lists must contain the same indices as node_order_in_system (if it is provided) or 1, …, num_nodes (if it is not), otherwise a ValueError is raised. The values in the list are assumed to correpond to the node indices in the order they are specified in node_order_in_lists. That is, the value in slot k in the parameter list is assigned to the node with index node_order_in_lists[k].

  • If the parameter is a list and node_order_in_lists is not provided, the values in the list are assumed to correspond to nodes in the same order as node_order_in_system (or in num_nodes, …, 1, if node_order_in_system is not provided).

(These are the same requirements as in stockpyl.supply_chain_network.serial_system(), except that the default node numbering is num_nodes, …, 1 here.)

Either demand_mean and demand_standard_deviation must be provided (in which case the demand will be assumed to be normally distributed), or demand_source must be provided, or network must be provided.

If demand_source is provided and has all-integer support, this is accounted for in the discretization, and the solutions returned will also be integer.

Parameters

  • num_nodes (int, optional) – Number of nodes in serial system. [\(N\)]

  • node_order_in_system (list, optional) – List of node indices in the order that they appear in the serial system, with upstream-most node listed first. If omitted, the system will be indexed num_nodes, …, 1. Ignored if network is provided.

  • node_order_in_lists (list, optional) – List of node indices in the order in which the nodes are listed in any attributes that are lists. (node_order_in_lists[k] is the index of the k th node.) Ignored if network is provided.

  • echelon_holding_cost (float, list, or dict, optional) – Echelon holding cost at each node. [\(h\)]

  • lead_time (float, list, or dict, optional) – (Shipment) lead time at each node. [\(L\)]

  • stockout_cost (float, optional) – Stockout cost per item per unit time at node 1. [\(p\)]

  • demand_mean (float, optional) – Mean demand per unit time at node 1. Ignored if demand_source is not None. [\(\mu\)]

  • demand_standard_deviation (float, optional) – Standard deviation of demand per unit time at node 1. Ignored if demand_source is not None. [\(\sigma\)]

  • demand_source (DemandSource, optional) – A DemandSource object describing the demand distribution. Required if demand_mean and demand_standard_deviation are None.

  • network (SupplyChainNetwork, optional) – A SupplyChainNetwork object that provides all of the necessary data. If provided, num_nodes, …, demand_source are ignored.

  • S (dict, optional) – Dict of echelon base-stock levels to evaluate. If present, no optimization is performed and the function just returns the cost under base-stock levels S; to optimize instead, set S = None (the default). [\(S\)]

  • plots (bool, optional) – True for the function to generate plots of \(C(\cdot)\) functions, False otherwise.

  • x (ndarray, optional) – x-array to use for truncation and discretization, or None (the default) to determine automatically.

  • x_num (int, optional) – Number of discretization intervals to use for x range. Ignored if x is provided. Ignored if a discrete distribution is provided in demand_source (since in that case x range is discretized to integers).

  • d_num (int, optional) – Number of discretization intervals to use for d range. Ignored if a discrete distribution is provided in demand_source (since in that case d range is discretized to integers).

  • ltd_lower_tail_prob (float, optional) – Lower tail probability to use when truncating lead-time demand distribution.

  • ltd_upper_tail_prob (float, optional) – Upper tail probability to use when truncating lead-time demand distribution.

  • sum_ltd_lower_tail_prob (float, optional) – Lower tail probability to use when truncating “sum-of-lead-times” demand distribution.

  • sum_ltd_upper_tail_prob (float, optional) – Upper tail probability to use when truncating “sum-of-lead-times” demand distribution.

Returns

  • S_star (dict) – Dict of optimal echelon base-stock levels. [\(S^*\)]

  • C_star (float) – Optimal expected cost. [\(C^*\)]

Raises

  • ValueError – If network is None and num_nodes, …, stockout_cost are None.

  • ValueError – If network, node_order_in_system, and num_nodes are all None.

  • ValueError – If stockout_cost is None or if echelon_holding_cost or lead_time is None for any node.

  • ValueError – If demand_mean or demand_standard_deviation is None and demand_source is None.

  • ValueError – If stockout_cost < 0 or if lead_time < 0 for any node.

Equations Used:

\[\underline{g}_0(x) = (p+h'_1)x^-\]

For \(j=1,\ldots,N\):

\[\begin{split}\begin{gather*} \hat{g}_j(x) = h_jx + \underline{g}_{j-1}(x) \\ g_j(y) = E\left[\hat{g}_j(y-D_j)\right] \\ S^*_j = \mathrm{argmin} \{g_j(y)\} \\ \underline{g}_j(x) = g_j(\min\{S_j^*,x\}) \end{gather*}\end{split}\]

The range of \(x\) values considered is discretized and truncated. The \(\hat{g}_j(x)\) functions sometimes need to be evaluated for \(x\) values outside this range. For those values, the following limits provide linear approximations that are used instead (see Problem 6.13):

\[\begin{split}\begin{gather*} \lim_{x \rightarrow -\infty} \hat{g}_j(x) = \sum_{i=1}^j h_i\left(x - \sum_{k=i}^{j-1} E[D_k]\right) - (p+h'_1)\left(x - \sum_{k=1}^{j-1} E[D_k]\right) \\ \lim_{x \rightarrow +\infty} \hat{g}_j(x) = \begin{cases} h_jx + g_{j-1}(S^*_{j-1}), & \text{if $j>1$} \\ h_jx, & \text{if $j=1$} \end{cases} \end{gather*}\end{split}\]

References

  1. Chen and Y. S. Zheng. Lower bounds for multiechelon stochastic inventory systems. Management Science, 40(11):1426–1443, 1994.

    1. Clark and H. Scarf. Optimal policies for a multiechelon inventory problem. Management Science, 6(4):475–490, 1960.

Example (Example 6.1):

>>> S_star, C_star = optimize_base_stock_levels(
...     num_nodes=3,
...     echelon_holding_cost=[2, 2, 3],
...     lead_time=[2, 1, 1],
...     stockout_cost=37.12,
...     demand_mean=5,
...     demand_standard_deviation=1
...     )
>>> S_star
{3: 22.700237234889784, 2: 12.012332294949644, 1: 6.5144388073261155}
>>> C_star
47.668653127136345
newsvendor_heuristic(num_nodes=None, node_order_in_system=None, node_order_in_lists=None, echelon_holding_cost=None, lead_time=None, stockout_cost=None, demand_mean=None, demand_standard_deviation=None, demand_source=None, network=None, weight=0.5, round_type=None)[source]

Shang-Song (2003) heuristic for stochastic serial systems under stochastic service model (SSM), as described in FoSCT.

Problem instance may either be provided in the individual parameters num_nodes, …, demand_source, or as a SupplyChainNetwork in the network parameter.

By default, the nodes in the system are assumed to be indexed num_nodes, …, 1, with node 1 at the downstream end, but this can be changed by providing either the node_order_in_system or network parameter.

The node-specific parameters (echelon_holding_cost, lead_time) must be either a dict, a list, or a singleton, with the following requirements:

  • If the parameter is a dict, then the keys must contain the node indices and the values must contain the corresponding attribute values. If a given node index is contained in node_order_in_system (or in 1, …, num_nodes, if node_order_in_system is not provided) but is not a key in the dict, the attribute value is set to None for that node.

  • If the parameter is a singleton, then the attribute is set to that value for all nodes.

  • If the parameter is a list and node_order_in_lists is provided, node_order_in_lists must contain the same indices as node_order_in_system (if it is provided) or 1, …, num_nodes (if it is not), otherwise a ValueError is raised. The values in the list are assumed to correpond to the node indices in the order they are specified in node_order_in_lists. That is, the value in slot k in the parameter list is assigned to the node with index node_order_in_lists[k].

  • If the parameter is a list and node_order_in_lists is not provided, the values in the list are assumed to correspond to nodes in the same order as node_order_in_system (or in num_nodes, …, 1, if node_order_in_system is not provided).

(These are the same requirements as in stockpyl.supply_chain_network.serial_system(), except that the default node numbering is num_nodes, …, 1 here.)

Either demand_mean and demand_standard_deviation must be provided (in which case the demand will be assumed to be normally distributed), or demand_source must be provided, or network must be provided.

Rounding is discussed in Shang and Song (2003), p. 625.

Parameters

  • num_nodes (int, optional) – Number of nodes in serial system. [\(N\)]

  • node_order_in_system (list, optional) – List of node indices in the order that they appear in the serial system, with upstream-most node listed first. If omitted, the system will be indexed num_nodes, …, 1. Ignored if network is provided.

  • node_order_in_lists (list, optional) – List of node indices in the order in which the nodes are listed in any attributes that are lists. (node_order_in_lists[k] is the index of the k th node.) Ignored if network is provided.

  • echelon_holding_cost (float, list, or dict, optional) – Echelon holding cost at each node. [\(h\)]

  • lead_time (float, list, or dict, optional) – (Shipment) lead time at each node. [\(L\)]

  • stockout_cost (float, optional) – Stockout cost per item per unit time at node 1. [\(p\)]

  • demand_mean (float, optional) – Mean demand per unit time at node 1. Ignored if demand_source is not None. [\(\mu\)]

  • demand_standard_deviation (float, optional) – Standard deviation of demand per unit time at node 1. Ignored if demand_source is not None. [\(\mu\)]

  • demand_source (DemandSource, optional) – A DemandSource object describing the demand distribution. Required if demand_mean and demand_standard_deviation are None.

  • network (SupplyChainNetwork, optional) – A SupplyChainNetwork object that provides all of the necessary data. If provided, num_nodes, …, demand_source are ignored.

  • weight (float, optional) – Weight to use in weighted sum of lower- and upper-bound base-stock levels.

  • round_type (string, optional) – Set to ‘up’ to always round base-stock levels up to next larger integer, ‘down’ to always round down, ‘nearest’ to round to nearest integer, or None to not round at all.

Returns

S_heur – Dict of heuristic echelon base-stock levels. [\(\tilde{S}\)]

Return type

dict

Raises

  • ValueError – If network is None and num_nodes, …, stockout_cost are None.

  • ValueError – If stockout_cost is None or if echelon_holding_cost or lead_time is None for any node.

  • ValueError – If demand_mean or demand_standard_deviation is None and demand_source is None.

  • ValueError – If stockout_cost < 0 or if lead_time < 0 for any node.

References

    1. Shang and J.-S. Song. Newsvendor bounds and heuristic for optimal policies in serial supply chains. Management Science, 49(5):618-638, 2003.

Equation Used (equation (6.32)):

\[\tilde{S}_j = \texttt{weight}\tilde{F}_j^{-1}\left(\frac{p+\sum_{i=j+1}^N h_i}{p+\sum_{i=j}^N h_i}\right) + (1-\texttt{weight})\tilde{F}_j^{-1}\left(\frac{p+\sum_{i=j+1}^N h_i}{p+\sum_{i=1}^N h_i}\right)\]

for \(j=1,\ldots,N\).

Example (Example 6.1):

>>> S_heur = newsvendor_heuristic(
...             num_nodes=3,
...             echelon_holding_cost=[2, 2, 3],
...             lead_time=[2, 1, 1],
...             stockout_cost=37.12,
...             demand_mean=5,
...             demand_standard_deviation=1
...             )
>>> S_heur # (optimal is {3: 22.700237234889784, 2: 12.012332294949644, 1: 6.5144388073261155})
{3: 22.634032391786285, 2: 12.027434723327854, 1: 6.490880975286938}
>>> # Calculate expected cost of heuristic solution. (optimal is 47.668653127136345)
>>> expected_cost(
...             echelon_S=S_heur,
...             num_nodes=3,
...             echelon_holding_cost=[2, 2, 3],
...             lead_time=[2, 1, 1],
...             stockout_cost=37.12,
...             demand_mean=5,
...             demand_standard_deviation=1
...             )
47.680099140842174
expected_cost(echelon_S, num_nodes=None, echelon_holding_cost=None, lead_time=None, stockout_cost=None, demand_mean=None, demand_standard_deviation=None, demand_source=None, network=None, x_num=1000, d_num=100, ltd_lower_tail_prob=3.167124183311998e-05, ltd_upper_tail_prob=3.167124183311998e-05, sum_ltd_lower_tail_prob=3.167124183311998e-05, sum_ltd_upper_tail_prob=6.661338147750939e-16)[source]

Calculate expected cost of given solution.

This is a wrapper function that calls optimize_base_stock_levels() without doing any optimization.

For parameter descriptions, see docstring for optimize_base_stock_levels().

Parameters
Returns

cost – Expected cost of system.

Return type

float

Raises

  • ValueError – If stockout_cost is None or if echelon_S, echelon_holding_cost, or lead_time is None for any node.

  • ValueError – If demand_mean or demand_standard_deviation is None and demand_source is None.

  • ValueError – If stockout_cost < 0 or if lead_time < 0 for any node.

Equations Used: See optimize_base_stock_levels().

Example (Example 6.1):

>>> expected_cost(
...             echelon_S={1: 6.5144388073261155, 2: 12.012332294949644, 3: 22.700237234889784},
...     num_nodes=3,
...     echelon_holding_cost=[2, 2, 3],
...     lead_time=[2, 1, 1],
...     stockout_cost=37.12,
...     demand_mean=5,
...     demand_standard_deviation=1
...     )
47.668653127136345
expected_holding_cost(echelon_S, num_nodes=None, echelon_holding_cost=None, lead_time=None, stockout_cost=None, demand_mean=None, demand_standard_deviation=None, demand_source=None, network=None, x_num=1000, d_num=100, ltd_lower_tail_prob=3.167124183311998e-05, ltd_upper_tail_prob=3.167124183311998e-05, sum_ltd_lower_tail_prob=3.167124183311998e-05, sum_ltd_upper_tail_prob=6.661338147750939e-16)[source]

Calculate expected holding cost of given solution.

The basic idea is to set the stockout cost to 0 and call optimize_base_stock_levels() without doing any optimization.

For parameter descriptions, see docstring for optimize_base_stock_levels().

Parameters
Returns

holding_cost – Expected holding cost of system.

Return type

float

Raises

  • ValueError – If stockout_cost is None or if echelon_S, echelon_holding_cost, or lead_time is None for any node.

  • ValueError – If demand_mean or demand_standard_deviation is None and demand_source is None.

  • ValueError – If stockout_cost < 0 or if lead_time < 0 for any node.

Equations Used: See optimize_base_stock_levels().

Example (Example 6.1):

>>> expected_holding_cost(
...             echelon_S={1: 6.5144388073261155, 2: 12.012332294949644, 3: 22.700237234889784},
...     num_nodes=3,
...     echelon_holding_cost=[2, 2, 3],
...     lead_time=[2, 1, 1],
...     stockout_cost=37.12,
...     demand_mean=5,
...     demand_standard_deviation=1
...     )
43.15945901616041