1CM120 - Formula sheet

LR Module SPIM Module SPIM – Greedy Heuristic
Problem (P) 𝐼𝐼: set of SKUs The Greedy Heuristic is about finding a
min[𝐶𝐶(𝑆𝑆)] 𝑁𝑁: set of machine types feasible solution in the cheapest possible way.
Subject to 𝑚𝑚𝑖𝑖,𝑛𝑛 (≥ 0): Demand rate for SKU 𝑖𝑖 by machine type 𝑛𝑛 Minimum basestock levels already found for
𝐸𝐸𝐸𝐸𝐸𝐸(𝑆𝑆) ≤ 𝐸𝐸𝐸𝐸𝑂𝑂𝑜𝑜𝑜𝑜𝑜𝑜 𝑀𝑀𝑛𝑛 = ∑𝑖𝑖∈𝐼𝐼 𝑚𝑚𝑖𝑖,𝑛𝑛 : total demand rate of machine type 𝑛𝑛 enumeration procedure. Make a table for:
𝑆𝑆𝑖𝑖 ∈ {0,1, … }, ∀𝑖𝑖 ∈ 𝐼𝐼 𝜇𝜇𝑖𝑖 = ∑𝑛𝑛∈𝑁𝑁 𝑚𝑚𝑖𝑖,𝑛𝑛 : Total demand rate for SKU 𝑖𝑖 iteration, gammas, k, basestock levels,
𝑡𝑡𝑖𝑖 (> 0): Mean replenishment lead time for SKU 𝑖𝑖 aggregate mean waiting times, and total cost.

