Warehouse request queue: FIFO allocation and threshold dispatch
Definitionowmr_queue_engineThis definition encodes the period-by-period mechanics shared by the FIFO policy (Definition 1) and the consolidation policy (Definition 2) once they have started. In each period , after the scheduled receipts:
- each retailer applies its rule to its inventory position including outstanding requests, , where is its net inventory plus stock in transit to it, the unallocated quantity of its requests, and its reserve, the stock allocated to its requests but still held at the warehouse; if it requests , and positive requests join the end of one first-in, first-out queue, simultaneous requests in increasing retailer index;
- the warehouse applies its rule to , where is warehouse stock, supplier stock in transit, and fixed centers; the order arrives periods later (at once if ), and each new request of a batch retailer receives an offset from an offset rule;
- the unallocated warehouse stock is allocated to the requests in queue order, the last one possibly in part;
- a request of a non-batch retailer ships each allocation at once, while a request of a batch retailer, of size , ships its whole reserve in a period in which its cumulative allocation rises to or past , rises to or past when , or reaches ; all portions sent to one retailer in a period form one dispatch, which arrives periods later (at once if );
- demand occurs.
The state also defines the starting step: the policy may append initial requests of prescribed sizes before running these rules.
Formalization Note The state records the unallocated warehouse stock, the retailer net inventories, the scheduled arrivals by period, and the queue, where each request carries its retailer, size, cumulative allocation, shipped quantity, offset, and creation period. Initial requests are not ordinary requests; ordinary requests are indexed in creation order. ; every prescribed pipeline quantity arrives by period .
import Definitions.Def_owmr_single_location
/-!
# The warehouse request queue shared by the FIFO and consolidation policies
Source: M. Hu, "A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse
Multi-Retailer Systems": Definition 1 (ii)–(iii) (FIFO policy), Definition 2 (ii)–(iv)
(consolidation policy), Section 5.1, and Appendix C.2.
Both policies run the same mechanism once started. In each period `t`, after the scheduled
receipts:
1. each retailer `i` applies its `(s_i, S_i)` rule to its inventory position including
outstanding requests, `P̂_i = P_i + Δ_i + R_i` (`P_i`: net inventory plus stock in transit to
`i`; `Δ_i`: unallocated quantity of its requests; `R_i`: reserve, i.e. stock allocated to its
requests but still held at the warehouse); if `P̂_i ≤ s_i` it requests `S_i - P̂_i`, and a
positive request joins the end of one FIFO queue (requests of one period in increasing
retailer index);
2. the warehouse applies its `(s₀, S₀)` rule to `W + O + ∑_i (P_i - c_i)` (`W`: warehouse stock,
`O`: supplier stock in transit, `c_i`: the retailer centers); an order arrives `L₀` periods
later (at once if `L₀ = 0`);
3. the unallocated warehouse stock is allocated to the requests in queue order, the last one
possibly in part;
4. a request of a non-batch retailer ships every allocation at once; a request of a batch
retailer, of size `Q` and offset `ϑ`, ships its whole reserve in a period in which its
cumulative allocation rises to or past a dispatch threshold (`3Qϑ/4`, and also
`3Q(1+ϑ)/4` if `ϑ < 1/3`) or reaches `Q`; all portions sent to one retailer in a period form
one dispatch, which arrives `L_i` periods later (at once if `L_i = 0`);
5. demand occurs.
-/
open MeasureTheory
open scoped ENNReal NNReal
noncomputable section
namespace OWMR
variable {n : ℕ}
/-- A retailer request in the warehouse queue. -/
structure Req (n : ℕ) where
/-- requesting retailer -/
ret : Fin n
/-- request size `Q` -/
size : ℝ
/-- cumulative allocation -/
alloc : ℝ
/-- quantity shipped so far -/
shipped : ℝ
/-- offset `ϑ` (used only for requests of batch retailers) -/
offset : ℝ
/-- creation period -/
born : ℕ
/-- State of a policy at the start of a period, before receipts. -/
structure EngState (n : ℕ) where
/-- whether the policy has started (preparation finished) -/
running : Bool
/-- unallocated warehouse stock -/
Wbar : ℝ
/-- retailer net inventories -/
I : Fin n → ℝ
/-- scheduled supplier arrivals, by arrival period -/
supPipe : ℕ → ℝ
/-- scheduled arrivals at each retailer, by arrival period -/
retPipe : Fin n → ℕ → ℝ
/-- FIFO queue of requests (head first) -/
queue : List (Req n)
/-- number of ordinary requests created so far -/
nOrd : ℕ
/-- Parameters of the queue mechanism: retailer rules `(s_i, S_i)`, centers `c_i` in the supplier
position, batch flags, and the supplier rule `(s₀, S₀)`. -/
structure EngParams (n : ℕ) where
s : Fin n → ℝ
S : Fin n → ℝ
center : Fin n → ℝ
batch : Fin n → Bool
s0 : ℝ
S0 : ℝ
/-- An offset rule: given the state at creation, the period, the ordinary-request index `j`
(starting at `1`), the retailer, and the request size, returns the offset `ϑ`. -/
abbrev OffsetRule (n : ℕ) := EngState n → ℕ → ℕ → Fin n → ℝ → ℝ
/-- The initial engine state for a prescribed initial state. -/
def initEngState (N : Network n) (x : InitState n) : EngState n where
running := false
Wbar := x.W
I := x.I
supPipe := fun t => if t < N.L0 then x.supPipe t else 0
retPipe := fun i t => if t < N.L i then x.retPipe i t else 0
queue := []
nOrd := 0
/-- Scheduled receipts of period `t`. -/
def receive (st : EngState n) (t : ℕ) : EngState n :=
{ st with Wbar := st.Wbar + st.supPipe t, I := fun i => st.I i + st.retPipe i t }
/-- Demand of period `t`. -/
def applyDemand (st : EngState n) (dt : DemandVec n) : EngState n :=
{ st with I := fun i => st.I i - (dt i : ℝ) }
/-- Stock in transit to retailer `i` after the receipts of period `t`. -/
def inTransit (L : Fin n → ℕ) (st : EngState n) (t : ℕ) (i : Fin n) : ℝ :=
∑ k ∈ Finset.range (L i), st.retPipe i (t + 1 + k)
/-- Supplier stock in transit after the receipts of period `t`. -/
def supInTransit (L0 : ℕ) (st : EngState n) (t : ℕ) : ℝ :=
∑ k ∈ Finset.range L0, st.supPipe (t + 1 + k)
/-- `Δ_i`: unallocated quantity of retailer `i`'s requests. -/
def unalloc (st : EngState n) (i : Fin n) : ℝ :=
((st.queue.filter (fun r => r.ret = i)).map (fun r => r.size - r.alloc)).sum
/-- `R_i`: reserve of retailer `i`'s requests (allocated, not yet shipped). -/
def reserve (st : EngState n) (i : Fin n) : ℝ :=
((st.queue.filter (fun r => r.ret = i)).map (fun r => r.alloc - r.shipped)).sum
/-- `P_i`: net inventory plus stock in transit to retailer `i`. -/
def physPos (L : Fin n → ℕ) (st : EngState n) (t : ℕ) (i : Fin n) : ℝ :=
st.I i + inTransit L st t i
/-- `P̂_i = P_i + Δ_i + R_i`: inventory position including outstanding requests. -/
def phat (L : Fin n → ℕ) (st : EngState n) (t : ℕ) (i : Fin n) : ℝ :=
physPos L st t i + unalloc st i + reserve st i
/-- Retailer `i`'s request in period `t` under its `(s_i, S_i)` rule. -/
def reqSize (L : Fin n → ℕ) (P : EngParams n) (st : EngState n) (t : ℕ) (i : Fin n) : ℝ :=
if phat L st t i ≤ P.s i then P.S i - phat L st t i else 0
/-- Steps 1–2 of a running period (after receipts): retailer requests, the supplier order, and
the offsets of the new requests. Returns the state at creation (before allocation) and the
supplier order. -/
def phaseA (L0 : ℕ) (L : Fin n → ℕ) (P : EngParams n) (rule : OffsetRule n) (t : ℕ)
(st : EngState n) : EngState n × ℝ :=
let rs := (List.finRange n).filter (fun i => 0 < reqSize L P st t i)
let pos := st.Wbar + ∑ i, reserve st i + supInTransit L0 st t
+ ∑ i, (physPos L st t i - P.center i)
let q0 := if pos ≤ P.s0 then P.S0 - pos else 0
let mk : Fin n → ℝ → Req n := fun i θ =>
{ ret := i, size := reqSize L P st t i, alloc := 0, shipped := 0, offset := θ, born := t }
let st1 : EngState n :=
{ st with
Wbar := if L0 = 0 then st.Wbar + q0 else st.Wbar
supPipe := if L0 = 0 then st.supPipe
else Function.update st.supPipe (t + L0) (st.supPipe (t + L0) + q0)
queue := st.queue ++ rs.map (fun i => mk i 0)
nOrd := st.nOrd + rs.length }
let newReqs := rs.mapIdx (fun k i =>
mk i (if P.batch i then rule st1 t (st.nOrd + k + 1) i (reqSize L P st t i) else 0))
({ st1 with queue := st.queue ++ newReqs }, q0)
/-- Whether the cumulative allocation of a batch request of size `Q` and offset `ϑ`, moving from
`prev` to `new` in one period, rises to or past a dispatch threshold (`3Qϑ/4`, and `3Q(1+ϑ)/4`
if `ϑ < 1/3`) or reaches `Q`. -/
abbrev crossesThreshold (Q θ prev new : ℝ) : Prop :=
(prev < 3 * Q / 4 * θ ∧ 3 * Q / 4 * θ ≤ new) ∨
(θ < 1 / 3 ∧ prev < 3 * Q / 4 * (1 + θ) ∧ 3 * Q / 4 * (1 + θ) ≤ new) ∨
(prev < Q ∧ new = Q)
/-- FIFO allocation of the unallocated stock `w` and the resulting shipments; returns the updated
queue, the remaining unallocated stock, and the quantity shipped to each retailer. -/
def serve (batch : Fin n → Bool) : List (Req n) → ℝ → List (Req n) × ℝ × (Fin n → ℝ)
| [], w => ([], w, 0)
| r :: rs, w =>
let a := min (r.size - r.alloc) w
let r1 : Req n := { r with alloc := r.alloc + a }
let ship : ℝ :=
if batch r.ret = false ∨ crossesThreshold r.size r.offset r.alloc r1.alloc then
r1.alloc - r1.shipped else 0
let rest := serve batch rs (w - a)
({ r1 with shipped := r1.shipped + ship } :: rest.1, rest.2.1,
rest.2.2 + Pi.single r.ret ship)
/-- Dispatch `q` in period `t`: arrives at once if `L_i = 0`, otherwise `L_i` periods later. -/
def sendOut (L : Fin n → ℕ) (t : ℕ) (q : Fin n → ℝ) (st : EngState n) : EngState n :=
{ st with
I := fun i => if L i = 0 then st.I i + q i else st.I i
retPipe := fun i => if L i = 0 then st.retPipe i
else Function.update (st.retPipe i) (t + L i) (st.retPipe i (t + L i) + q i) }
/-- Steps 3–4 of a running period: allocation and dispatch. Fully shipped requests leave the
queue. Returns the new state and the dispatches. -/
def phaseB (L : Fin n → ℕ) (P : EngParams n) (t : ℕ) (st : EngState n) :
EngState n × (Fin n → ℝ) :=
let res := serve P.batch st.queue st.Wbar
(sendOut L t res.2.2
{ st with Wbar := res.2.1, queue := res.1.filter (fun r => r.shipped < r.size) }, res.2.2)
/-- A running period after receipts: returns the state before demand, the supplier order, and
the dispatches. -/
def runStep (L0 : ℕ) (L : Fin n → ℕ) (P : EngParams n) (rule : OffsetRule n) (t : ℕ)
(st : EngState n) : EngState n × ℝ × (Fin n → ℝ) :=
let a := phaseA L0 L P rule t st
let b := phaseB L P t a.1
(b.1, a.2, b.2)
/-- Start the policy: append initial requests of the given sizes (the positive ones, in
increasing retailer index), with the given offsets; initial requests are not ordinary requests. -/
def startWith (st : EngState n) (t : ℕ) (sizes θ0 : Fin n → ℝ) : EngState n :=
{ st with
running := true
queue := st.queue ++ ((List.finRange n).filter (fun i => 0 < sizes i)).map (fun i =>
{ ret := i, size := sizes i, alloc := 0, shipped := 0, offset := θ0 i, born := t }) }
/-- The period by which every prescribed pipeline has arrived: `max(L₀, max_i L_i)`. -/
def Network.Tpipe (N : Network n) : ℕ := max N.L0 (Finset.univ.sup N.L)
end OWMR
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Conventions. Every declaration below has an implicit natural-number parameter (the case is allowed), and carries its usual increasing order. Lists are finite sequences, read from first to last entry. The scalars named L0, s0, S0 are written , , . To keep them apart from entries at index , the values of the functions , , on are written , , . All real-valued data are unrestricted reals, since no sign or ordering condition appears anywhere in the file. The file contains no natural-number subtraction: all index arithmetic (, , , , ) is addition. is the vector with entry at and elsewhere.
Imported notions used. A network is a record that contains a natural number and a function . It also has components this file never uses: a probability measure on , real numbers named K0, h, p, and real functions named K, H on . An initial state is a record of a real number , a vector , a function , and functions for . The imported validity predicate for initial states (nonnegativity of and of both pipe functions) is not assumed anywhere in this file. A demand vector is an element .
Req. A request is a record with these fields: an index , four real numbers , , , , and a natural number . No relation among the fields is imposed; for example, is not required. When no request exists, because would have to lie in the empty set , so every list of requests is empty. Declarations in this file write the field but never read it.
EngState. A state is a record of the following fields:
- a Boolean flag ;
- a real number (field Wbar);
- a vector ;
- a function (field supPipe);
- for each , a function (field retPipe);
- a list of requests;
- a natural number .
No constraints are imposed. In this file, initEngState sets the flag to false and startWith sets it to true; nothing reads it. Only phaseA reads and increases .
EngParams. A parameter record consists of:
- three functions (fields s, S, center);
- a function (field batch);
- two real numbers , .
No constraints are imposed: neither nor is required. Within the file, and enter only through reqSize, only through the quantity of phaseA, and only through of phaseA, and through phaseA and serve.
OffsetRule. An offset rule is an arbitrary function . It assigns a real number to every state , pair of natural numbers and , index and real number . No property of is required.
initEngState. For a network and an initial state , it returns the state with , , , an empty queue and . Using and of , the pipe functions are
Both comparisons are strict, so the values of at indices (resp. ) are discarded. If then , and if then . No other component of is used.
receive and applyDemand. returns with replaced by and each replaced by . It does not modify the functions and : their entries at index are not reset to . All other fields are unchanged. For a demand vector , returns with each replaced by and nothing else changed. There is no truncation at , so may become negative. No other declaration in this file calls either function; in particular, runStep does not use them.
inTransit, supInTransit, unalloc, reserve, physPos, phat. Fix , , a state , and . The two transit sums are
These windows exclude index itself. Each sum is when , resp. . The two queue sums are
They run over the queue entries whose index is , counted with multiplicity. Each is if there is no such entry, and the summands may be negative. Finally, and
reqSize. With , , , , as above, if (non-strict), and otherwise. The first branch is not clipped: when , and when . Hence exactly when and .
phaseA. Applied to , it returns a pair made of a state and a real number. It is built in the following order, and steps 1 to 3 read only the input state .
- Let be the list of all , in increasing order, with (strict). Here is the size from
reqSize: when , and otherwise, where involves the entire queue of . The length is , and whenever . - Let
The second term is , which covers every queue entry. The third term is added once, outside the sums over . The unallocated amounts do not enter , and neither do the requests created in this call. 3. Let if (non-strict), and otherwise. It is not clipped, so when . 4. Form an intermediate state from as follows. The amount is added whatever its sign.
- If , replace by and leave unchanged.
- If , leave unchanged and add to the single entry ; all other entries stay the same.
- Append requests to the end of , for in this order. Request has index , size , alloc , shipped , offset and born .
- Set .
The fields , and are unchanged. 5. For (the position in the list of step 1, counted from ), set
The rule is called only for indices with . Its second argument is . Its third argument uses the input count (not ) and runs through . Every call receives the same state . That state already reflects the update by from step 4 and the count , and it holds all new requests with offset , not the offsets being computed. The last argument is the size computed from . 6. The output state is with its queue replaced by followed by requests, for in this order. Request has index , size , alloc , shipped , offset and born . The offset- copies from step 4 do not remain. The output number is .
So, relative to , the output state differs only in four places:
- , when ;
- , when ;
- the appended requests, each of strictly positive size;
- , which increases by .
When , the queue and are unchanged and is never called. When , . The numbers and are explicit arguments here, and nothing ties them to the and of any network.
crossesThreshold. For real numbers , , , , it is the statement
In the first two disjuncts, the comparisons with are strict and those with are non-strict. The third disjunct requires and the exact equality , with itself rather than . The condition is strict, with the real number. No sign or range condition is placed on or . Each disjunct implies , so the statement is false whenever .
serve. Its inputs are , a list of requests and a real number . returns a triple: a list of requests, a real number, and a vector in . For the empty list it returns the empty list, and . Otherwise it treats the entries from first to last, passing on a remainder. Start with , and for set
Then if or holds, and otherwise. Finally . The three outputs are:
- the list , where is with alloc replaced by and shipped by (index, size, offset and born unchanged), in the same order and with nothing removed;
- the real number ;
- the vector , so is the sum of over the entries with index .
Further details:
- The remainder is reduced by the allocations , not by the amounts .
- The threshold test uses and . It compares alloc before this call's allocation () with alloc after it ().
- When shipping is triggered, is the whole difference , not just . This includes amounts allocated in earlier calls and not yet shipped.
- For an index with the test is skipped, and after every call.
- If , then , alloc becomes exactly , and . If in addition , the third disjunct of the threshold test holds, so the entry ships .
- If , then and . When , this is a partial allocation of the whole remainder.
- There is no early stop. While the remainder is , each entry with gets and keeps its alloc, and the remainder stays . Since , such an entry fails the threshold test. It therefore ships if , and ships its outstanding if .
- Nothing is clipped at . If or , then can be negative, alloc decreases, and . For example, with and , alloc drops to and the positive remainder passes to later entries. can also be negative, when shipping is triggered and .
sendOut. For , , a vector and a state , it returns modified separately for each . If , is replaced by and is unchanged. If , is unchanged and is added to the single entry , with all other entries unchanged. , , the queue, and are unchanged. There is no sign condition on .
phaseB. Applied to , it returns a pair made of a state and a vector in . Let , with the flag function of . Thus the queue is served in its stored order, starting from the amount . The output state is obtained from in three steps:
- Set , that is, minus the total allocation .
- Replace the queue by the entries of with (strict), preserving their order. Entries with are removed, and all others are kept regardless of their alloc.
- Apply to the result.
The output vector is . In particular, if an entry's alloc rises in this call from below its size to exactly its size, it gets and is removed. , and are not changed. Only is used from , and enters only as the index in sendOut. If the queue is empty, and the queue stay as they are, , and sendOut changes nothing numerically.
runStep. Applied to , it returns the triple , where and . Consequently:
phaseBserves the queue of , which ends with the requests thatphaseAcreated in the same call, so these are served after all older entries.- Serving starts from , which includes when and does not when .
- When , is added to within the same call.
runStepdoes not callreceiveorapplyDemand, neither reads nor changes , and uses the same in both phases.
Indices relative to : phaseA writes at , and phaseB writes at . These are the last indices of the windows and that the transit sums above add up at the same . receive at index reads the entries at .
startWith. For a state , and functions , it returns with set to true and with requests appended at the end of the queue. There is one request for each with (strict), in increasing order of . It has index , size , alloc , shipped , offset and born . is not increased, and , , and are unchanged. No offset rule or flag is consulted: the offsets are used as given, for every . If no is positive (in particular if ), only changes.
Network.Tpipe. For a network , it is the natural number , using the and of . The inner maximum over the empty index set is , so for it equals . No other declaration in this file uses it.