The deterministic FIFO policy (Definition 1)
Definitionowmr_fifo_policyFor a retailer with , let be a canonical optimum of its single-location problem with planning setup cost and lead time (cost , demand ), and let be a best half window of . The deterministic FIFO policy follows three rules.
- Retailer policies. Retailer uses whichever of and has the smaller augmented cost if , and base stock at a minimizer of if . Its fixed mirror center is a mirror center of the selected policy, and the base-stock level if .
- Requests and dispatch. Retailer applies its policy, in each period after the scheduled receipts, to its inventory position including outstanding requests, . Each positive order joins one FIFO queue of requests; after the supplier order, the warehouse fills requests in queue order from available stock, the last one possibly in part, and sends all portions for retailer in that period as one dispatch.
- Supplier orders. The warehouse orders with an policy that attains the supplier value , applied to the aggregate position .
Initialization (Appendix B). No orders or dispatches are placed until all prescribed pipelines have arrived, retaining warehouse stock, and then until every retailer position is at most its selected target . In the first period in which this holds, each retailer with receives one initial request of that size, and the three rules run from that period on.
The policy is an echelon stock policy with FIFO service; Theorem 1 bounds its long-run average cost.
Formalization Note The choices in the definition (the canonical optimum, the best half window, the selected pair, the mirror centers , and the supplier pair) are parameters c : FIFOChoice n, constrained by IsFIFOChoice N c; when the two candidates tie, either may be selected. Simultaneous requests join the queue in increasing retailer index, a fixed tie-breaking rule (retailer labels are arbitrary). With , the policy starts in the first period with in which, after the receipts, every retailer net inventory (its position, as nothing is in transit) is at most its target. The policy is a deterministic function of the initial state and the past demands.
import Definitions.Def_owmr_queue_engine
/-!
# The deterministic FIFO policy `π_FIFO` (Definition 1)
Source: M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse
Multi-Retailer Systems", Section 3, Definition 1, the paragraphs before it, and the
initialization in Appendix B (Step 1 of the proof of Proposition 2).
The definition involves choices (an optimal `(s,S)` pair satisfying the canonical conditions,
a minimizing half window, a mirror center, an optimal supplier `(s,S)` pair, and tie-breaking).
They are collected in `FIFOChoice`; `IsFIFOChoice` states the properties Definition 1 requires of
them. Simultaneous requests join the queue in increasing retailer index (a fixed tie-breaking
rule; retailer labels are arbitrary).
Initialization (Appendix B, Step 1): no orders or dispatches are placed until all prescribed
pipelines have arrived (the last can arrive in period `Tpipe - 1`, where
`Tpipe = max(L₀, max_i L_i)`), retaining warehouse stock, and then until every retailer position
`P_i` (= net inventory, as nothing is in transit) is at most its selected target `Γ_i = S_i`.
In the first period `t` with `Tpipe ≤ t + 1` in which, after the receipts, every `P_i ≤ Γ_i`,
the policy starts: each retailer with `Γ_i - P_i > 0` gets one initial request of that size,
after which the supplier rule and the queue run as in Definition 1 from that period on.
-/
open MeasureTheory
open scoped ENNReal NNReal
noncomputable section
namespace OWMR
variable {n : ℕ}
/-- The choices made in Definition 1: retailer `(s_i, S_i)` (base stock when `s_i = S_i`), mirror
centers `a_i`, and the supplier `(s₀, S₀)`. -/
structure FIFOChoice (n : ℕ) where
s : Fin n → ℝ
S : Fin n → ℝ
a : Fin n → ℝ
s0 : ℝ
S0 : ℝ
/-- The requirements of Definition 1 on the choices.
* (i) If `K_i > 0`: for some optimal `(ŝ_i, Ŝ_i)` satisfying the canonical conditions for the
single-location problem of retailer `i` with planning setup cost `5K_i/3` and lead time `L_i`,
and some half window `(s'_i, S'_i)` of `[ŝ_i, Ŝ_i]` with the smallest average holding and
backlog cost, retailer `i` uses whichever of the two has the smaller augmented cost (either one
in case of a tie), and `a_i` is a mirror center of the selected policy. If `K_i = 0`: base
stock (`s_i = S_i`) at a minimizer of `F_i`, with `a_i = S_i`.
* (iii) The supplier `(s₀, S₀)` policy attains the supplier value `J₀(K₀ + K_max)`. -/
def IsFIFOChoice (N : Network n) (c : FIFOChoice n) : Prop :=
(∀ i, 0 < N.K i →
∃ sh Sh s' S' : ℝ,
IsCanonicalOptimum (N.marginal i) (N.F i) (5 * N.K i / 3) sh Sh ∧
IsBestHalfWindow (N.marginal i) (N.F i) sh Sh s' S' ∧
((c.s i = sh ∧ c.S i = Sh ∧ N.augCost i sh Sh ≤ N.augCost i s' S') ∨
(c.s i = s' ∧ c.S i = S' ∧ N.augCost i s' S' ≤ N.augCost i sh Sh)) ∧
mirrorAvg (N.marginal i) N.h N.p (c.s i) (c.S i) (c.a i)
= mirrorCost (N.marginal i) N.h N.p (c.s i) (c.S i)) ∧
(∀ i, N.K i = 0 → c.s i = c.S i ∧ (∀ y, N.F i (c.S i) ≤ N.F i y) ∧ c.a i = c.S i) ∧
c.s0 ≤ c.S0 ∧
ssAvgCost N.aggregate N.fL0 (N.K0 + N.Kmax) c.s0 c.S0 = N.J0 (N.K0 + N.Kmax)
/-- The queue parameters of `π_FIFO`: every allocation ships at once, and the supplier position
uses the mirror centers `a_i`. -/
def FIFOChoice.params (c : FIFOChoice n) : EngParams n where
s := c.s
S := c.S
center := c.a
batch := fun _ => false
s0 := c.s0
S0 := c.S0
/-- One period of `π_FIFO` (including the initialization): returns the state before demand, the
supplier order, and the dispatches. -/
def fifoStep (N : Network n) (c : FIFOChoice n) (t : ℕ) (st0 : EngState n) :
EngState n × ℝ × (Fin n → ℝ) :=
let st := receive st0 t
if st.running then runStep N.L0 N.L c.params (fun _ _ _ _ _ => 0) t st
else if N.Tpipe ≤ t + 1 ∧ ∀ i, st.I i ≤ c.S i then
runStep N.L0 N.L c.params (fun _ _ _ _ _ => 0) t
(startWith st t (fun i => c.S i - st.I i) (fun _ => 0))
else (st, 0, 0)
/-- The state of `π_FIFO` at the start of period `t` along the demand sequence `d`. -/
def fifoRun (N : Network n) (x : InitState n) (c : FIFOChoice n) (d : ℕ → DemandVec n) :
ℕ → EngState n
| 0 => initEngState N x
| t + 1 => applyDemand (fifoStep N c t (fifoRun N x c d t)).1 (d t)
/-- The deterministic FIFO policy `π_FIFO` of Definition 1, from the initial state `x`. -/
def fifoPolicy (N : Network n) (x : InitState n) (c : FIFOChoice n) : DetPolicy n where
order t d := (fifoStep N c t (fifoRun N x c d t)).2.1
dispatch t d := (fifoStep N c t (fifoRun N x c d t)).2.2
end OWMR
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Read-back of Def_owmr_fifo_policy.lean
Overview. The file defines six things:
- a record of real parameters (
FIFOChoice); - a predicate relating to a network (
IsFIFOChoice); - the conversion of into parameters of a queue-based simulation engine (
FIFOChoice.params); - one period of that engine, with a start rule (
fifoStep); - the engine's trajectory along a demand path (
fifoRun); - the deterministic policy that reads its order and dispatch quantities off that trajectory (
fifoPolicy).
The last four accept every , and none of them requires IsFIFOChoice. No declaration in the file assumes sign, moment or validity conditions on the network or on the initial state.
Notation and the imported definitions that are used
Indices and conventions. is an implicit argument of every declaration. Retailers are written , which is the code's index set shifted by one. "In increasing order of " refers to this order. There are no retailers when . Write . Every subtraction below is between real numbers: demands are nonnegative reals, converted to reals before they are subtracted. Natural numbers (lead times, period indices) are only added and compared, so no truncated subtraction occurs anywhere.
Network. A network consists of natural numbers , a probability measure on , and real numbers , , , . The following are derived from it.
- is the law of the -th coordinate under . is the law of the coordinate sum under , which is the point mass at when . Both are probability measures on .
- . When , , by the convention for an empty supremum of reals.
- , which is when .
For ,
where is the sum of independent draws from and is the sum of independent draws from . In particular when .
These are Bochner integrals, which are by convention when the integrand is not integrable. For this happens, for all at once, exactly when and has infinite mean, and then . For it happens exactly when , and has infinite mean, and then .
Single-location functionals. Let be a probability measure on , let , let , and let be i.i.d. with law . The recursion is
Each per-period cost is truncated by before summation. All of the following take values in :
Here are the network's, is ssAvgCost, and , are mirrorAvg, mirrorCost.
The optimal value (slValue) is an infimum taken over:
- all auxiliary probability spaces ;
- all rules , with , , , that are jointly measurable in and depend on only through .
The quantity minimized is
with independent of the demands, so the level starts at .
Three further notions:
- (
IsCanonicalOptimum) means all of the following: ; ; ; ; and for every . Since is finite, this requires . - (
IsBestHalfWindow) means all of the following: ; ; and for all reals with , and . The fixed cost is on both sides of this comparison. - (
augCost) and (J0).
FIFOChoice n. A choice is a record of three real vectors , , indexed by the retailers, and two reals , . The record imposes no relation among its entries. For example, or are allowed.
IsFIFOChoice N c. This is the proposition that the following four conditions hold simultaneously.
- For every retailer with there exist reals , which may depend on , such that:
- holds;
- holds;
- either , and , or , and ;
- , that is, attains the infimum over .
- For every retailer with : ; for every (a comparison of real values, with no truncation); and .
- .
- . This is an equality in , so it holds when both sides are .
The fixed cost is inside CO, inside , and inside BHW.
The predicate does not determine from , for these reasons:
- When , including the case where both are infinite, either alternative is allowed.
- The witnesses are only required to exist.
- There may be several minimizing , several minimizers of , and several pairs satisfying (4).
Retailers with are not excluded, since is an arbitrary real. They fall under neither (1) nor (2), so their are unconstrained.
The predicate may be unsatisfiable:
- (1) is impossible if for some with .
- (1) needs a canonical optimum, an attained best half window, and an attained infimum over .
- (2) needs an attained global minimum of .
- (4) needs some that achieves the equality.
The file asserts no such existence and selects no choice. If by the Bochner convention, every real minimizes . For , conditions (1) and (2) are vacuous, , and is the point mass at , so only (3) and (4), with fixed cost , remain. No other declaration in the file refers to this predicate.
FIFOChoice.params c. These are the engine parameters obtained from :
- the per-retailer numbers and ;
- a per-retailer "center", equal to ;
- a per-retailer batch flag, set to false for every retailer;
- the numbers and .
How each parameter enters is described under fifoStep.
The flags matter only in that step. With flag false, a request's shipment in a period is its whole allocated-but-unshipped amount, and its offset is . With flag true, which never occurs here, shipment would wait until the allocated amount crosses thresholds that depend on the request's size and on an offset produced by an "offset rule". Consequently, in this file all offsets are and the offset rule is never evaluated.
fifoStep N c t σ. An engine state consists of:
- a flag, running or not;
- a real (stock);
- reals (retailer levels, possibly negative);
- real sequences and , (supplier and retailer pipelines, indexed by the period in which they are received);
- a finite ordered list of requests (the queue), where each request has a retailer , a real size , real allocated and shipped amounts and , an offset, and a creation period;
- a counter .
Given , , a period and a state , the step returns a triple: a new state, an order quantity , and a dispatch vector . It works as follows.
- Receipt: and for all . Nothing else changes. Call the result .
- If is running, apply the engine period (below) to and return its result.
- Otherwise, if and for every (levels after the receipt), the engine starts:
- the flag is set to running;
- for each with , in increasing order of , a request is appended to the end of with retailer , size , , offset , and creation period ;
- is unchanged;
- is then applied to this state in the same period , and its result is returned.
- Otherwise, the step returns : the received state, order , and the zero dispatch vector.
The engine period uses the parameters of FIFOChoice.params c and the constant- offset rule. It has two parts.
(A) Requests and order. All quantities here are computed from the state as it enters . For each ,
and if , otherwise . Each with gets one new request of size , with , offset and creation period . These requests are appended to the end of , after all existing requests, in increasing order of , and grows by their number. The order is
Note that pos contains no unallocated amounts . If , then immediately. Otherwise .
(B) FIFO allocation and shipment. Start from , which includes if . Go through from the first request to the last. For each request :
- put ;
- set ;
- ship , using the updated ;
- set and .
The dispatch is the total shipped on requests with retailer , or if there are none. Then:
- ;
- requests with stay in in their order, and the rest are removed;
- for each , if , otherwise .
returns the resulting state, and .
fifoRun N x c d. The inputs are an initial state and a demand path with . The initial state consists of reals and and real sequences and . The run is the sequence of engine states defined by:
- : not running; ; ; for and for ; for and for ; empty queue; .
- : take the state returned by
fifoStep, then set for every . Nothing else changes.
So is the state at the beginning of period , before that period's receipt, and it depends on only through . Only the entries with and with of the initial pipelines are ever used, and none are used when the corresponding lead time is . is not required to be nonnegative.
fifoPolicy N x c. This is a deterministic policy: a pair of functions of the period and the whole demand path , with no auxiliary random input. Its order at is the returned by fifoStep, where comes from fifoRun. Its dispatch vector at is the returned by the same step. Both depend on only through , and both are defined for every and every . Unfolding along the run gives the following.
Invariants.
- The flag is false in , is set only by the start branch, and is never reset.
- Requests are created with , and (B) sets for every queued request. So whenever (A) is evaluated, for every queued . Consequently the sums in and in pos vanish, each shipment in (B) equals , and is the unshipped remainder.
- Since , a request leaves the queue exactly when it is fully shipped.
- The counter , the offsets and the creation periods never affect or .
Before the start. Only receipts and demand subtractions occur. The queue is empty, the pipelines hold only the initial entries, and order and dispatch are . After the receipt in period ,
Start period. Once , every initial pipeline entry has been received. The start period is therefore
The smallest possible value of is . If no such exists, the policy never starts, and every order and every dispatch is in every period.
In period , let and .
- Start requests of size are queued for each with .
- In (A), all pipeline sums are : their indices are at least , beyond the initial entries, and nothing has been sent before . The start requests make , so and no further request is created.
- The order is if , and otherwise, where
- In (B), the started retailers are served in increasing order of with , where is what remains of after the earlier retailers. The other retailers get . Unfilled remainders stay in the queue.
After the start. Every period is a receipt followed by :
- For each , is , plus the retailer- pipeline due in periods , plus the unshipped remainders of 's queued requests. A new request of size is created for each with and .
- pos is , plus the supplier pipeline due in periods , plus . The order is when , and otherwise.
- The stock is then allocated FIFO as in (B).
Orderings and ties.
- The queue is ordered by creation period and, within a period, by increasing . In period only start requests are created.
- Stock is allocated greedily from the front of the queue. Each request takes as much as possible before the next one is considered, and partially served requests keep their place.
- Every trigger is a weak inequality: , , , .
- A request is created only when its size is strictly positive.
Degenerate cases.
- No sign conditions are imposed, so the arithmetic is exactly as written.
- If , the order is negative whenever .
- The stock entering (B) can be negative, through , through negative initial pipeline entries, or through a negative . If it is negative and the queue is nonempty, the first queued request receives equal to that stock, which is a negative dispatch to its retailer, and the stock becomes . If the queue is empty, the stock stays negative.
- If , the initial supplier pipeline is ignored and the pipeline sum in pos is empty. enters the stock before (B) of the same period, so it can be dispatched in that period.
- If , retailer 's initial pipeline is ignored and its pipeline sum is empty. is added to in the same period, before that period's demand is subtracted.
- If , for example when all lead times are , the time condition holds from and only the level condition decides the start.
- If :
- ;
- the level condition is vacuous, so ;
- the dispatch vector is the empty vector;
- ;
- the stock is never drawn down.