𝐸𝐸𝐸𝐸𝐸𝐸(𝑆𝑆) = � 𝐸𝐸𝐸𝐸𝑂𝑂𝑖𝑖 (𝑆𝑆𝑖𝑖 ) 𝑡𝑡𝑖𝑖𝑒𝑒𝑒𝑒 (0 ≤ 𝑡𝑡𝑖𝑖𝑒𝑒𝑒𝑒 ≤ 𝑡𝑡𝑖𝑖 ): Mean time for an emergency Δ𝑖𝑖 𝑑𝑑(𝑆𝑆)
Γ𝑖𝑖 = −
𝑖𝑖∈𝐼𝐼 shipment for SKU 𝑖𝑖 Δ𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 )
𝐶𝐶(𝑆𝑆) = � 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ) = � 𝑐𝑐𝑖𝑖𝑎𝑎 𝑆𝑆𝑖𝑖 𝑐𝑐𝑖𝑖𝑒𝑒𝑒𝑒 (≥ 0): corresponding cost for an emergency Δ𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ) = 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 + 1) − 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 )
𝑖𝑖∈𝐼𝐼 𝑖𝑖∈𝐼𝐼 shipment Δ𝑖𝑖 𝑑𝑑(𝑆𝑆) = 𝑑𝑑(𝑆𝑆 + 𝑒𝑒𝑖𝑖 ) − 𝑑𝑑(𝑆𝑆)
𝑐𝑐𝑖𝑖ℎ (> 0): Inventory holding cost per time unit per part +
�𝑛𝑛𝑜𝑜𝑜𝑜𝑜𝑜 �
�𝑛𝑛 (𝑆𝑆 + 𝑒𝑒𝑖𝑖 ) − 𝑊𝑊
Δ𝑖𝑖 𝑑𝑑(𝑆𝑆) = � ��𝑊𝑊
General Optimization Problem of SKU 𝑖𝑖
𝑛𝑛∈𝒩𝒩
min 𝑓𝑓(𝑥𝑥) , 𝑥𝑥 ∈ 𝒳𝒳 𝑜𝑜𝑜𝑜𝑜𝑜 +
Subject to �𝑛𝑛 (𝑆𝑆) − 𝑊𝑊
− �𝑊𝑊 �𝑛𝑛 � �
�𝑛𝑛𝑜𝑜𝑜𝑜𝑜𝑜 (> 0): Target level for the aggregate mean waiting
𝑊𝑊
𝑔𝑔𝑗𝑗 (𝑥𝑥) ≤ 𝑏𝑏𝑗𝑗 , 𝑗𝑗 = 1, … , 𝑚𝑚 time for machine type 𝑛𝑛 𝑜𝑜𝑜𝑜𝑜𝑜 +
�𝑛𝑛 (𝑆𝑆) − 𝑊𝑊
Here, 𝑑𝑑(𝑆𝑆) = ∑𝑛𝑛∈𝑁𝑁 �𝑊𝑊 �𝑛𝑛 �
𝑆𝑆 = {𝑥𝑥: 𝑥𝑥 ∈ 𝒳𝒳, 𝑔𝑔𝑗𝑗 (𝑥𝑥) ≤ 𝑏𝑏𝑗𝑗 , 𝑗𝑗 = 1, … , 𝑚𝑚} is called the
feasible region Decision variables Increase the basestock level for the largest Γ𝑖𝑖 .
𝑆𝑆𝑖𝑖 : Basestock level for SKU 𝑖𝑖, (𝑆𝑆𝑖𝑖 ∈ {0,1, … }), and 𝑆𝑆 =
Lagrange function (𝑆𝑆1 , 𝑆𝑆2 , . . , 𝑆𝑆|𝐼𝐼| ) SPIM – Dantzig-Wolfe Decomposition
𝑚𝑚
To get a lower bound for optimal costs and a
𝐿𝐿(𝑥𝑥, 𝜆𝜆) = 𝑓𝑓(𝑥𝑥) + ��𝑔𝑔𝑗𝑗 (𝑥𝑥) − 𝑏𝑏𝑗𝑗 � ∗ 𝜆𝜆𝑗𝑗 Output variables heuristic solution.
𝑗𝑗=1 1 𝑆𝑆
𝛽𝛽𝑖𝑖 (𝑆𝑆𝑖𝑖 ): Fill rate for SKU 𝑖𝑖. 𝛽𝛽𝑖𝑖 (𝑆𝑆𝑖𝑖 ) = 1 − ( ∗ 𝜌𝜌𝑖𝑖 𝑖𝑖 )/ 𝐾𝐾 ≔ {0,1,2 … }: Set of basestock policies for
𝑆𝑆𝑖𝑖 !
1
Lagrange Dual function:
𝑆𝑆
(∑𝑗𝑗=0
𝑖𝑖 𝑗𝑗
∗ 𝜌𝜌𝑖𝑖 ). Here, 𝜌𝜌𝑖𝑖 = 𝜇𝜇𝑖𝑖 𝑡𝑡𝑖𝑖 . Aggregate fill rate: each SKU 𝑖𝑖 ∈ 𝐼𝐼
𝑗𝑗!
𝐻𝐻(𝜆𝜆) = min[𝐿𝐿(𝑥𝑥, 𝜆𝜆)] 𝑚𝑚 𝑆𝑆𝑖𝑖𝑘𝑘 : Basestock level of policy 𝑘𝑘 for SKU 𝑖𝑖 (one
𝛽𝛽(𝑆𝑆) = ∑𝑖𝑖∈𝐼𝐼 � 𝑖𝑖� ∗ 𝛽𝛽𝑖𝑖 (𝑆𝑆𝑖𝑖 )
𝑀𝑀
can take 𝑆𝑆𝑖𝑖𝑘𝑘 = 𝑘𝑘)
Weak Duality 𝑥𝑥𝑖𝑖𝑘𝑘 ∈ {0,1}: Variable which indicates whether
Let 𝑥𝑥 ∗ be the optimal value of the optimization problem. 𝑊𝑊𝑖𝑖 (𝑆𝑆𝑖𝑖 ): Mean waiting time for demands for SKU 𝑖𝑖.
𝑊𝑊𝑖𝑖 (𝑆𝑆𝑖𝑖 ) = �1 − 𝛽𝛽𝑖𝑖 (𝑆𝑆𝑖𝑖 )� ∗ 𝑡𝑡𝑖𝑖𝑒𝑒𝑒𝑒 policy 𝑘𝑘 is chosen for SKU 𝑖𝑖 (𝑥𝑥𝑖𝑖𝑘𝑘 = 1) or not
Then, for 𝜆𝜆 ≥ 0, we have 𝑓𝑓(𝑥𝑥 ∗ ) ≥ 𝐻𝐻(𝜆𝜆)
(𝑥𝑥𝑖𝑖𝑘𝑘 = 0).

