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
Chen and Y. S. Zheng. Lower bounds for multiechelon stochastic inventory systems. Management Science, 40(11):1426–1443, 1994.
Clark and H. Scarf. Optimal policies for a multiechelon inventory problem. Management Science, 6(4):475–490, 1960.
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 aSupplyChainNetwork
in thenetwork
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 thenode_order_in_system
ornetwork
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
, ifnode_order_in_system
is not provided) but is not a key in the dict, the attribute value is set toNone
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 asnode_order_in_system
(if it is provided) or 1, …,num_nodes
(if it is not), otherwise aValueError
is raised. The values in the list are assumed to correpond to the node indices in the order they are specified innode_order_in_lists
. That is, the value in slotk
in the parameter list is assigned to the node with indexnode_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 asnode_order_in_system
(or innum_nodes
, …, 1, ifnode_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 isnum_nodes
, …, 1 here.)Either
demand_mean
anddemand_standard_deviation
must be provided (in which case the demand will be assumed to be normally distributed), ordemand_source
must be provided, ornetwork
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 ifnetwork
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 thek
th node.) Ignored ifnetwork
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 notNone
. [\(\mu\)]demand_standard_deviation (float, optional) – Standard deviation of demand per unit time at node 1. Ignored if
demand_source
is notNone
. [\(\sigma\)]demand_source (
DemandSource
, optional) – ADemandSource
object describing the demand distribution. Required ifdemand_mean
anddemand_standard_deviation
areNone
.network (
SupplyChainNetwork
, optional) – ASupplyChainNetwork
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, setS
=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 ifx
is provided. Ignored if a discrete distribution is provided indemand_source
(since in that casex
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 indemand_source
(since in that cased
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
isNone
andnum_nodes
, …,stockout_cost
areNone
.ValueError – If
network
,node_order_in_system
, andnum_nodes
are allNone
.ValueError – If
stockout_cost
isNone
or ifechelon_holding_cost
orlead_time
isNone
for any node.ValueError – If
demand_mean
ordemand_standard_deviation
isNone
anddemand_source
isNone
.ValueError – If
stockout_cost
< 0 or iflead_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
Chen and Y. S. Zheng. Lower bounds for multiechelon stochastic inventory systems. Management Science, 40(11):1426–1443, 1994.
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 aSupplyChainNetwork
in thenetwork
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 thenode_order_in_system
ornetwork
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
, ifnode_order_in_system
is not provided) but is not a key in the dict, the attribute value is set toNone
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 asnode_order_in_system
(if it is provided) or 1, …,num_nodes
(if it is not), otherwise aValueError
is raised. The values in the list are assumed to correpond to the node indices in the order they are specified innode_order_in_lists
. That is, the value in slotk
in the parameter list is assigned to the node with indexnode_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 asnode_order_in_system
(or innum_nodes
, …, 1, ifnode_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 isnum_nodes
, …, 1 here.)Either
demand_mean
anddemand_standard_deviation
must be provided (in which case the demand will be assumed to be normally distributed), ordemand_source
must be provided, ornetwork
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 ifnetwork
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 thek
th node.) Ignored ifnetwork
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 notNone
. [\(\mu\)]demand_standard_deviation (float, optional) – Standard deviation of demand per unit time at node 1. Ignored if
demand_source
is notNone
. [\(\mu\)]demand_source (
DemandSource
, optional) – ADemandSource
object describing the demand distribution. Required ifdemand_mean
anddemand_standard_deviation
areNone
.network (
SupplyChainNetwork
, optional) – ASupplyChainNetwork
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
isNone
andnum_nodes
, …,stockout_cost
areNone
.ValueError – If
stockout_cost
isNone
or ifechelon_holding_cost
orlead_time
isNone
for any node.ValueError – If
demand_mean
ordemand_standard_deviation
isNone
anddemand_source
isNone
.ValueError – If
stockout_cost
< 0 or iflead_time
< 0 for any node.
References
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
echelon_S (dict) – Dict of echelon base-stock levels to be evaluated.
parameters (other) – See
optimize_base_stock_levels()
.
- Returns
cost – Expected cost of system.
- Return type
float
- Raises
ValueError – If
stockout_cost
isNone
or ifechelon_S
,echelon_holding_cost
, orlead_time
isNone
for any node.ValueError – If
demand_mean
ordemand_standard_deviation
isNone
anddemand_source
isNone
.ValueError – If
stockout_cost
< 0 or iflead_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
echelon_S (dict) – Dict of echelon base-stock levels to be evaluated.
parameters (other) – See
optimize_base_stock_levels()
.
- Returns
holding_cost – Expected holding cost of system.
- Return type
float
- Raises
ValueError – If
stockout_cost
isNone
or ifechelon_S
,echelon_holding_cost
, orlead_time
isNone
for any node.ValueError – If
demand_mean
ordemand_standard_deviation
isNone
anddemand_source
isNone
.ValueError – If
stockout_cost
< 0 or iflead_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