Sect. 10.1.1: the Clark-Scarf decomposition — echelon order-up-to levels minimize the expected period cost of the two-level serial system
ProvedInventoryControl.clark_scarf_two_levelThe Clark-Scarf decomposition for a two-level serial system, the central result of Chapter 10.
Installation 1 faces normally distributed period demand (mean , standard deviation , independent across periods) and replenishes from installation 2, which replenishes from an outside supplier with infinite supply; lead-times are and periods, demand is backordered, and costs are echelon holding costs and a shortage cost per unit and period, with and . In an arbitrary period the total expected cost is determined by the echelon position chosen at installation 2 and the realized position at installation 1 a lead-time later, which is subject to and may depend on ; after the reallocation (10.4)-(10.5) it is .
Let be the newsboy level of Eq. (10.8), , and let minimize the total cost of Eq. (10.9). Then:
- for every and every allocation rule with (and finite expected cost),
- the echelon order-up-to policy , which sets and , attains .
In words: the optimal policy is an echelon-stock order-up-to policy at both installations, is found from a newsboy problem that does not involve installation 2 at all, and is then found by minimizing a convex function of one variable in which installation 2's inability to deliver appears as an induced shortage cost. This is the decomposition Clark and Scarf discovered, and the origin of the echelon-inventory measure. In Example 10.1 (, , , , , ) it gives and with total cost .
Formalization Note The theorem is the per-period decomposition the book derives; it does not model the infinite-horizon dynamics, in which the same stationary policy is applied in every period and is feasible because the outside supplier has infinite supply (the book's "obvious" step). Allocation rules are arbitrary functions of the realized lead-time demand with an explicit integrability hypothesis, since a rule with infinite expected cost is not a competitor. and are characterized rather than constructed; their existence for is established by the other items of this mission.
import Definitions.Def_InventoryControl_clarkScarf
namespace InventoryControl
theorem clark_scarf_two_level (e1 e2 b1 mu sigma : ℝ) (he1 : 0 ≤ e1) (he2 : 0 ≤ e2) (hb : 0 < b1)
(hs : 0 < sigma) (L1 L2 : ℕ) (S1 : ℝ)
(hS1 : ProbabilityTheory.cdf (ProbabilityTheory.gaussianReal 0 1)
((S1 - (L1 + 1) * mu) / (Real.sqrt (L1 + 1) * sigma)) = (e2 + b1) / (e1 + e2 + b1))
(S2 : ℝ) (hS2 : ∀ y2 : ℝ, csTotalCost e1 e2 b1 mu sigma L1 L2 S1 S2
≤ csTotalCost e1 e2 b1 mu sigma L1 L2 S1 y2) :
(∀ y2 : ℝ, ∀ a : ℝ → ℝ, (∀ u, a u ≤ y2 - u) →
MeasureTheory.Integrable (fun u => csStage1Cost e1 e2 b1 mu sigma L1 (a u))
(csDemand mu sigma L2) →
csTotalCost e1 e2 b1 mu sigma L1 L2 S1 S2
≤ ∫ u, (csStage2Cost e2 mu L2 y2 + csStage1Cost e1 e2 b1 mu sigma L1 (a u))
∂(csDemand mu sigma L2))
∧ csTotalCost e1 e2 b1 mu sigma L1 L2 S1 S2
= ∫ u, (csStage2Cost e2 mu L2 S2 + csStage1Cost e1 e2 b1 mu sigma L1 (min S1 (S2 - u)))
∂(csDemand mu sigma L2) := by sorry
end InventoryControl
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.