Strong Duality �𝑛𝑛 (𝑆𝑆): Aggregate mean waiting time for demands by
𝑊𝑊
If for a feasible solution 𝑥𝑥 and 𝜆𝜆 ≥ 0, 𝑓𝑓(𝑥𝑥) = 𝐻𝐻(𝜆𝜆), then �𝑛𝑛 (𝑆𝑆) = ∑𝑖𝑖∈𝐼𝐼 �𝑚𝑚𝑖𝑖,𝑛𝑛 � ∗ 𝑊𝑊𝑖𝑖 (𝑆𝑆𝑖𝑖 )
machine type 𝑛𝑛. 𝑊𝑊 Multi-location System with Lateral
𝑀𝑀𝑛𝑛
𝑥𝑥 is an optimal solution Transshipments
Output variables:
𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ): Expected total cost per time unit for SKU 𝑖𝑖.
Everett Result – The Everett results provides us with a 𝛽𝛽𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ): Fraction satisfied by LW 𝑗𝑗 itself
set of given conditions under which strong duality holds. 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ) ≔ 𝑐𝑐𝑖𝑖ℎ ∗ 𝑆𝑆𝑖𝑖 + 𝜇𝜇𝑖𝑖 �1 − 𝛽𝛽𝑖𝑖 (𝑆𝑆𝑖𝑖 )� ∗ 𝑐𝑐𝑖𝑖𝑒𝑒𝑒𝑒
If for a given 𝜆𝜆 ≥ 0, 𝑆𝑆(𝜆𝜆) minimizes 𝐿𝐿(𝑆𝑆, 𝜆𝜆), then 𝑆𝑆(𝜆𝜆) is 𝛼𝛼𝑖𝑖,𝑗𝑗,𝑘𝑘 (𝑆𝑆𝑖𝑖 ): Fraction of demand for SKU 𝑖𝑖 at LW
the optimal solution for Problem P. This means we have 𝐶𝐶(𝑆𝑆) = ∑𝑖𝑖∈𝐼𝐼 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ): Total average costs 𝑗𝑗 that is delivered from main LW 𝑘𝑘 via a lateral
the following: (1) 𝐸𝐸𝐸𝐸𝑂𝑂𝑜𝑜𝑜𝑜𝑜𝑜 ≥ 𝐸𝐸𝐸𝐸𝐸𝐸(𝑆𝑆(𝜆𝜆)), and (2) transshipment.
𝜆𝜆�𝐸𝐸𝐸𝐸𝐸𝐸�𝑆𝑆(𝜆𝜆)� − 𝐸𝐸𝐸𝐸𝑂𝑂𝑜𝑜𝑜𝑜𝑜𝑜 � = 0 Optimization Problem 𝐴𝐴𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ): Total fraction satisfied by a lateral
min[𝐶𝐶(𝑆𝑆)] transshipment, 𝐴𝐴𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ) = ∑𝑘𝑘∈𝐾𝐾\{𝑗𝑗} 𝛼𝛼𝑖𝑖,𝑗𝑗,𝑘𝑘 (𝑆𝑆𝑖𝑖 )
Poisson probability �𝑛𝑛𝑜𝑜𝑜𝑜𝑜𝑜 , 𝑛𝑛 ∈ ℕ
�𝑛𝑛 (𝑆𝑆) ≤ 𝑊𝑊
Subject to 𝑊𝑊 𝜃𝜃𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ): Fraction satisfied by an emergency
�𝜆𝜆𝑥𝑥 ∗ 𝑒𝑒 −𝜆𝜆 �
ℙ{𝑋𝑋 = 𝑥𝑥} = 𝑆𝑆𝑖𝑖 ∈ {0,1, … } for all 𝑖𝑖 ∈ 𝐼𝐼 shipment
𝑥𝑥!
𝐶𝐶𝑃𝑃 : Optimal costs of problem P
𝛽𝛽𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ) + 𝐴𝐴𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ) + 𝜃𝜃𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ) = 1
Basic Multi-Item, Single-Location Inventory
SPIM – Enumeration Formulas:
Model – Total investment
Lower bound for optimal basestock levels: 𝑊𝑊𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ): Mean waiting time for demands for
𝐶𝐶(𝑆𝑆) = � 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ) = � 𝑐𝑐𝑖𝑖𝑎𝑎 ∗ 𝑆𝑆𝑖𝑖 𝑆𝑆𝑖𝑖,𝑙𝑙𝑙𝑙 ≔ min[𝑆𝑆𝑖𝑖 ∈ ℕ0 |∆𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ) > 0] , 𝑖𝑖 ∈ 𝐼𝐼 SKU 𝑖𝑖 at LW 𝑗𝑗
𝑖𝑖∈𝐼𝐼 𝑖𝑖∈𝐼𝐼
Aggregate mean number of backorders in steady-state Lower bound for 𝑪𝑪𝑷𝑷 : 𝐶𝐶𝑃𝑃𝑙𝑙𝑙𝑙 ≔ ∑𝑖𝑖∈𝐼𝐼 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖,𝑙𝑙𝑙𝑙 ) 𝑊𝑊𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 ) = 𝑙𝑙𝑙𝑙𝑙𝑙
� 𝑡𝑡𝑗𝑗,𝑘𝑘 ∗ 𝛼𝛼𝑖𝑖,𝑗𝑗,𝑘𝑘 (𝑆𝑆𝑖𝑖 ) + 𝑡𝑡𝑗𝑗𝑒𝑒𝑒𝑒
𝐸𝐸𝐸𝐸𝐸𝐸(𝑆𝑆) = � 𝐸𝐸𝐸𝐸𝑂𝑂𝑖𝑖 (𝑆𝑆𝑖𝑖 ) Feasible solution 𝑘𝑘∈𝐾𝐾,𝑘𝑘≠𝑗𝑗
𝑜𝑜𝑜𝑜𝑜𝑜
�𝑚𝑚𝑚𝑚𝑚𝑚 �𝑛𝑛𝑜𝑜𝑜𝑜𝑜𝑜 �
𝑖𝑖∈𝐼𝐼 𝑊𝑊 ≔ 𝑚𝑚𝑚𝑚𝑛𝑛𝑛𝑛∈ℕ �𝑊𝑊 ∗ 𝜃𝜃𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 )
Backorder position 𝑜𝑜𝑜𝑜𝑜𝑜
�𝑚𝑚𝑚𝑚𝑚𝑚 �
𝑆𝑆𝑖𝑖 = min�𝑥𝑥 ≥ 𝑆𝑆𝑖𝑖.𝑙𝑙𝑙𝑙 �𝑊𝑊𝑖𝑖 (𝑥𝑥) ≤ 𝑊𝑊 �𝑛𝑛 (𝑆𝑆): Aggregate mean waiting time for group
𝑆𝑆𝑖𝑖 𝑊𝑊
𝑢𝑢𝑢𝑢
Upper bound for 𝑪𝑪𝑷𝑷 : 𝐶𝐶𝑃𝑃 = 𝐶𝐶(𝑆𝑆) 𝑛𝑛 ∈ 𝑁𝑁𝑗𝑗 , 𝑗𝑗 ∈ 𝐽𝐽
𝐸𝐸𝐸𝐸𝑂𝑂𝑖𝑖 (𝑆𝑆𝑖𝑖 ) = 𝑚𝑚𝑖𝑖 𝑡𝑡𝑖𝑖 − 𝑆𝑆𝑖𝑖 + �(𝑆𝑆𝑖𝑖 − 𝑥𝑥) ∗ ℙ{𝑋𝑋𝑖𝑖 = 𝑥𝑥}
𝒖𝒖𝒖𝒖
𝑪𝑪𝑷𝑷 − 𝑪𝑪𝒍𝒍𝒍𝒍 𝑚𝑚
𝑥𝑥=0 𝑷𝑷 : Amount that you use to make extra costs for �𝑛𝑛 (𝑆𝑆) = � 𝑖𝑖,𝑛𝑛 ∗ 𝑊𝑊𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 )
𝑊𝑊
SKUs compared to the costs under solution 𝑀𝑀𝑛𝑛
𝑖𝑖∈𝐼𝐼
�𝑆𝑆1,𝑙𝑙𝑙𝑙 , 𝑆𝑆2,𝑙𝑙𝑙𝑙 , 𝑆𝑆3,𝑙𝑙𝑙𝑙 �.
Lagrange Relaxation 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ): Expected total cost per time unit for
Upper bound for optimal basestock levels: SKU 𝑖𝑖
𝐿𝐿(𝑆𝑆, 𝜆𝜆) = � 𝐿𝐿𝑖𝑖 (𝑆𝑆𝑖𝑖 , 𝜆𝜆) − 𝜆𝜆 ∗ 𝐸𝐸𝐸𝐸𝑂𝑂𝑜𝑜𝑜𝑜𝑜𝑜 𝑆𝑆𝑖𝑖,𝑢𝑢𝑢𝑢
𝑖𝑖∈𝐼𝐼 𝑢𝑢𝑢𝑢
where ≔ max�𝑥𝑥 ≥ 𝑆𝑆𝑖𝑖,𝑙𝑙𝑙𝑙 �𝐶𝐶𝑖𝑖 (𝑥𝑥) − 𝐶𝐶𝑖𝑖 �𝑆𝑆𝑖𝑖,𝑙𝑙𝑙𝑙 � ≤ 𝐶𝐶𝑃𝑃 − 𝐶𝐶𝑃𝑃𝑙𝑙𝑙𝑙 � , 𝑖𝑖 ∈ 𝐼𝐼
= � 𝑐𝑐𝑖𝑖ℎ ∗ 𝑆𝑆𝑖𝑖,𝑗𝑗 + � 𝑀𝑀𝑖𝑖,𝑗𝑗 � � 𝑐𝑐𝑗𝑗,𝑘𝑘
𝑙𝑙𝑙𝑙𝑙𝑙

𝐿𝐿𝑖𝑖 (𝑆𝑆𝑖𝑖 , 𝜆𝜆) ≔ 𝑐𝑐𝑖𝑖𝑎𝑎 𝑆𝑆𝑖𝑖 + 𝜆𝜆 ∗ 𝐸𝐸𝐸𝐸𝑂𝑂𝑖𝑖 (𝑆𝑆𝑖𝑖 ) Search for the best solution among all solutions 𝑆𝑆 with 𝑗𝑗∈𝐽𝐽 𝑗𝑗∈𝐽𝐽 𝑘𝑘∈𝐾𝐾,𝑘𝑘≠𝑗𝑗
𝑆𝑆𝑖𝑖,𝑙𝑙𝑙𝑙 ≤ 𝑆𝑆𝑖𝑖 ≤ 𝑆𝑆𝑖𝑖,𝑢𝑢𝑢𝑢 for all 𝑖𝑖 ∈ 𝐼𝐼. This gives an optimal ∗ 𝛼𝛼𝑖𝑖,𝑗𝑗,𝑘𝑘 (𝑆𝑆𝑖𝑖 ) + 𝑐𝑐𝑗𝑗𝑒𝑒𝑒𝑒
solution 𝑆𝑆 ∗ and the optimal costs 𝐶𝐶𝑃𝑃 = 𝐶𝐶(𝑆𝑆 ∗ ).
Smallest stock level
∗ 𝜃𝜃𝑖𝑖,𝑗𝑗 (𝑆𝑆𝑖𝑖 )�
Smallest stock level for where Δ𝐿𝐿𝑖𝑖 (𝜆𝜆, 𝑆𝑆𝑖𝑖 ) > 0 is the
optimal solution. Smallest stock level where ℙ{𝑋𝑋𝑖𝑖 ≤
𝑆𝑆𝑖𝑖 } = (𝜆𝜆 − 𝑐𝑐𝑖𝑖𝑎𝑎 )/𝜆𝜆 is the optimal solution 𝐶𝐶(𝑆𝑆) = ∑𝑖𝑖∈𝐼𝐼 𝐶𝐶𝑖𝑖 (𝑆𝑆𝑖𝑖 ): Total average costs




1