Optimal and Order-optimal Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Optimal and Order-optimal Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Optimal and Order-optimal Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment Xi Chen∗

arXiv:2605.25888v1 [cs.LG] 25 May 2026

Leonard N. Stern School of Business, New York University, New York, NY 10012, USA, [email protected]

Yuze Chen∗ Qiuzhen College, Tsinghua University, Beijing 100084, China, [email protected]

Ziyi Chen∗ Qiuzhen College, Tsinghua University, Beijing 100084, China, [email protected]

Yuan Zhou∗ Yau Mathematical Sciences Center & Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China, [email protected]

We study how an e-commerce firm should make real-time fulfillment decisions in a two-layer distribution network when multi-item customer orders arrive sequentially and future demand is unknown. The central managerial tension is whether to use scarce front distribution center (FDC) inventory to save current fulfillment cost or preserve that inventory for future orders that may be more valuable to serve locally. We formulate an adversarial online model with multiple FDCs, one regional distribution center (RDC), multi-unit multi-item orders, and item-specific and time-varying variable costs. Our theoretical objective is to characterize when simple, interpretable, and implementable fulfillment rules can perform nearly as well as an optimal clairvoyant planner. We develop a family of Gated Priority-based Greedy policies, derive competitive-ratio guarantees under both time-varying and time-invariant cost structures, and establish matching or near-matching lower bounds for any online algorithm. Numerical experiments show that the proposed policies perform strongly relative to generalized myopic and forecast-based benchmarks. The analysis yields managerial guidance on when local inventory should be protected, when splitting orders is worth the fixed-cost burden, and how the relative magnitudes of fixed and variable costs determine the value of more sophisticated optimization. Key words : e-commerce; two-layer multi-item order fulfillment; online decision-making; competitive ratio; gated priority-based greedy policy

Introduction

The rapid growth of e-commerce has made order fulfillment a central operational challenge in modern retail. Large online platforms process massive volumes of orders and must do so cost-effectively across geographically distributed inventories and customer destinations. Fulfillment decisions therefore play a direct role in shaping operational efficiency and profitability. ∗

Author names listed in alphabetical order. 1

E-commerce fulfillment is particularly challenging because of three defining features. First, customer orders often contain multiple items with heterogeneous cost and inventory characteristics, which requires the firm to make coordinated fulfillment decisions across different products within the same order. Second, fulfillment costs are only partially stable over time: although the fixed cost of using a distribution center may remain constant over the selling horizon, per-unit variable costs may vary across orders over time because different orders are shipped to different destinations, and may also be affected by seasonality, promotions, congestion, and other changing operating conditions. Third, firms often operate a two-layer fulfillment network with multiple front distribution centers (FDCs) and a regional distribution center (RDC) (Shen et al. 2024). In such networks, different FDCs may offer different cost advantages for the same order depending on the geographic match between fulfillment locations and customer destinations, with these differences arising primarily through destination-dependent per-unit variable costs rather than fixed activation costs. At the same time, each FDC holds only limited inventory. The RDC, in contrast, carries deeper inventory and provides a reliable fallback option, although usually at a higher fulfillment cost. Together, these three features create a fulfillment environment that is substantially more complex than the one faced in traditional store-based retail. These operational features give rise to a dynamic two-layer multi-item order fulfillment problem. For each arriving order, the firm must decide which location should supply each item, taking into account current inventory availability, the fixed cost of using fulfillment locations, the variable cost of assigning items across locations, and the future option value of scarce FDC inventory. Because the relative cost of using an FDC depends on the destination of the order, the firm must also account for the geographic match between inventory locations and demand locations. The core tension is intertemporal: allocating FDC inventory to reduce current fulfillment cost may diminish the firm’s ability to fulfill future orders at low cost. The problem is also computationally challenging. When an order contains multiple items and the network includes more than one FDC, the set of feasible fulfillment plans grows combinatorially with the number of items. As we show in this paper, even the single-period fulfillment problem is NP-hard, which makes it difficult to derive real-time fulfillment rules that are both computationally efficient and operationally effective. These difficulties are further amplified by sequential order arrivals, irreversible fulfillment decisions, and time-varying costs. The central question is therefore how to design a real-time fulfillment policy that remains implementable at scale while performing well under demand uncertainty and exploiting limited local inventory effectively. Our paper addresses this question through a theoretical framework that is closely connected to practice. We characterize the performance loss induced by immediate and irreversible real-time decisions under uncertain future order arrivals, time-varying fulfillment costs, and computational constraints. To this end, we develop a gated priority-based greedy framework. We show that, under

different operational settings, appropriately designed gating conditions and priority rules over distribution centers enable a simple greedy policy to attain a finite competitive ratio relative to the clairvoyant benchmark, independent of the selling horizon, and that these competitive ratio guarantees are either optimal or order-optimal in all settings we study. This perspective is particularly relevant for large-scale e-commerce platforms, where highly sophisticated optimization methods may be difficult to deploy reliably in real time. In such settings, transparent and computationally efficient fulfillment rules with provable worst-case guarantees can offer an attractive balance between rigor and practicality. 1.1.

Overview of Our Model

Model. We study the multi-item order fulfillment problem in a two-layer distribution network consisting of K front distribution centers (FDCs) and one regional distribution center (RDC). FDCs hold finite and non-replenishable inventory across multiple items, while the RDC acts as an unlimited backup that can always fulfill any remaining demand. Customer orders arrive sequentially over a finite selling horizon. Each order may request multiple items and, importantly, multiple units of each item, which provides a more realistic generalization of the single-unit demand assumption commonly adopted in prior work (Jasin and Sinha 2015, Ma 2023, Amil et al. 2025). Upon the arrival of each order, the fulfillment policy must immediately determine how to allocate demand across the FDCs and the RDC, without observing future orders. Each distribution center incurs a fixed activation cost fk (where k “ 0 denotes the RDC and k P rK s denotes an FDC) whenever it is used to fulfill any part of an order, regardless of the quantity shipped, as well as an item-specific per-unit variable cost. The objective is to minimize the total fulfillment cost over the selling horizon. A distinctive feature of our model is that variable costs are allowed to vary over time, which captures fulfillment environments in which variable costs change across arriving orders due to destination-dependent fulfillment costs and evolving operating conditions. To the best of our knowledge, this practically relevant setting has not been studied in the existing literature. Competitive Analysis. We evaluate performance through the competitive ratio, defined as the worstcase ratio between the total fulfillment cost incurred by an online policy and that incurred by an optimal offline benchmark with full knowledge of the entire order sequence and all cost realizations. We work in a fully adversarial setting, in which the initial inventory levels, the sequence of customer orders, and the time-varying variable costs are all chosen by an adversary, without any distributional assumptions. This framework yields robust, distribution-free performance guarantees and directly captures the risk of poor performance under challenging demand and cost environments.

1.2.

Our Contributions

A Gated Priority-based Greedy Framework. A recent paper, Zhao et al. (2025), studies a natural myopic policy that minimizes the fulfillment cost of each order in isolation in a single-FDC–RDC network. A natural extension to the multi-FDC setting is to apply the same principle and minimize the cost of each order separately. Although this generalized myopic policy may perform well in some instances, computing the optimal allocation for each order is already computationally intractable: as we show in Section EC.2.5, the corresponding single-order optimization problem is NP-hard. To overcome this difficulty, we develop a gated priority-based greedy framework. The starting point is a priority-based greedy policy: for each item in an arriving order, the algorithm ranks distribution centers according to a prescribed cost-based priority rule and then constructs the fulfillment plan greedily. While this approach substantially improves computational tractability, a purely prioritybased greedy policy can be overly short-sighted and may perform poorly in the worst case. We therefore introduce a gating condition that determines whether the greedy allocation should be executed or the entire order should instead be routed to the RDC. If the gating condition is triggered, the algorithm fulfills the entire order solely through the RDC; otherwise, it follows the greedy allocation. The resulting framework is computationally efficient: once the gating condition and priority rankings are determined, the policy can be implemented in time proportional to the product of the number of items and the number of FDCs. Another key advantage of this framework is its flexibility. Both the priority rule and the gating condition can be tailored to the underlying cost structure. Representative priority rules include fixedcost-based and variable-cost-based rankings, which we refer to as the Fixed-Cost and VariableCost priority rules, respectively. Representative gating conditions include order-size threshold rules and cost-comparison rules that compare the greedy allocation with RDC-only fulfillment; we refer to these as the Order-Size and Cost-Comparison conditions, respectively. In particular, for the general multi-FDC setting with time-varying variable costs, we pair the Fixed-Cost priority rule with the Order-Size gating condition, under which sufficiently large orders are routed entirely to the RDC once their size exceeds a calibrated threshold. For the general multi-FDC settings with time-invariant variable costs, we instead pair the Variable-Cost priority rule with the CostComparison gating condition, which routes an order to the RDC whenever the cost of the greedy allocation exceeds that of RDC-only fulfillment. As we explain in Section 3, these priority rules and gating conditions are simple and intuitive in the corresponding settings, while yielding fulfillment policies that are both computationally efficient and operationally interpretable. The framework can also be extended to incorporate time-dependent priority rules, FDC-gating conditions, under which the entire order is routed to the sole FDC rather than to the RDC, and randomized gating conditions. These extensions are useful for the refined treatment of the single-FDC setting presented in Section 4.

5 # of FDCs

Cost Structure Timevarying‹

Multi-FDC (K ě 2)

Upper Bound on Competitive Ratio ˆ´ ˙ b ¯ f0 f0 b O ^ _ min f a a

Lower Bound on Competitive Ratio ˆ´ ˙ b ¯ f0 f0 b Ω ^ _ min f a a

(Order-Size F-Priority, Theorem 1):

(Theorem 2)

kPrKs k

ř f0 ` kPrKs fk

Timeinvariant‹‹ Timevarying‹

minkPrKs fk

Single-FDC (K “ 1)

Timeinvariant‹‹

Timeinvariant‹‹ (Zhao et al. 2025)

ř f0 ` kPrKs fk minkPrKs fk

(Cost-Comparison V-Priority, Theorem 3): b ¯ b ¯ ´´ f0 f0 O ^ _ ab f1 a (Better-of-Two, Corollary 1) $ ? 1? &1 ` , w ă 5´1 2 1´w`2

kPrKs k

1´w

(Theorem 4): b ¯ b ¯ ´´ f f0 Ω f0 ^ _ ab a 1 (Theorem 7)

ď 19.828 (Proposition 2)

wě (w “ f0 {f1 , Rand.-Cost-Comp. V-Priority, Theorem 8) ´ ¯ f Myopic policy: 1 ` f0 _ 2

ď 6.473 (Proposition 1)

´ ¯ f 1 ` f0 _ 54

? 5´1 2

%1 ` w,

UB{LB

ď 1.123 (Theorem 9)

a For fixed f1 : Ωp f0 q

Unbounded

‹ : In the time-varying setting (Assumption 1), the competitive ratio depends on the fixed costs f0 , f1 , . . . , fK and on the lower and upper bounds a and b of the variable costs, as defined in Eq. (2). ‹‹ : In the time-invariant setting (Assumption 2), the competitive ratio only depends on the fixed costs f0 , f1 , . . . , fK , as defined in Eq. (3). : : These bounds remain valid when K “ 1. However, for this special case, we prove sharper bounds, reported in the rows corresponding to K “ 1.

Table 1

Summary of Our Results

A summary of all instantiations of the framework and its extensions, together with the corresponding priority rules and gating conditions, is provided in Table 3 in Section 3.1. Provably Optimal and Order-optimal Competitive Ratios. We consider two alternative assumptions on the cost structure. The time-invariant assumption, formally stated in Assumption 2, is standard in the online fulfillment literature and assumes that all costs remain constant across the sequence of arriving orders. The time-varying assumption, formally stated in Assumption 1, allows the per-unit variable costs to vary across arriving orders. This latter assumption captures practical settings in which variable costs are destination-dependent, while the fixed cost of using a distribution center remains stable over the selling horizon. Under both assumptions, for a general number of FDCs with K ě 2, we instantiate the Gated Priority-based Greedy framework to obtain two algorithms: Cost-Comparison V-Priority, designed for the time-invariant setting using the VariableCost priority rule and the Cost-Comparison gating condition; and Order-Size F-Priority, designed for the time-varying setting using the Fixed-Cost priority rule and the Order-Size gating condition. We establish upper bounds on their competitive ratios in Theorem 3 and Theorem 1, respectively. The rows corresponding to K ě 2 in Table 1 summarize these bounds. The upper bound for CostComparison V-Priority exactly matches the lower bound, establishing its optimality with respect

to the worst-case competitive ratio. The upper bound for Order-Size F-Priority matches the lower bound up to a factor of at most 6.473, thereby establishing that the algorithm is order-optimal. Throughout, we view the competitive ratio as a function of the fixed costs f0 , f1 , . . . , fK , while taking the worst-case ratio over the unknown order sequence and the time-varying variable costs. In the time-varying setting, we further assume that the variable costs lie in the interval ra, bs, where 0 ă a ď b, as specified in Assumption 1, and define the competitive ratio accordingly as a function of a and b in Eq. (2). This boundedness assumption is essential: if variable costs are unbounded, then the competitive ratio is also unbounded, as shown in Theorem 2, rendering the problem less meaningful under competitive analysis. In the time-invariant setting, by contrast, both the upper and lower bounds depend only on the fixed costs f0 , f1 , . . . , fK , in accordance with the competitive-ratio definition in Eq. (3). Although the algorithms described above apply to any number of FDCs K ě 1, their competitive ratio guarantees may be further improved in the single-FDC setting (K “ 1). The corresponding results are reported in the first two K “ 1 rows of Table 1. We refine the algorithmic guarantees for both the time-varying and time-invariant variable-cost settings. These algorithms are again instantiated from extensions of our Gated Priority-based Greedy framework; in particular, the Better-of-Two algorithm is a hybrid of two such instantiations. Table 3 in Section 3.1 provides a more detailed summary of their features. As a result, in the time-varying setting, the Betterof-Two algorithm achieves an order-optimal competitive ratio, matching the lower bound up to a constant factor. In the time-invariant setting, the Randomized-Cost-Comparison V-Priority algorithm matches the lower bound up to a factor of 1.123, improving upon the factor-2 guarantee for the general-K case. Competitive Ratio Lower Bounds for Any Fulfillment Policy. We also establish competitive ratio lower bounds for each scenario that apply to all online fulfillment policies, including randomized ones. The corresponding results are also reported in Table 1. Our lower bounds are based on a unified adversarial two-instance argument that forces any online algorithm to deplete valuable FDC inventory prematurely and thereby incur higher future costs. The key idea is to construct pairs of instances with a common prefix but different continuations, so that the algorithm must commit before it can determine whether early use of FDC inventory is beneficial or harmful. This construction relies on two mechanisms: one based on fixed-cost heterogeneity, which induces early depletion of low-fixed-cost FDC inventory, and the other based on temporal variation in per-unit variable costs. The latter mechanism is implemented differently across settings: when K ě 2, it uses multiple FDCs with identical initial variable costs but asymmetric future evolutions, whereas when K “ 1, it sets the initial variable cost at an intermediate level to obscure whether early allocation or later preservation

is preferable. The time-varying lower bound combines both mechanisms, whereas the time-invariant lower bound relies primarily on the fixed-cost construction. We then invoke Yao’s minimax principle to extend the argument to randomized algorithms. Improvement upon Existing Work. For the single-FDC setting, Zhao et al. (2025) study a myopic policy under the assumption that the variable costs c0 and c1 for the RDC and the FDC, respectively, are both time- and item-independent. Their theoretical analysis yields three bounds on the competi´ ¯ f0 f1 tive ratio: (1) if f0 ď f1 and c0 ą c1 , the competitive ratio is upper bounded by 1 ` f1 `αc _ ; f0 `αc0 1 0 (2) if f0 ą f1 , c0 ą c1 , it is upper bounded by 1 ` f1f`c ; (3) if f0 ą f1 , c0 ď c1 , it is upper bounded 1 ´ ¯ 1 ´c0 q by 1 ` pf0 ´ff11q´pc _ 0 . One advantage of these results is that they capture a more fine-grained `c1

dependence on c0 and c1 . However, if we instead consider the worst-case competitive ratio under adversarial choices of c0 and c1 , then our guarantees improve upon theirs. Specifically, the results of Zhao et al. (2025) imply that the competitive ratio of the myopic policy is upper bounded by 1 ` ´ ¯ ! ) f0 f0 _ 1 “ max 1 ` , 2 . Compared with this guarantee, our Cost-Comparison V-Priority f1 f1 algorithm attains the same worst-case competitive ratio while allowing for item-dependent variable costs. Moreover, our Randomized-Cost-Comparison V-Priority algorithm, which is specifically designed for the single-FDC setting, achieves a strictly better competitive ratio when w “ ff01 is small. For clarity, this comparison is also summarized in Table 1. We also strengthen the lower bound on the competitive ratio achievable by randomized algorithms. ? Zhao et al. (2025) show a lower bound that grows on the order of f0 as f0 Ñ 8. By contrast, our ! ) lower bound in Theorem 9 shows that the competitive ratio is at least max 1 ` ff10 , 54 , which grows linearly with f0 and matches the upper bound for Randomized-Cost-Comparison V-Priority within a factor of 1.123, showing the near-optimality of our Randomized-Cost-Comparison VPriority algorithm for the single-FDC fulfillment problem. 1.3.

Literature Review

E-commerce fulfillment and order splitting. Real-time order fulfillment has been studied extensively in operations and revenue management because splitting a multi-item order across facilities can increase outbound shipping costs and degrade the customer experience. Early work emphasized implementable decision rules and re-optimization in large-scale execution systems. Xu et al. (2009) study real-time multi-item order fulfillment and show the value of periodically reevaluating assignments, with the objective of reducing the total number of shipments. Acimovic and Graves (2015) develop a fulfillment heuristic based on the dual values of a transportation linear program with known demand, and Andrews et al. (2019) develop primal-dual algorithms for an industrial order fulfillment system without demand forecasting.

8 Model features Arriving orders

Jasin and Sinha (2015)

Ma (2023)

Amil et al. (2025)

Zhao et al. (2025)

Stochastic, under known distribution

# of DCs Quantity of an item in an order Variable-cost structure

Adversarial Two-layer, single FDC

Multiple Single Time-invariant, item-specific Item-facility LP with rounding Average-case, asymptotic

Main policy Performance guarantee

Table 2

This paper

Two-layer, multiple FDCs Multiple

Time-invariant, item-independent Method-based LP with rounding Average-case, nonasymptotic

Time-varying, item-specific Gated priority-based Myopic greedy Worst-case, nonasymptotic

Comparison with Closely Related Theoretical Literature

Provable policies for multi-item e-commerce fulfillment. The theoretical literature most closely related to ours studies provable fulfillment policies for online multi-item orders. The seminal work of Jasin and Sinha (2015) formulates a stochastic multi-item e-commerce fulfillment problem with multiple facilities, finite inventories, fixed and variable shipping costs, and customer orders drawn from a known distribution. They combine a deterministic item-facility linear program with correlated rounding and establish asymptotic average-case performance guarantees. Ma (2023) improves this line of work by modifying the correlated-rounding scheme and obtaining an asymptotically p1 ` ln q qcompetitive policy, where q measures order size. More recently, Amil et al. (2025) revisit LP formulations through a method-based perspective, connect the fulfillment problem to prophet-inequality arguments, and derive nonasymptotic average-case guarantees. In contrast to these forecast-informed approaches, Zhao et al. (2025) study a two-layer RDC-FDC network under adversarial arrivals and analyze the worst-case competitive ratio of a myopic policy. Table 2 summarizes the closest theoretical papers. Existing LP-based studies primarily examine the performance of forecast-informed policies when the order distribution is known. Zhao et al. (2025) move to adversarial arrivals, but their model is restricted to a single FDC, single-unit item requests, and variable costs that are independent of both item and time. Our model incorporates multiple FDCs, multi-unit multi-item orders, item-specific and time-varying variable costs, and adversarial fluctuations in both order arrivals and variable costs. This combination introduces methodological challenges absent from previous work: cross-facility order splitting becomes computationally more difficult, and intertemporal inventory allocation under adversarial arrivals and heterogeneous variable costs entails a substantially more intricate trade-off. Online resource allocation. Our work is also connected to the broader literature on online resource allocation, which studies sequential decisions with limited resources and evaluates policies using competitive ratio or regret. Classic examples include online bipartite matching (Karp et al. 1990), online budgeted allocation and AdWords (Mehta et al. 2007), and the primal-dual methodology

for online packing and covering problems (Buchbinder and Naor 2009). In operations management, robust revenue management and online booking use competitive analysis to obtain distributionfree guarantees when demand forecasts are unavailable or unreliable (Lan et al. 2008, Ball and Queyranne 2009), while LP re-solving policies provide strong regret guarantees under stochastic arrival models (Jasin and Kumar 2012, Bumpensanti and Wang 2020). More recently, (He et al. 2025) shows the effectiveness of primal-dual methods for online resource allocation without repeated re-solving, and recent work on online allocation or matching with reusable resources shows that greedy-like policies can be effective when resources return after stochastic service durations (Goyal et al. 2025, Simchi-Levi et al. 2025). Our problem can be viewed as a fulfillment-specific online resource allocation problem, where FDC inventories are allocated sequentially to multi-item orders. However, the presence of fulfillment split and fixed activation costs makes the model structurally different from classical online resource allocation problems. Delay, omnichannel, replenishment, and pricing extensions. A related stream studies fulfillment together with other retail decisions. The benefit of delaying fulfillment decisions is studied by a series of papers (Wei et al. 2021, Xie et al. 2025, Zhou et al. 2025). Omnichannel retailing integrates online demand with store-based inventory and in-store demand (Govindarajan et al. 2021, Hübner et al. 2022). Inventory replenishment has also been studied jointly with online fulfillment decisions (Acimovic and Graves 2017, Goedhart et al. 2023, Ling et al. 2026). Another stream of work combines dynamic pricing and order fulfillment (Lei et al. 2018, Harsha et al. 2019, Qiu et al. 2021). In contrast to these richer models, we focus on a more stylized fulfillment setting that permits sharper theoretical analysis and leads to optimal or order-optimal competitive-ratio guarantees, while these extensions suggest natural directions for future work.

Model Description

In this section, we describe the formal setting of the model. There are n distinct items, indexed by i “ 1, 2, . . . , n, stored across K FDCs and one RDC. The RDC is indexed by k “ 0 and has unlimited inventory for all items. The FDCs are indexed by k “ 1, 2, . . . , K, and each FDC k starts i i with an initial inventory of Ik,0 units of item i, where Ik,0 ě 0. FDC inventories are nonreplenishable

throughout the selling horizon. Customer orders arrive sequentially over a finite horizon of T discrete periods, indexed by t “ 1, 2, . . . , T . Each order may request one or more items, and the quantity requested for item i in period t is denoted by Sti . We allow Sti to be any nonnegative integer, in contrast to the binary-demand assumption commonly adopted in prior work (Amil et al. 2025, Zhao et al. 2025). Let St “ pSti qiPrns denote the order vector in period t. Upon the arrival of each order, the fulfillment decision must be made immediately and irrevocably.

An order may be fulfilled using inventory from one or more FDCs and/or the RDC, and the resulting cost depends on the chosen fulfillment plan. If FDC k is used to fulfill any part of an order, then a fixed cost fk is incurred, regardless of the number of items or units supplied by that FDC. In addition, fulfilling item i from FDC k in period t incurs a per-unit variable cost cik,t , which may vary over time. Similarly, if the RDC is used to fulfill any part of an order, then a fixed cost f0 is incurred, together with a per-unit variable cost ci0,t for each unit of item i supplied by the RDC in period t. The objective is to determine an online fulfillment policy that minimizes the total fulfillment cost over the selling horizon. Unlike Zhao et al. (2025), which assumes that variable costs are independent of both item and time, we allow the variable costs cik,t to be item-specific and time-varying. This generalization captures important features of real-world fulfillment systems, including destination-dependent shipping costs, fluctuating transportation costs, and changing labor or operating conditions. Since decisions are made online, the fulfillment policy may use only the information available up to the current period and has no access to future customer orders. In each period t, after observing the arriving order St “ pSti qiPrns and the variable costs pcik,t qkP0YrKs,iPrns , the fulfillment policy must immediately choose fulfillment quantities mik,t , where

mik,t denotes the quantity of item i supplied from location k in period t, with k “ 0 corresponding to the RDC. These quantities must satisfy the following constraints: • Demand fulfillment constraint. For each item i and period t, the total quantity supplied from řK all FDCs and the RDC must equal the requested quantity: k“0 mik,t “ Sti holds for all i and t. • Inventory constraint. For each FDC k and item i, the total fulfillment quantity from FDC k up řt i to time t cannot exceed its initial inventory: τ “1 mik,τ ď Ik,0 holds for all k ‰ 0, i, and t. Let ř t i i Ik,t “ Ik,0 ´ τ “1 mik,τ be the remaining inventory of item i at FDC k at the end of time t. Then i the inventory constraint can be equivalently written as mik,t ď Ik,t´1 for all k ‰ 0, i, and t.

• Non-negativity constraint. The fulfillment quantities must be non-negative, i.e., mik,t ě 0 holds for all k, i, and t. The fulfillment cost incurred in period t is

řK “ k“0

fk ¨ I

` řn

i i“1 mk,t ą 0

řn

i i i“1 ck,t ¨ mk,t

‰

, where Ip¨q

denotes the indicator function. Therefore, the total fulfillment cost over the entire selling horizon is « ˜ ¸ ff T ÿ K n n ÿ ÿ ÿ fk ¨ I mik,t ą 0 ` cik,t ¨ mik,t . (1) t“1 k“0

i“1

The goal of the fulfillment policy is to minimize this total cost. Competitive Ratio. We study the problem in an adversarial setting, where the initial inventories of the FDCs, the sequence of customer orders, and the corresponding variable costs are chosen by an adversary. The performance of a fulfillment policy is evaluated by its competitive ratio, defined as the

worst-case ratio between the total fulfillment cost incurred by the online policy and that incurred by an optimal offline algorithm with full knowledge of the entire sequence of customer orders and variable costs in advance. Since this worst-case ratio is taken over all admissible order sequences and variable costs, it can be viewed as a function only of the fixed costs f0 , f1 , . . . , fK . In the fully general time-varying-variable-cost setting, however, this competitive ratio may be unbounded. We therefore focus on a bounded-variable-cost version of the problem, in which the variable costs are assumed to lie in the interval ra, bs for some 0 ă a ď b. Specifically, for any instance i I “ tIk,0 , cik,t , Sti uiPrns,tPrT s,k“0,...,K , let ALGpI q and OPTpI q denote the total fulfillment costs incurred

by the online algorithm and the optimal offline algorithm, respectively. We then define the competitive ratio of the algorithm as RpALGq “ RpALG; f0 , f1 , . . . , fK , ra, bsq “ sup def

n,T

sup

i Ik,0 cik,t Pra,bs pkPrKs,iPrnsq pk“0,...,K,iPrns,tPrT sq

ALGpI q . St :tPrT s OPTpI q sup

(2)

In the more restrictive time-invariant-variable-cost setting, by contrast, we are able to design competitive algorithms even when the variable costs are unbounded. In this case, we define the competitive ratio as Rinv pALGq “ Rinv pALG; f0 , f1 , . . . , fK q “ sup def

n,T

sup

i Ik,0 cik,t ”cik pkPrKs,iPrnsq pk“0,...,K,iPrns,tPrT sq

ALGpI q . St :tPrT s OPTpI q sup

(3)

When there is no ambiguity, we omit the parameters f0 , f1 , . . . , fK , a, and b from the competitive ratio notations in Eq. (2) and Eq. (3). A fulfillment policy is said to be α-competitive if its competitive ratio is at most α, where the precise definition of the competitive ratio depends on the setting under consideration. Our goal is to design a computationally efficient online algorithm with the smallest possible competitive ratio. Throughout the paper, we use the terms “algorithm” and “policy” interchangeably.

Competitive Ratio Upper & Lower Bounds for Multi-FDC Networks

In this section, we present our algorithmic and lower bound results for the two-layer multi-item order fulfillment problem over general multi-FDC networks, that is, for all K ě 1. We begin in Section 3.2 by formally introducing the Gated Priority-based Greedy framework. We then present and analyze its instantiations under two specific settings: time-varying variable costs (Section 3.3) and time-invariant variable costs (Section 3.4). For each setting, we also establish a complementary lower bound on the competitive ratio achievable by any online algorithm in the corresponding subsection. Before turning to the formal development, we first provide a detailed overview of the motivation and intuition behind the Gated Priority-based Greedy framework and its scenario-specific instantiations in Section 3.1.

3.1.

Overview of Algorithmic Intuitions

Myopic Policy and Its Computational Intractability. Zhao et al. (2025) studied the myopic policy in the single-FDC setting (K “ 1), where each arriving order is fulfilled so as to minimize its current cost in isolation. Because there is only one FDC and the variable costs are identical across items, this decision reduced to a simple comparison between using the FDC and routing the entire order to the RDC, and is therefore computationally straightforward. They further showed that this policy admitted strong competitive-ratio guarantees in the single-FDC setting. A natural generalization to the multi-FDC setting is to apply the same myopic principle and compute, for each arriving order, the fulfillment plan that minimizes the current order’s cost subject to the inventory and demand constraints. Formally, at period t, this policy solves « ˜ ¸ ff K n n ÿ ÿ ÿ min fk ¨ I mik,t ą 0 ` cik,t ¨ mik,t , tmik,t uk,i

k“0

i“1

subject to the demand and inventory constraints. However, for general K, this natural extension becomes computationally intractable: the policy must determine both which subset of distribution centers to activate and how to allocate the order across them. As we show in Appendix EC.2.5, the resulting optimization problem is NP-hard in general via a reduction from Set Cover. This computational intractability motivates our search for a more tractable online decision rule. Priority-based Greedy as a Tractable Surrogate. To address this computational intractability, we begin with a more radical but much more tractable surrogate, which we call the priority-based greedy policy. Before any orders arrive, the policy fixes, for each item i, a priority ranking ăi over all distribution centers (DCs). Upon the arrival of an order, the policy fulfills each item greedily according to this ranking: it first uses as much inventory as possible from the highest-priority DC, then moves to the next DC in the ranking, and continues until the demand is fully satisfied. Since the RDC has infinite inventory, every order can always be fulfilled. This priority-based greedy rule is computationally simple, requiring only OpnK q time per order, and therefore offers a dramatic improvement over the exponential complexity of the myopic approach. The key remaining question is whether one can design the priority rankings so that such a simple greedy rule also achieves strong worst-case performance guarantees. Why Pure Priority-based Greedy is Not Enough. Despite its computational appeal, a purely prioritybased greedy policy can perform poorly in the worst case because it is too short-sighted. In particular, by greedily exploiting currently attractive FDC inventory, it may deplete scarce FDC stock too early and thereby sacrifice substantial future savings. The following example illustrates this phenomenon.

Example 1 (Failure of purely priority-based greedy). We consider a simple instance with one FDC, one RDC, and a single item. For any integer M ě 1, consider a problem instance with horizon T “ M ` 1. The fixed costs are f0 “ 1 and f1 “ 0, and the variable costs satisfy c0,t “ c0 “ 1{M and c1,t “ c1 “ 1{M for all t P rT s. The initial FDC inventory is I1,0 “ M . The order sequence is given 1 by S11 “ M and S21 “ S31 “ ¨ ¨ ¨ “ SM `1 “ 1. We now consider the following two priority rankings for

the only item 1: • FDC ă1 RDC. The greedy policy uses the FDC to fulfill the first order, incurring cost f1 ` S11 ¨ c1 “ 0 ` M ¨ p1{M q “ 1. The FDC inventory is then exhausted, so all remaining orders must be fulfilled from the RDC, incurring an additional cost of pT ´ 1q ¨ pf0 ` 1 ¨ c0 q “ M p1 ` 1{M q “ M ` 1. Hence, the total cost is 1 ` pM ` 1q “ M ` 2. • RDC ă1 FDC. Since the RDC is never depleted, The greedy policy uses the RDC to fulfill all orders. The resulting cost is pf0 ` S11 ¨ c0 q ` pT ´ 1q ¨ pf0 ` 1 ¨ c0 q “ 1 ` M ¨ p1{M q ` M ¨ p1 ` 1 ¨ p1{M qq “ M ` 3.

By contrast, the optimal offline policy fulfills the first order from the RDC, incurring cost f0 ` M ¨ c0 “ 1 ` M ¨ p1{M q “ 2, and reserves the FDC inventory for the later small orders. The remaining orders are then fulfilled from the FDC at total cost pT ´ 1q ¨ pf1 ` 1 ¨ c1 q “ M ¨ p0 ` 1 ¨ p1{M qq “ 1. Thus, the total cost incurred by the offline policy is 2 ` 1 “ 3. Therefore, under either priority ranking, the purely priority-based greedy algorithm incurs a competitive ratio of ΩpM q. By contrast, our Order-Size F-Priority also applies to this instance, ? and Theorem 1 guarantees a competitive ratio of Op M q. Hence, the purely priority-based greedy ? algorithm can be worse by a factor of Ωp M q, where M can be arbitrarily large. This example highlights the central weakness of the pure priority-based greedy algorithm. Under the ranking FDC ă1 RDC, the algorithm uses FDC inventory too aggressively, without accounting for its future value. Under the ranking RDC ă1 FDC, the algorithm goes to the opposite extreme and fails to use the FDC inventory at all. From Priority-based Greedy to Gated Priority-based Greedy. To address this weakness, we augment the priority-based greedy rule with a gating condition. The resulting policy first determines whether the arriving order should be handled greedily using all DCs or instead be routed entirely to the RDC. If the gating condition is triggered, the order is fulfilled solely through the RDC; otherwise, the order is fulfilled according to the priority-based greedy allocation. We refer to this general class of policies as the gated priority-based greedy framework. The logic is simple: the priority rule determines how an order should be allocated when FDC inventory is worth using, while the gating condition determines whether FDC inventory should be used at all. In this way, the framework preserves the computational tractability of greedy allocation while protecting against the most harmful forms of short-sighted inventory depletion or excessive fixed-cost expenditure.

Scenario-specific Instantiations. A key advantage of the Gated Priority-based Greedy framework is its flexibility: both the priority rule and the gating condition can be tailored to the underlying cost structure. The appropriate design depends on which component of the cost structure primarily drives the worst-case competitive ratio in each setting.

# of FDCs

Cost Structure

Framework

Timevarying (Assump. 1) Multi-FDC

Priority Rule

Gating Condition

Order-Size F-Pri. (Algorithm 2)

Fixed-Cost

Order-Size

Original Timeinvariant (Assump. 2)

Timevarying (Assump. 1) Single-FDC Timeinvariant (Assump. 2) Table 3

Algorithm

Cost-Comp. V-Pri. (Algorithm 3)

Variable-Cost Cost-Comparison

Extension w/ time-dependent priority rules (★)

Cost-Comp. AdjV-Pri. AdjustedCost-Comparison (Algorithm 4) Variable-Cost

Extend (★) further w/ FDC-gating cond.

Order-Size AdjV-Pri. (Algorithm 5)

AdjustedVariable-Cost

Order-Size FDC-gating cond.

Extension w/ randomized gating condition

Rand.-Cost-Comp. V-Pri. (Algorithm 6)

Variable-Cost

RandomizedCost-Comparison

Summary of the Scenario-specific Instantiations of the Gated Priority-based Greedy Framework and its Extensions.

• Time-varying variable costs (Assumption 1). In this setting, the variable costs are bounded in the range of ra, bs, where a and b are fixed parameters. The effect of variable-cost fluctuations on the competitive ratio is therefore controlled by the ratio b{a. Thus, the main source of worst-case loss comes from how fixed activation costs are incurred. Accordingly, we use the Fixed-Cost priority, which ranks DCs in nondecreasing order of fixed cost and gives higher priority to DCs that are cheaper to activate. To prevent the greedy rule from depleting FDC inventory too aggressively, we combine this priority rule with an Order-Size gating condition: when the total size of an incoming order exceeds a threshold θ, the entire order is routed to the RDC. Intuitively, large orders can better amortize the RDC fixed cost and are therefore less valuable targets for scarce FDC inventory, whereas small orders benefit more from the fixed-cost savings of local fulfillment. This yields the Order-Size F-Priority algorithm; see Section 3.3. • Time-invariant variable costs (Assumption 2). In this setting, the variable costs cik are constant over time but may be arbitrarily large relative to the fixed costs. Thus, the main source of worst-case loss comes from how variable costs are incurred. Accordingly, we use the VariableCost priority rule, which ranks DCs in nondecreasing order of variable cost for each item. The

main risk in this setting is not over-depletion of FDC inventory, but rather excessive activation of multiple FDCs, each of which incurs its own fixed cost. We therefore introduce a CostComparison gating condition: the greedy allocation is used only when its total cost does not exceed the cost of fulfilling the same order entirely through the RDC. Otherwise, the order is routed to the RDC. This yields the Cost-Comparison V-Priority algorithm; see Section 3.4. • Refinements for single-FDC settings. For single-FDC networks, we design algorithms with sharper competitive ratio guarantees based on extensions of the Gated Priority-based Greedy framework. These extensions allow for time-dependent priority rules, FDC-gating conditions, under which the entire order is routed to the sole FDC rather than to the RDC, and randomized gating conditions. In the time-varying variable cost setting, we instantiate the extended framework using the Adjusted-Variable-Cost priority rule, which generalizes the Variable-Cost rule by reweighting the variable costs through an additional parameter, together with the Cost-Comparison gating condition and the Order-Size FDC-gating condition. This yields the Cost-Comparison AdjV-Priority algorithm and the Order-Size AdjV-Priority algorithm; see Section 4.1. In the time-invariant variable cost setting, we introduce the Randomized-Cost-Comparison gating condition. Combined with the VariableCost priority rule, this produces the Randomized-Cost-Comparison V-Priority algorithm; see Section 4.2. Table 3 summarizes these instantiations. The following subsections formalize the framework and establish the competitive guarantees of the resulting algorithms. 3.2.

Formal Introduction of the Gated Priority-based Greedy Framework

We now formalize the class of Gated Priority-based Greedy fulfillment policies that captures the ideas described above. The framework is summarized in Algorithm 1. For each item i, the policy maintains a priority ranking, that is, a total order ăi over all distribution centers (DCs). It also maintains a gating condition Gptfk , cik , S i , m̂ik uq which is a Boolean-valued function of the fixed costs, the current-period variable costs, the current-period order quantities, and the pure greedy fulfillment plan induced by the priority rankings. Upon the arrival of an order St , the policy first computes the greedy fulfillment plan tm̂ik,t uk,i induced by ăi (Line 4), and then evaluates the gating condition Gptfk , cik,t , Sti , m̂ik,t uq. If the gating condition is triggered, the order is fulfilled entirely through the RDC; otherwise, it is fulfilled according to the priority-based greedy plan. For a pure priority-based greedy algorithm, higher-priority FDCs are always used as much as possible before lower-priority FDCs are considered. As a gated extension, Gated Priority-based Greedy preserves this property during periods when the pure greedy allocation is selected. The following lemma formalizes this observation and plays a central role in the analysis of each scenariospecific instantiation of the framework.

Algorithm 1 Gated Priority-based Greedy 1: Input: A priority ranking ăi among all DCs and a gating condition Gptfk , cik , S i , m̂ik uq P t0, 1u; 2: for each time period t “ 1, 2, . . . , T do 3:

Observe customer order St and variable costs tcik,t uk“0,...,K ;

Compute the pure greedy fulfillment quantities according to the priority ranking ăi :

i“1,...,n

m̂ik,t “ min

!´ Sti ´

Iki 1 ,t´1

¯`

i , Ik,t´1

) I pk ăi 0q , @ k P rK s, i P rns,

k1 PrKs:k1 ăi k

m̂i0,t “ Sti ´

m̂ik,t , @ i P rns;

kPrKs

if gating condition Gptfk , cik,t , Sti , m̂ik,t uq “ 1 then

mi0,t Ð Sti and mik,t Ð 0 for all k P rK s, i P rns;

Ź route entire order to RDC

else

mik,t Ð m̂ik,t for all k P t0, . . . , K u, i P rns; Ź follow priority-based greedy ␣ ( i i Execute fulfillment plan mik,t , and update inventory levels: Ik,t Ð Ik,t´1 ´ mik,t , @k, i.

Lemma 1. Fix an item i. Without loss of generality, suppose that the total order ăi on t0, . . . , K u is 1 ăi 2 ăi ¨ ¨ ¨ ăi k0 ăi 0 ăi k0 ` 1 ăi ¨ ¨ ¨ ăi K, so that FDC 1 has the highest priority. For any period t, let tm̂ik,t uK k“0 denote the pure greedy fulfillment plan generated by Algorithm 1. Define A “ řK tt : k“1 mik,t ą 0u, namely, the set of periods in which the actual fulfillment plan uses at least one FDC to fulfill demand for item i. Then for any set B Ě A, we have j ÿ ÿ

m̂ik,t ě

k“1 tPB

j ÿ ÿ

@ j “ 1, 2, . . . , k0 .

mi,˚ k,t ,

k“1 tPB

The key step in proving the lemma is the following chain of inequalities: # + j ÿ j j ÿ ÿ ÿ ÿ ÿ i i i m̂k,t ě min St , Ik,0 ě mi,˚ k,t . k“1 tPB

tPB

k“1

k“1 tPB

The second inequality follows directly from the demand-fulfillment and inventory constraints. To see the first inequality, observe that, in each period t, the pure greedy quantities m̂ik,t are generated according to the priority order ăi . Hence, for the FDCs t1, . . . , j u, either the demand for item i is fully covered, or all available inventory at these FDCs is allocated. In addition, for every period t P A, the Gated Priority-based Greedy algorithm coincides with the pure greedy plan. Together, these observations capture the main idea behind the proof of the first inequality. A detailed proof is provided in Section EC.1.1 of the e-companion.

3.3.

Scenario-specific Instantiation: Time-varying Variable Costs

We first consider the setting in which the variable costs cik,t may vary over time. To analyze this case, we impose the following boundedness assumption. As we show later, this assumption is essentially necessary for obtaining a finite competitive ratio for any online fulfillment policy. Assumption 1. There exist constants b ą a ą 0 such that a ď cik,t ď b for all k, i, t. This assumption is natural in practice: although per-unit variable costs may vary over time because of destination mix and changing operating conditions, they are typically bounded away from both zero and infinity over a fixed service region and planning horizon. More importantly, as shown later in Theorem 2, the minimax competitive ratio necessarily depends on the scale factor b{a. Hence, if b Ñ 8 or a Ñ 0` , the competitive ratio diverges. Thus, without Assumption 1, no online policy can admit a finite worst-case guarantee. At the same time, the assumption still permits rich heterogeneity, since the costs remain item-specific, facility-specific, and time-varying. Under Assumption 1, we instantiate the Gated Priority-based Greedy framework using the Fixed-Cost priority rule, which ranks DCs in nondecreasing order of fixed cost fk , together with the Order-Size gating condition, which is triggered whenever the order size exceeds a prescribed threshold θ. The formal definitions of the algorithm, the priority rule, and the gating condition are given in Algorithm 2. Algorithm 2 Order-Size F-Priority (Input parameter: θ ě 0) Instantiate Gated Priority-based Greedy using: • Fixed-Cost priority: let ăi “ăF @i P rns where k ăF j ô fk ă fj or fk “ fj , k ă j,

@ k, j P t0, . . . , K u;

• Order-Size gating condition (with parameter θ): G

ˆ ␣

(

fk , cik,t , Sti , m̂ik,t k“0,...,K i“1,...,n

n ÿ

“I

Sti ą θ

i“1

As discussed in Section 3.1, under the bounded variable cost assumption, the primary source of worst-case loss arises from the fixed costs. This observation motivates the use of the Fixed-Cost priority. At the same time, the Order-Size gating condition, parameterized by the threshold θ, prevents the FDC inventory from being depleted too aggressively. The following Theorem 1 establishes an upper bound on the competitive ratio of the Order-Size F-Priority algorithm. As can be seen from the proof, the threshold θ plays a balancing role. A larger value of θ offers stronger protection against premature depletion of the FDC inventory: even if our algorithm is later

forced to rely on the RDC under the pure priority-based greedy policy, the corresponding fixed cost is amortized over at least θ items in the order. By contrast, a smaller value of θ helps limit the competitive ratio loss incurred by the “all-RDC” fulfillment plan to at most θ, as established by our key technical Lemma 1. Theorem 1. Under Assumption 1, the competitive ratio of Order-Size F-Priority defined in Algorithm 2 satisfies " RpOrder-Size F-Priorityq ď max θ, b

In particular, if we choose θ “

pminkPrKs fk ´bq f0 ` a 4a2

RpOrder-Size F-Priorityq ď max Proof.

Let A “ tt :

* f0 ` bθ b , . minkPrKs fk ` aθ a

minkPrKs fk ´b 2a

, then

f0 pminkPrKs fk ´ bq2 minkPrKs fk ´ b b ` ´ , a 4a2 2a a

řn

i i“1 St ď θ u be the set of time periods that the total number of items in

the order is at most θ (i.e., when the algorithm follows the pure priority-based greedy policy). Let K tmi,˚ k,t uk“0 denote the fulfillment plan of the optimal offline policy. For simplicity, we also denote

f “ minkPrKs fk as the minimal fixed cost among all FDCs. The total cost incurred by the OrderSize F-Priority fulfillment policy can be upper bounded as follows: « ˜ ¸ ff T ÿ K n n ÿ ÿ ÿ i i i pcost incurred by Order-Size F-Priorityq “ fk ¨ I mk,t ą 0 ` ck,t ¨ mk,t t“1 k“0

« ÿ

K ÿ

tPA

k“0

fk ¨ I

n ÿ

i“1

mik,t ą 0

i“1

n ÿ

i“1

Sti

« ÿ `

i“1

f0 ` b

n ÿ

Sti

(4)

i“1

tRA

For the optimal offline algorithm, we lower bound its total cost as follows: « ˜ ¸ ff T ÿ K n n ÿ ÿ ÿ OPT “ fk ¨ I mi,˚ ` cik,t ¨ mi,˚ k,t ą 0 k,t t“1 k“0

« K ÿ ÿ ě tPA

i“1

fk ¨ I

k“0

n ÿ

i“1

mi,˚ `a k,t ą 0

n ÿ i“1

Sti `

« ÿ tRA

mintf, f0 u ` a

n ÿ

Sti .

(5)

i“1

Comparing Eq. (4) and Eq. (5), for the terms corresponding to t R A, we have « ff ff " * ÿ« ÿ ÿ ÿ b f ` bθ 0 f0 ` b Sti ď max , ¨ mintf, f0 u ` a Sti . a f ` aθ i i tRA tRA

(6)

For the terms corresponding to t P A, we will prove that the cost incurred by Order-Size Fřn řn Priority is at most θ times the offline optimum. For each t P A, by i“1 Sti ď θ, we have i“1 mi,˚ k,t ď `řn ˘ i,˚ θ ¨ I i“1 mk,t ą 0 holds for each DC k P rK s Y t0u. Therefore, ˜ ¸ « ˜ ¸ff K n K n ÿÿ ÿ ÿ ÿ ÿ fk ¨ mi,˚ ďθ¨ fk ¨ I mi,˚ . (7) k,t k,t ą 0 tPA k“0

i“1

tPA k“0

i“1

On the other hand, we prove the following claim after the proof of this theorem.

Claim 1. For each item i P rns, we have Claim 1 implies that

K ÿÿ

n ÿ

fk ¨

řK `

k“0

K ÿÿ

mik,t

fk ¨

i“1

tPA k“0

˘ ˘ ř řK ` fk ¨ mik,t ď tPA k“0 fk ¨ mi,˚ k,t .

tPA

n ÿ

mi,˚ k,t

(8)

i“1

tPA k“0

Combining Eq. (7), Eq. (8), we have « ˜ ¸ ff « ff K n n K n n ÿ ÿ ÿ ÿ ÿ ÿ ÿ ÿ i i i i fk ¨ I mk,t ą 0 ` b St ď fk ¨ mk,t ` b St tPA

i“1

k“0

i“1

« K ÿ ÿ ď tPA

fk ¨

k“0

n ÿ

mi,˚ k,t ` b

i“1

n ÿ

fftPA

Sti ď

i“1

k“0

« ÿ

θ¨

tPA

K ÿ

i“1

fk ¨ I

n ÿ

mi,˚ k,t ą 0

i“1

k“0

n ÿ

Sti

i“1

˜ ¸ ff * «ÿ " K n n ÿ ÿ b i,˚ ď max θ, ¨ fk ¨ I mk,t ą 0 ` a Sti . a i“1 i“1 k“0

(9)

Combining Eq. (4), Eq. (5), Eq. (6), and Eq. (9), we prove the theorem.

Fix an item i P rns. Without loss of generality, we assume that f1 ď ¨ ¨ ¨ ď fk0 ă

Proof of Claim 1.

f0 ď fk0 `1 ď ¨ ¨ ¨ ď fK . Note that ˜ ¸ ˜ ¸ « ff K K K ÿ ÿ ÿ ÿ ÿ ÿ ` ˘ ` ˘ i,˚ i,˚ i,˚ fk ¨ mik,t ´ fk ¨ mk,t “ f0 ¨ mi0,t ´ m0,t ` fk ¨ mik,t ´ mk,t tPA

tPA

k“0

« ÿ

´f0 ¨

“ tPA k0 ÿ

K ÿ `

tPA k“1 ff K K ÿ ÿ ÿ` ˘ ` ˘ ˘ pfk ´ f0 q ¨ mik,t ´ mi,˚ fk ¨ mik,t ´ mi,˚ “ mik,t ´ mi,˚ k,t ` k,t k,t k“0

k“1

tPA

k0 ÿ` ÿ` ˘ ÿ ˘ i,˚ i pfk ´ f0 q ¨ pfk ´ f0 q ¨ mk,t ´ mk,t “ m̂ik,t ´ mi,˚ k,t , tPA

k“1

(10)

tPA

where the inequality is because fk ě f0 and mik,t “ 0 for all k ą k0 , by the Order-Size F-Priority algorithm, and the last equality is because the algorithm follows the pure priority-based greedy policy during periods t P A. We further have Eq. (10) “

kÿ 0 ´1 j“1

pfj ´ fj`1 q ¨

j ÿ ÿ `

k0 ÿ ÿ ˘ ` i ˘ p q m̂ik,t ´ mi,˚ ` f ´ f ¨ m̂k,t ´ mi,˚ k0 0 k,t k,t ď 0,

k“1 tPA

(11)

k“1 tPA

Where the inequality is due to that fj ď fj`1 @j P t1, . . . , k0 ´ 1u, fk0 ď f0 , and that ˘ řj ř ` i i,˚ k“1 tPA m̂k,t ´ mk,t ě 0 holds for all j P t1, . . . , k0 u (which is guaranteed by Lemma 1, as A contains all time periods in which the policy uses at least one FDC to fulfill the order). Combining Eq. (10) and Eq. (11), we prove the claim.

Lower Bound. The next theorem establishes a lower bound on the competitive ratio of any online fulfillment policy under Assumption 1 for the case K ě 2. The full proof is deferred to Section EC.1.2 of the e-companion. The corresponding lower bound for the case K “ 1 will be presented later in Theorem 7.

Theorem 2. Under Assumption 1, for any K ě 2 and any given fixed costs tfk uK k“0 , every online ! ! )) b fulfillment policy satisfies RpALGq ě max 1, 4a , 14 maxně2 min n, min f0 f `na . kPrKs k

We now compare the above lower bound with the upper bound established in Theorem 1. The following proposition shows that the two bounds match up to a constant factor, which implies the order-optimality of our Order-Size F-Priority algorithm. The proof is straightforward, and is deferred to Section EC.1.3 of the e-companion. Proposition 1. The upper bound in Theorem 1 and the lower bound in Theorem 2 match up to ? a constant factor of 2p1 ` 5q ď 6.473. 3.4.

Scenario-specific Instantiation: Time-invariant Variable Costs

In this section, we instantiate the Gated Priority-based Greedy framework for the setting with time-invariant variable costs, as formalized in the following assumption. Assumption 2. The variable costs are time-invariant; that is, cik,t ” cik for all k, i, and t. This assumption is widely adopted in prior work (Jasin and Sinha 2015, Zhao et al. 2025, Amil et al. 2025). Under this setting, the variable costs are known to the online algorithm in advance. We instantiate the Gated Priority-based Greedy framework using the Variable-Cost priority rule, which ranks DCs for each item i in nondecreasing order of variable cost cik , together with the Cost-Comparison gating condition, which is triggered whenever the total cost of fulfilling the order by priority-based greedy allocations exceeds the cost of fulfilling the entire order through the RDC. The formal definitions of the algorithm, the priority rule, and the gating condition are provided in Algorithm 3. Algorithm 3 Cost-Comparison V-Priority Instantiate Gated Priority-based Greedy using: • Variable-Cost priority: for @i P rns, define ăi as k ăi j ô cik ă cij or cik “ cij , k ă j; • Cost-Comparison gating condition: ˜ « ˜ ¸ ff ¸ ˆ ˙ K n n n ÿ ÿ ÿ ÿ ␣ ( i i i i i i i i G fk , ck , St , m̂k,t k“0,...,K “ I fk ¨ I m̂k,t ą 0 ` ck ¨ m̂k,t ą f0 ` c0 ¨ St . i“1,...,n

k“0

i“1

As discussed in Section 3.1, under the time-invariant variable cost assumption, the main source of worst-case loss comes from the variable costs. This observation motivates the use of the VariableCost priority rule. At the same time, the Cost-Comparison gating condition prevents excessive activation of FDCs and the resulting large fixed costs. The following Theorem 3 establishes an upper bound on the competitive ratio of the Cost-Comparison V-Priority algorithm.

Theorem 3. Under Assumption 2, the competitive ratio of Cost-Comparison V-Priority defined in Algorithm 3 satisfies #

Rinv pCost-Comparison V-Priorityq ď max Proof.

f0 `

kPrKs fk

minkPrKs fk

, 2 .

K Let tmi,˚ k,t uk“0 denote the fulfillment plan of the optimal offline policy. For simplicity,

we also denote f “ minkPrKs fk as the minimal fixed cost among all FDCs. We define the costs incurred at period t by the optimal offline policy and by the Cost-Comparison V-Priority policy, respectively, as « ˜ ¸ ff K n n ÿ ÿ ÿ Vt˚ “ fk ¨ I mi,˚ ` cik ¨ mi,˚ k,t ą 0 k,t , k“0

i“1

Vt “

i“1

K ÿ

fk ¨ I

n ÿ

mik,t ą 0 `

i“1

k“0

n ÿ

cik ¨ mik,t .

i“1

Then, we have pcost incurred by Cost-Comparison V-Priorityq “

T ÿ

Vt ,

OPT “

t“1

T ÿ

Vt˚ .

t“1

At each time period t, we define an intermediate cost V̄t as follows: ˜ ¸ $ K n n ÿ ÿ ÿ ’ ’ i ’ f ` f ¨ I m ą 0 ` ci0 ¨ Sti , (if OPT only uses RDC) ’ k k,t & 0 i“1 i“1 k“1 V̄t “ K K ÿ n ’ ÿ ÿ ’ ’ ’ f ` f ` cik ¨ mi,˚ (otherwise) k % 0 k,t . k“1

(12)

k“0 i“1

Step I: Upper bounding the intermediate costs. We first prove the following upper bound on the intermediate costs:

V̄t ď max

f0 `

řK

k“1 fk

, 2 ¨ Vt˚ .

(13)

For time periods t where OPT uses only the RDC to fulfill the order, the cost of OPT is Vt˚ “ řn f0 ` i“1 ci0 ¨ Sti . If Cost-Comparison V-Priority uses only the RDC as well, then we have the intermediate cost V̄t “ Vt˚ . If Cost-Comparison V-Priority uses at least one FDC, then we `řn ˘ řn ‰ řK “ know that the gating condition is not triggered, i.e., k“0 fk ¨ I i“1 mik,t ą 0 ` i“1 cik ¨ mik,t ď řn f0 ` i“1 ci0 ¨ Sti ; in this case, we have ˜ ¸ K n n n ÿ ÿ ÿ ÿ i V̄t “ f0 ` fk ¨ I mk,t ą 0 ` ci0 ¨ Sti ď 2f0 ` 2 ci0 ¨ Sti ď 2Vt˚ . k“1

i“1

For time periods t where OPT uses at least one FDC to fulfill the order, we bound the intermediate cost as follows: V̄t “ f0 `

K ÿ k“1

fk `

n K ÿ ÿ k“0 i“1

f0 ` cik ¨ mi,˚ k,t ď

řK

k“1 fk

¨ Vt˚ .

Combining both cases above, we prove the upper bound in Eq. (13). Step II: Upper bounding our algorithm’s cost via the intermediate costs. We upper bound that the total cost of Cost-Comparison V-Priority as follows: T ÿ

Vt ď

t“1

T ÿ

(14)

V̄t .

t“1

To prove Eq. (14), we let A be the set of time periods that Cost-Comparison V-Priority uses at least one FDC to fulfill the order. We consider the following cases. řn • Case 1. For periods t R A, we have Vt “ f0 ` i“1 ci0 ¨ Sti . — Case 1a. If OPT uses RDC only, then we further have Vt “ V̄t . — Case 1b. If OPT uses at least one FDC, since the gating condition is triggered, we have « ˜ ¸ ff n K n n ÿ ÿ ÿ ÿ i i i i i Vt “ f0 ` c0 ¨ St ď fk ¨ I m̂k,t ą 0 ` ck ¨ m̂k,t i“1

i“1

k“0

ď f0 `

K ÿ k“1

fk `

K ÿ n ÿ

i“1

cik ¨ m̂ik,t “ V̄t `

k“0 i“1

K ÿ n ÿ

k“0 i“1

cik ¨ m̂ik,t ´

K ÿ n ÿ

cik ¨ mi,˚ k,t

. (15)

k“0 i“1

• Case 2. For periods t P A, we have mik,t “ m̂ik,t for all k, i. If OPT uses RDC only, the definition `řn ˘ řn řK řK of V̄t implies that V̄t “ f0 ` k“1 fk ¨ I i“1 mik,t ą 0 ` i“1 k“0 cik ¨ mi,˚ k,t , and therefore « ˜ ¸ ff ˜ ¸ K n n K ÿ n K ÿ n ÿ ÿ ÿ ÿ ÿ Vt “ fk ¨ I mik,t ą 0 ` cik ¨ m̂ik,t ď V̄t ` cik ¨ m̂ik,t ´ cik ¨ mi,˚ . (16) k,t k“0

i“1

k“0 i“1

If OPT uses at least one FDC, then we may also verify that have Eq. (16) holds. Summarizing the cases above, let B Ě A be the set of time periods that either Cost-Comparison V-Priority or OPT uses at least one FDC to fulfill the order, and we have that ˜ ¸ K ÿ n K ÿ n ÿ ÿ ÿ Vt ď V̄t ` cik ¨ m̂ik,t ´ cik ¨ mi,˚ . k,t tPB

k“0 i“1

(17)

k“0 i“1

On the other hand, the following claim can be proved using our key technical Lemma 1. The proof of the claim uses similar arguments as Claim 1, and is deferred to Section EC.1.4 of the e-companion. ¯ ř ´ř ¯ ř ´řK i K i,˚ i i Claim 2. For each item i P rns, we have tPB c ¨ m̂ ď c ¨ m k,t . k,t k“0 k tPB k“0 k Combining Eq. (17) and Claim 2, we establish Eq. (14). Finally, we prove the theorem by combining Eq. (13) and Eq. (14).

Lower Bound. The next theorem establishes a lower bound on the competitive ratio of any online fulfillment policy under Assumption 2 for all K ě 1. The proof is deferred to Section EC.1.2 of the e-companion. A refined lower bound for the case of K “ 1 will be presented later in Theorem 9.

Theorem 4. Under Assumption 2, for any K ě 1 and any given fixed costs tfk uK k“0 , every online ř f0 `

fulfillment policy satisfies Rinv pALGq ě min kPrKsf k . kPrKs k

This theorem shows that the lower bound on the competitive ratio coincides exactly with the upper bound attained by the Cost-Comparison V-Priority algorithm whenever the fixed costs satisfy ř f0 ` kPrKs fk ě 2. Therefore, under Assumption 2, in the case K ě 2, or when K “ 1 and f0 ě f1 , minkPrKs fk

Cost-Comparison V-Priority achieves the exact optimal competitive ratio.

Refinements for Single-FDC Settings

While the algorithms presented in Section 3 apply to any number of FDCs K ě 1, their competitive ratio guarantees may be further improved in the single-FDC setting (K “ 1), which is the focus of this section. In Section 4.1, we study the single-FDC setting with time-varying variable costs, whereas in Section 4.2, we consider the corresponding setting with time-invariant variable costs. 4.1.

Time-varying Variable Costs with Single FDC

In this section, we present an improved algorithm for the time-varying variable cost setting with a single FDC. The algorithm also operates under Assumption 1, namely, that the variable costs lie in the interval ra, bs. Our approach is a hybrid algorithm that combines two sub-algorithms: the first achieves a better dependence on b{a, while the second further improves the competitive ratio when f0 ě f1 . Both are based on variants of the Gated Priority-based Greedy framework, with slight modifications to incorporate time-dependent priority rules and FDC-gating conditions that route the entire order to the FDC rather than the RDC. We first present the two sub-algorithms, then combine them into a hybrid algorithm and characterize its competitive ratio, and finally complement this result with a lower bound on the competitive ratio of any algorithm. The first sub-algorithm: improve the dependence on b{a. Compared with Theorem 1, when the fixed costs are held fixed, our first refined algorithm improves the competitive ratio from Opb{aq a to Op b{aq. This algorithm is also an instantiation of our Gated Priority-based Greedy framework. To improve the dependence on the variable cost parameters, we can no longer neglect the losses induced by variable costs, as we did in Order-Size F-Priority (Algorithm 2, Section 3.3). Motivated by this consideration, we introduce the Adjusted-Variable-Cost priority rule, which ranks a the FDC and RDC by comparing ci1,t with a{b ¨ ci0,t . However, the main risk of using the AdjustedVariable-Cost priority rule is analogous to that of using the Variable-Cost priority rule in Cost-Comparison V-Priority (Algorithm 3, Section 3.4): it may lead to excessive activation of the FDC and thus incur a large fixed cost. To control this risk, we adopt the same Cost-Comparison gating condition as in Cost-Comparison V-Priority.

We also note that the Adjusted-Variable-Cost priority rule is time-dependent, in the sense that the ranking may vary across time periods, whereas our original Gated Priority-based Greedy framework only admits time-invariant priority rankings. Nevertheless, it is straightforward to extend the Gated Priority-based Greedy framework to allow the algorithm to use a timedependent priority rule at each time period. The formal definitions of the improved algorithm, the priority rule, and the gating condition are provided in Algorithm 4. Algorithm 4 Cost-Comparison AdjV-Priority (single FDC) Extend Gated Priority-based Greedy by replacing all time-independent priority rules ăi with time-dependent priority rules ăi,t in Algorithm 1, and instantiate the resulting framework using: a • Adjusted-Variable-Cost priority: for @i P rns, define ăi as 1 ăi,t 0 ô ci1,t ă ab ¨ ci0,t ; • Cost-Comparison gating condition: ˜ « ˜ ¸ ff ¸ ˆ ˙ n n n ÿ ÿ ÿ ÿ ␣ ( G fk , cik,t , Sti , m̂ik,t k“0,1 “ I fk ¨ I m̂ik,t ą 0 ` cik,t ¨ m̂ik,t ą f0 ` ci0,t ¨ Sti . i“1,...,n

k“0,1

i“1

The following theorem provides an upper bound for the competitive ratio of Cost-Comparison AdjV-Priority. Its proof uses a similar technique as that of Theorem 3. Theorem 5. Under Assumption 1, the competitive ratio of Cost-Comparison AdjVPriority defined in Algorithm 4 satisfies #

RpCost-Comparison AdjV-Priorityq ď 1 ` max Proof.

f0 , f1

c + b . a

K Let tmi,˚ k,t uk“0 denote the fulfillment plan of the optimal offline policy. For simplicity, we

also denote f “ minkPrKs fk as the minimal fixed cost among all FDCs. We define the costs incurred at period t by the optimal offline policy and by the Cost-Comparison AdjV-Priority policy, respectively, as « ˜ ¸ ff n n ÿ ÿ ÿ i,˚ i,˚ i ˚ Vt “ fk ¨ I mk,t ą 0 ` ck,t ¨ mk,t , k“0,1

i“1

Vt “

fk ¨ I

k“0,1

n ÿ

mik,t ą 0

n ÿ

i“1

cik,t ¨ mik,t

i“1

Then, we have pcost incurred by Cost-Comparison AdjV-Priorityq “

T ÿ t“1

Vt ,

OPT “

T ÿ

Vt˚ .

t“1

At each time period t, we define an intermediate cost V̄t as follows: ¸ c ˜ $ n n ÿ ’ b ÿ i i ’ ’ ¨ c0,t ¨ Sti , (if OPT only uses RDC) f ` f ¨ I m ą 0 ` 0 1 ’ 1,t & a i“1 i“1 ¸ V̄t “ c ˜n n ’ ÿ ÿ ’ b ’ ’ . (otherwise) ci0,t ¨ mi,˚ ci1,t ¨ mi,˚ %f0 ` f1 ` a ¨ 0,t ` 1,t i“1 i“1

(18)

The proof of the following claim is similar to Steps I and II in the proof of Theorem 3. It also uses a variant of Lemma 1 for the extended Gated Priority-based Greedy framework with time-dependent priority rules in the case K “ 1, whose proof parallels that of Lemma 1. The proof of Claim 3 and the corresponding lemma details are deferred to Section EC.1.6 of the e-companion. b ) ! Claim 3. For each time period t, we have V̄t ď max 1 ` ff10 , 1 ` ab ¨ Vt˚ . Furthermore, we have řT řT t“1 Vt ď t“1 V̄t . Finally, we prove the theorem by combining the two equations in Claim 3.

The second sub-algorithm: improve the performance when f0 ě f1 . Algorithm 4 improves a the competitive ratio dependence on b{a from Opb{aq to Op b{aq. However, there remains a gap between its overall competitive ratio and the true lower bound, as will be established in Theorem 7. This gap is particularly pronounced in the regime where f0 {f1 is large, and arises mainly because the algorithm tends to use the RDC excessively, even when the FDC has abundant inventory. To further improve the competitive ratio in this regime, we slightly revise the Gated Prioritybased Greedy framework to FDC-Gated Priority-based Greedy. In this variant, the gating condition is replaced by the FDC-gating condition, which ensures that the algorithm uses the FDC rather than the RDC whenever the FDC inventory is sufficient to fulfill the order. Specifically, Lines 5–6 of Algorithm 1 (for K “ 1) are revised as follows, and all time-independent priority rules ăi elsewhere in the algorithm are replaced with time-dependent priority rules ăi,t , as in Algorithm 4: 5:

i if gating condition Gptfk , cik,t , Sti , m̂ik,t uq “ 1 and @i P rns, I1,t´1 ě Sti then

mi1,t Ð Sti , mi0,t Ð 0

@i P rns

Ź route entire order to FDC

We instantiate the FDC-Gated Priority-based Greedy framework using the Order-Size gating condition, which is triggered when the total order size does not exceeds a predefined threshold θ. For the time-dependent priority rule, we employ the Adjusted-Variable-Cost priority rule (a slightly more general version than that used in Algorithm 4), where the FDC variable cost is adjusted using a general parameter η. The complete description of the improved algorithm is provided in Algorithm 5. The following theorem provides an upper bound on the competitive ratio of Order-Size AdjVPriority. Its proof follows a framework similar to that of Theorem 5, in that it constructs an intermediate cost V̄t to relate the cost incurred by the algorithm to that of the optimal offline policy. However, the construction of V̄t is more involved and requires a case-by-case analysis. The full proof is deferred to Section EC.1.9 of the e-companion.

Algorithm 5 Order-Size AdjV-Priority (single FDC, input parameters η ě 1, θ ě 0) Instantiate the FDC-Gated Priority-based Greedy framework using: • Adjusted-Variable-Cost priority (param. η): @i P rns, define ăi as 1 ăi,t 0 ô ci1,t ă ci0,t {η; • Order-Size FDC-gating condition (param. θ): ˆ

˙ ␣

(

fk , cik,t , Sti , m̂ik,t k“0,...,K i“1,...,n

n ÿ

“I

Sti ď θ

i“1

Theorem 6. Suppose f0 ě f1 . Under Assumption 1, choosing η “

maxtf0 {2, bu a

f0 and θ “ 2aη , we

have that the competitive ratio of Order-Size AdjV-Priority defined in Algorithm 5 satisfies c ? max tf0 {2, bu . RpOrder-Size AdjV-Priorityq ď p4 ` 2q a Final algorithm by choosing the better of the two. Our final algorithm for the timevarying variable cost setting with a single FDC chooses the better of the two algorithms introduced above. Specifically, the Better-of-Two algorithm chooses Algorithm 4 whenever f0 ď f1 a a a ? or 1 ` maxtf0 {f1 , b{au ď p4 ` 2q maxt f0 {p2aq, b{au, and it chooses Algorithm 5 otherwise. The following corollary upper bounds the competitive ratio of this hybrid algorithm. The proof of Corollary 1 is deferred to Section EC.1.10 of the e-companion. Corollary 1. Under Assumption 1, in the single-FDC setting, we have # # + c c + ? f0 b max tf0 {2, bu RpBetter-of-Twoq ď min 1 ` max , , p4 ` 2q ` 8 ¨ Ipf0 ă f1 q f1 a a # # c + c + ? ? f0 b f0 ď max min 2 ¨ , p2 2 ` 1q , p4 ` 2q . f1 a a Lower Bound. The next theorem establishes a lower bound on the competitive ratio of any online fulfillment policy under Assumption 1 for the case K “ 1. Moreover, this lower bound matches, up to a constant factor, the upper bound of the Better-of-Two policy given in Corollary 1. The proof of Theorem 7 is deferred to Section EC.1.11 of the e-companion. Theorem 7. Under Assumption 1 and in the case of K “ 1, for any fixed costs f0 and f1 of the RDC and FDC, any online fulfillment policy has a competitive ratio of at least RpALGq ě b ! )) ! 0 max 1, 13 ab , 14 maxně2 min n, f1f`na . We now compare the above lower bound with the upper bound established in Corollary 1. The following proposition shows that the two bounds match up to a constant factor, which implies the order-optimality of our Better-of-Two algorithm. The proof is straightforward, and is deferred to Section EC.1.12 of the e-companion.

Proposition 2. The upper bound in Corollary 1 and the lower bound in Theorem 7 match up to ?

a constant factor of ?4¨p9`4? 2q ď 19.828. 10`4 2´1

4.2.

Time-Invariant Variable Costs Case

In this section, we present an improved algorithm for the single-FDC case in the time-invariant variable cost setting. Our goal is to improve the competitive ratio in the regime f0 ă f1 , where CostComparison V-Priority achieves a competitive ratio of 2 (Theorem 3). As in Cost-Comparison V-Priority, we adopt the Variable-Cost priority rule. However, for the gating condition, we introduce a soft version of the Cost-Comparison gating condition by incorporating randomization based on the difference in variable cost between the greedy allocation and the fully-RDC allocation. Specifically, we define a monotone nonincreasing function p : R Ñ r0, 1s that maps the variable cost řn difference i“1 pci0 ´ ci1 q ¨ m̂i1,t to the probability with which the gating condition is triggered. We refer to this gating condition as Randomized-Cost-Comparison, and the precise definition of pp¨q is given in Eq. (19). The intuition behind this design is as follows. When the variable cost increment of switching the řn FDC allocations entirely to RDC is small relative to the fixed FDC cost (i.e., i“1 pci0 ´ ci1 q ¨ m̂i1,t ď f1 ), it is more cost-effective to fulfill the order entirely from the RDC, so we set pp¨q “ 1. As the variable cost increment grows, the benefit of using the RDC decreases, and we gradually reduce the probability řn of routing the order to the RDC. Once the increment exceeds a threshold (i.e., i“1 pci0 ´ ci1 q ¨ m̂i1,t ą ! ) f2 max f1 , f10 ´ f0 ), it becomes more cost-effective to use the FDC, and we set pp¨q “ 0. The resulting algorithm is a natural randomized extension of Gated Priority-based Greedy. A complete description of the algorithm is provided in Algorithm 6. Algorithm 6 Randomized-Cost-Comparison V-Priority (single FDC) Instantiate Gated Priority-based Greedy with randomized gating condition using: • Variable-Cost priority: for @i P rns, define ăi as 1 ăi 0 ô ci1 ă ci0 , @i P rns; • Randomized-Cost-Comparison gating condition: ˜ ˜ ¸¸ ˆ ˙ n ÿ ␣ ( ` ˘ ci0 ´ ci1 ¨ m̂i1,t G fk , cik , Sti , m̂ik,t k“0,...,K “ Bernoulli p , i“1,...,n

where

i“1

$ 1, ’ ’ & f 2 ´pf `xqf

x ď f1 ,

! ) f12 , f ă x ď max f , ´ f 1 1 f 0 , ppxq “ f12 `pf0 `xqpx´f1 q 0) ! ’ 2 ’ f %0, x ą max f1 , f10 ´ f0 . 1

(19)

The following theorem provides upper bounds the competitive ratio of Randomized-CostComparison V-Priority. Its proof uses a similar technique as that of Theorem 3.

Theorem 8. Let w “ ff10 . Under Assumption 2, the competitive ratio of the Randomized-CostComparison V-Priority defined in Algorithm 6 satisfies #

1 ` 1´w`21?1´w , Rinv pRandomized-Cost-Comparison V-Priorityq ď 1`w Proof.

w ă 5´1 ?2 . w ě 5´1 2

Define the cost incurred by the optimal offline policy and the Randomized-Cost-

Comparison V-Priority fulfillment policy at time period t as ˜ ¸ ˜ ¸ n n n n ÿ ÿ ÿ ÿ i,˚ i,˚ ˚ Vt “ f 0 ¨ I m0,t ą 0 ` f1 ¨ I m1,t ą 0 ` ci0 ¨ mi,˚ ` ci1 ¨ mi,˚ 0,t 1,t , i“1

Vt “ f0 ¨ I

n ÿ

i“1

mi0,t ą 0 ` f1 ¨ I

i“1

n ÿ

i“1

mi1,t ą 0 `

i“1

n ÿ

i“1

ci0 ¨ mi0,t `

i“1

n ÿ

ci1 ¨ mi1,t .

i“1

Then the total cost incurred by the Randomized-Cost-Comparison V-Priority fulfillment policy and optimal offline policy can be written as pcost incurred by Randomized-Cost-Comparison V-Priorityq “

T ÿ

Vt ,

OPT “

t“1

T ÿ

Vt˚ .

t“1

Let I “ ti P rns : ci1 ă ci0 u. At each time period t, we define an intermediate cost V̄t as follows: $ n ÿ ` i,˚ ˘` ÿ ’ i i i ’ ’f0 ` pc1 ´ c0 q ¨ m1,t ´ m̂1,t ` ci0 ¨ Sti , if θt “ 1, ’ & i“1 iPI ˜ ¸ ˜ ¸ V̄t “ n n n ÿ ÿ ÿ ÿ ’ ’ i,˚ i i i i ’ f ¨ I m ą 0 ` f ¨ I m ą 0 ` p c ´ c q ¨ m ` ci0 ¨ Sti , if θt “ 0. ’ 0 1 1,t 0,t 1,t 1 0 % i“1

i“1

iPI

The proof of the following claim is similar to Steps I and II in the proof of Theorem 3. The proof of Claim 4 is deferred to Section EC.1.13 of the e-companion. Claim 4. Let Ft´1 denote the filtration up to time period t ´ 1. We have the following inequalities: # ? T T ÿ ÿ 1 ` 1´w`21?1´w , if w ă 5´1 ErV̄t |Ft´1 s ?2 Vt ď V̄t , and ď , @ t P rT s. (20) ˚ 5´1 V 1 ` w, if w ě t t“1 t“1 2 Finally, we prove the theorem by combining the inequalities in Eq. (20).

The next theorem, proved in Section EC.1.14, gives a lower bound on the competitive ratio for any online fulfillment policy under Assumption 2 for K “ 1. It also matches the upper bound of the Randomized-Cost-Comparison V-Priority in Theorem 8 within a constant factor. Theorem 9. Under Assumption 2 and K “ 1, given the fixed costs f0 and f1 of the DCs, any ! ) online fulfillment policy ALG has a competitive ratio of at least Rinv pALGq ě max 1 ` ff01 , 54 . Comparing the upper and lower bounds in Theorem 8 and Theorem 9, we can see that when the ratio of the fixed costs w “ ff01 is large enough, i.e., w ě

5´1 , the upper and lower bounds match 2

exactly, implying the optimality of our Randomized-Cost-Comparison V-Priority algorithm. ?

When w ă 5´1 , the upper and lower bounds are still of the same order within a constant factor of 2 ? ` ` ˘˘ 1 ` 1{ 0.75 ` 2 0.75 {1.25 ď 1.123.

Experiments

We conduct numerical experiments to examine whether the proposed policies preserve their theoretical advantages in representative stochastic environments and under deliberately challenging demand sequences. We summarize the main findings below. Overall, the results indicate that our policies achieve a favorable balance between computational efficiency and fulfillment-cost performance. In stochastic instances, they attain fulfillment costs comparable to those of computationally more demanding myopic and forecast-based benchmark policies. Under stressful temporal demand patterns, the gating mechanism can further yield substantial cost savings by mitigating premature depletion of scarce FDC inventory. Complete experimental settings and detailed results are provided in Section EC.2. Experimental setting. We evaluate the proposed policies in both the time-varying and time-invariant variable-cost settings using stochastic order-arrival instances in two-layer fulfillment networks with scarce FDC inventory and an unlimited-backup RDC. The experiments vary key problem dimensions, including the selling horizon and the number of FDCs, and compare our policies with generalized myopic and, where applicable, forecast-based LP policies. We additionally construct stress-test instances to examine the inventory-depletion failure mode that motivates the gating mechanism. Detailed parameter settings, benchmark definitions, and implementation information are provided in Section EC.2.1, and the baseline algorithms are specified in Section EC.2.5. Time-varying variable costs. We first compare Order-Size F-Priority with the generalized myopic policy in multi-FDC networks. As the selling horizon increases, Order-Size F-Priority attains fulfillment costs comparable to, and in several instances lower than, those of the myopic policy, while requiring substantially less computation. We then vary the number of FDCs. The running time of the myopic policy grows rapidly with network size, consistent with the computational intractability of per-order cost minimization, whereas the running time of Order-Size F-Priority remains nearly stable and its fulfillment cost remains close to that of the myopic benchmark. In the single-FDC setting, Order-Size AdjV-Priority similarly achieves costs comparable to, and often lower than, those of the myopic policy as the horizon increases. Please refer to Section EC.2.2 for details. Time-invariant variable costs. We next compare Cost-Comparison V-Priority with the generalized myopic policy and four forecast-based LP policies, namely IPFC, DPFC, Dilate, and ForceOpen. Although the LP-based policies receive the true demand distribution, CostComparison V-Priority achieves comparable fulfillment costs while requiring substantially less running time. This computational advantage becomes more pronounced as the number of FDCs

grows: the running times of both the myopic and LP-based policies increase with network size, whereas that of Cost-Comparison V-Priority remains nearly unchanged. In the single-FDC setting, Randomized-Cost-Comparison V-Priority also achieves cost performance comparable to the myopic and LP-based benchmarks. Please refer to Section EC.2.3 for details. Stress test. Finally, we construct a family of time-varying instances in which an initial large order is followed by many small orders, so that a myopic policy exhausts scarce FDC inventory prematurely. In these instances, Order-Size F-Priority achieves substantially lower fulfillment costs than the myopic policy, and the gap increases as the RDC fixed cost grows. This experiment illustrates the operational role of the gating mechanism: it protects local inventory against demand sequences under which immediate cost minimization can lead to severe future fixed-cost exposure. Please refer to Section EC.2.4 for details.

Conclusion

In this paper, we study a general multi-item online order fulfillment problem with multi-unit demand, multiple distribution centers, and rich cost structures. Our main goal is to bridge a practically important managerial problem with a sharp theoretical question: how well can a simple real-time fulfillment policy perform relative to a clairvoyant planner when future demand is unknown? To answer this question, we develop a family of Gated Priority-based Greedy policies, identify the cost regimes under which different variants are effective, and derive upper and lower bounds that establish optimality or near-optimality in several settings. Beyond the formal guarantees, the paper contributes a clear operational message. The key to realtime fulfillment is not merely choosing the cheapest facility for the current order; it is managing the intertemporal value of scarce local inventory. Our results show that this dynamic trade-off can often be handled by simple and interpretable gating rules, which is encouraging for firms seeking solutions that are both analytically grounded and practically deployable. Our work provides a systematic framework for designing and analyzing online fulfillment policies for modern e-commerce networks. Promising directions for future research include incorporating replenishment decisions, integrating online and store-based demand in omnichannel settings, allowing endogenous service promises or pricing, and studying learning-augmented variants in which forecasts are available but imperfect.

References Acimovic J, Graves SC (2015) Making Better Fulfillment Decisions on the Fly in an Online Retail Environment. Manufacturing & Service Operations Management 17(1):34–51, ISSN 1523-4614, 1526-5498, URL http://dx.doi.org/10.1287/msom.2014.0505.

31 Acimovic J, Graves SC (2017) Mitigating Spillover in Online Retailing via Replenishment. Manufacturing & Service Operations Management 19(3):419–436, ISSN 1523-4614, 1526-5498, URL http://dx.doi. org/10.1287/msom.2016.0614. Amil A, Makhdoumi A, Wei Y (2025) Multi-Item Order Fulfillment Revisited: LP Formulation and Prophet Inequality. Management Science ISSN 0025-1909, URL http://dx.doi.org/10.1287/mnsc.2023. 00357. Andrews JM, Farias VF, Khojandi AI, Yan CM (2019) Primal–Dual Algorithms for Order Fulfillment at Urban Outfitters, Inc. INFORMS Journal on Applied Analytics 49(5):355–370, ISSN 2644-0865, 26440873, URL http://dx.doi.org/10.1287/inte.2019.1013. Ball MO, Queyranne M (2009) Toward Robust Revenue Management: Competitive Analysis of Online Booking. Operations Research 57(4):950–963, ISSN 0030-364X, 1526-5463, URL http://dx.doi.org/10. 1287/opre.1080.0654. Buchbinder N, Naor J (2009) The Design of Competitive Online Algorithms via a Primal-Dual Approach. Foundations and Trends in Theoretical Computer Science 3(2–3):93–263, URL http://dx.doi.org/ 10.1561/0400000024. Bumpensanti P, Wang H (2020) A Re-Solving Heuristic with Uniformly Bounded Loss for Network Revenue Management. Management Science 66(7):2993–3009, ISSN 0025-1909, 1526-5501, URL http://dx. doi.org/10.1287/mnsc.2019.3365. Goedhart J, Haijema R, Akkerman R, de Leeuw S (2023) Replenishment and fulfilment decisions for stores in an omni-channel retail network. European Journal of Operational Research 311(3):1009–1022, ISSN 0377-2217, URL http://dx.doi.org/10.1016/j.ejor.2023.06.018. Govindarajan A, Sinha A, Uichanco J (2021) Joint inventory and fulfillment decisions for omnichannel retail networks. Naval Research Logistics (NRL) 68(6):779–794, ISSN 0894-069X, 1520-6750, URL http: //dx.doi.org/10.1002/nav.21969. Goyal V, Iyengar G, Udwani R (2025) Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources. Operations Research 73(4):1897–1915, ISSN 0030-364X, 1526-5463, URL http: //dx.doi.org/10.1287/opre.2021.0695. Harsha P, Subramanian S, Uichanco J (2019) Dynamic Pricing of Omnichannel Inventories. Manufacturing & Service Operations Management 21(1):47–65, ISSN 1523-4614, 1526-5498, URL http://dx.doi.org/ 10.1287/msom.2018.0737. He S, Wei Y, Xu J, Yu SH (2025) Online Resource Allocation without Re-solving: The Effectiveness of Primal-Dual Policies. URL http://dx.doi.org/10.2139/ssrn.5133857. Hübner A, Hense J, Dethlefs C (2022) The revival of retail stores via omnichannel operations: A literature review and research framework. European Journal of Operational Research 302(3):799–818, ISSN 03772217, URL http://dx.doi.org/10.1016/j.ejor.2021.12.021.

32 Jasin S, Kumar S (2012) A Re-Solving Heuristic with Bounded Revenue Loss for Network Revenue Management with Customer Choice. Mathematics of Operations Research 37(2):313–345, ISSN 0364-765X, 1526-5471, URL http://dx.doi.org/10.1287/moor.1120.0537. Jasin S, Sinha A (2015) An LP-Based Correlated Rounding Scheme for Multi-Item Ecommerce Order Fulfillment. URL http://dx.doi.org/10.13140/RG.2.1.2970.5680. Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing - STOC ’90, 352–358 (Baltimore, Maryland, United States: ACM Press), ISBN 978-0-89791-361-4, URL http: //dx.doi.org/10.1145/100216.100262. Lan Y, Gao H, Ball MO, Karaesmen I (2008) Revenue Management with Limited Demand Information. Management Science 54(9):1594–1609, ISSN 0025-1909, 1526-5501, URL http://dx.doi.org/10.1287/ mnsc.1080.0859. Lei YM, Jasin S, Sinha A (2018) Joint Dynamic Pricing and Order Fulfillment for E-commerce Retailers. Manufacturing & Service Operations Management 20(2):269–284, ISSN 1523-4614, 1526-5498, URL http://dx.doi.org/10.1287/msom.2017.0641. Ling Z, Jiang J, Xin L (2026) Online Order Fulfillment with Replenishment. URL http://dx.doi.org/10. 48550/arXiv.2603.04065. Ma W (2023) Order-Optimal Correlated Rounding for Fulfilling Multi-Item E-Commerce Orders. Manufacturing & Service Operations Management 25(4):1324–1337, ISSN 1523-4614, 1526-5498, URL http://dx.doi.org/10.1287/msom.2023.1219. Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. Journal of the ACM 54(5):22, ISSN 0004-5411, 1557-735X, URL http://dx.doi.org/10.1145/1284320.1284321. Qiu R, Hou L, Sun Y, Sun M, Sun Y (2021) Joint pricing, ordering and order fulfillment decisions for a dualchannel supply chain with demand uncertainties: A distribution-free approach. Computers & Industrial Engineering 160:107546, ISSN 0360-8352, URL http://dx.doi.org/10.1016/j.cie.2021.107546. Shen M, Tang CS, Wu D, Yuan R, Zhou W (2024) JD.com: Transaction-Level Data for the 2020 MSOM Data Driven Research Challenge. Manufacturing & Service Operations Management (M&SOM) (INFORMS) 26(1):2–10, ISSN 1523-4614, URL http://dx.doi.org/10.1287/msom.2020.0900. Simchi-Levi D, Zheng Z, Zhu F (2025) On Greedy-Like Policies in Online Matching with Reusable Network Resources and Decaying Rewards. Management Science 71(10):8908–8926, ISSN 0025-1909, 1526-5501, URL http://dx.doi.org/10.1287/mnsc.2023.02588. Wei L, Kapuscinski R, Jasin S (2021) Shipping Consolidation Across Two Warehouses with Delivery Deadline and Expedited Options for E-commerce and Omni-channel Retailers. Manufacturing & Service Operations Management 23(6):1634–1650, ISSN 1523-4614, 1526-5498, URL http://dx.doi.org/10. 1287/msom.2020.0903.

33 Xie Y, Ma W, Xin L (2025) The Benefits of Delay to Online Decision Making. Management Science mnsc.2023.00549, ISSN 0025-1909, 1526-5501, URL http://dx.doi.org/10.1287/mnsc.2023.00549. Xu P, Allgor R, Graves S (2009) Benefits of Reevaluating Real-Time Order Fulfillment Decisions. Manufacturing & Service Operations Management 11:340–355, URL http://dx.doi.org/10.1287/msom. 1080.0222. Zhao Y, Wang X, Xin L (2025) Multi-item Online Order Fulfillment in a Two-Layer Network. Operations Research 73(5):2297–2305, ISSN 0030-364X, 1526-5463, URL http://dx.doi.org/10.1287/ opre.2022.0100. Zhou Q, Gumus M, Miao S (2025) E-commerce Order Fulfillment Problem with Limited Time Window. Operations Research 73(6):2914–2932, URL http://dx.doi.org/10.1287/opre.2023.0453.

ec1

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Electronic Companion EC.1.

Omitted Proofs

EC.1.1.

Proof of Lemma 1

It is clear that for all j “ 1, . . . , k0 , we have j ÿ ÿ

řj

ř i,˚ i,˚ i i k“1 mk,t ď St and tPB mk,t ď Ik,0 , which implies that # ÿ

mi,˚ k,t ď min

k“1 tPB

j ÿ

Sti ,

tPB

+ i Ik,0 .

k“1

Now we only need to prove j ÿ ÿ

# ÿ

m̂ik,t ě min

k“1 tPB

Sti ,

tPB

j ÿ

+ i Ik,0

@ j “ 1, . . . , k0 .

k“1

By the definition of the Gated Priority-based Greedy policy, for all j “ 1, . . . , k0 , we have + # j j ÿ ÿ i Ik,t´1 , @ t. m̂ik,t “ min Sti , k“1

k“1

So we only need to prove + + # # j j ÿ ÿ ÿ ÿ i i i i Ik,0 , St , Ik,t´1 ě min min St , tPB

tPB

k“1

@ j “ 1, . . . , k0 .

(EC.1)

k“1

Fix j P t1, . . . , k0 u. We prove Equation (EC.1) via two steps. !ř ) řj ř řj i i Step I. We prove that k“1 tPA m̂ik,t “ min S , I tPA t k“1 k,0 . We consider the following two cases: • Suppose

i tPA St ď

řj

i k“1 Ik,0 . For periods t P A, the Gated Priority-based Greedy policy

fulfill the order by greedy quantities, so we have m̂ik,t “ mik,t . Then we have i i Ik,t´1 “ Ik,0 ´

t´1 ÿ

i mik,τ “ Ik,0 ´

τ “1

and then

j ÿ

i Ik,t´1 “

k“1

j ÿ

i Ik,0 ´

j ÿ ÿ

m̂ik,τ ,

τ ďt´1 τ PA

m̂ik,τ ě

k“1 τ ďt´1 τ PA

k“1

j ÿ k“1

i Ik,0 ´

Sτi ě

Sti .

τ ět tPA

τ ďt´1 τ PA

! ) řj i Therefore, we have min Sti , k“1 Ik,t´1 “ Sti for t P A, and thus j ÿ ÿ k“1 tPA

m̂ik,t “

ÿ tPA

min Sti ,

j ÿ k“1

+ i Ik,t´1

# ÿ “ tPA

Sti “ min

ÿ tPA

Sti ,

j ÿ k“1

+ i Ik,0 .

ec2

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

ř řj řj řj i i i • Suppose tPA Sti ą k“1 Ik,0 . We first prove k“1 Ik,T “ 0. Assume not, i.e. k“1 Ik,T ą 0, then řj i k“1 Ik,t ą 0 for all t. Then for all t P A, the Gated Priority-based Greedy fulfillment policy

fulfills orders from the FDCs, # + j j j j j j ÿ ÿ ÿ ÿ ÿ ÿ i i i i min Sti , Ik,t´1 “ m̂ik,t “ mik,t “ Ik,t´1 ´ Ik,t ă Ik,t´1 . k“1

k“1

řj řj řj i i i This implies that for all t P A, Sti ă k“1 Ik,t´1 and k“1 Ik,t “ k“1 Ik,t´1 ´ Sti . For t R A, we řj ř j i i have k“1 Ik,t “ k“1 Ik,t´1 . Therefore, we have j ÿ

i Ik,T “

k“1

j ÿ

i Ik,0 ´

Sti ď 0,

tPA

k“1

řj i i “ 0, and therefore, ą 0. Thus we have k“1 Ik,T which contradicts the assumption that k“1 Ik,T # + j ÿ j j j j ÿ ÿ ÿ ÿ ÿ ÿ i i i i m̂ik,t “ min Sti , Ik,t´1 “ Ik,0 ´ Ik,T “ Ik,0 . řj

k“1 tPA

tPA

k“1

Step II. We prove Equation (EC.1). We consider the following two cases: řj řj řj i i i • If there exists t P B zA such that Sti ą k“1 Ik,t´1 , since k“1 Ik,t´1 ě k“1 Ik,T , then we have ! ) ř ř řj ř ř j j i i i i tPBzA min St , k“1 Ik,t´1 ě k“1 Ik,T . Therefore, we have k“1 tPBzA m̂k,t “ j ÿ ÿ

m̂ik,t “

k“1 tPB

j ÿ ÿ

m̂ik,t `

j ÿ ÿ

m̂ik,t ě

k“1 tPA

k“1 tPBzA

j ÿ

i Ik,T `

˜ j ÿ

i Ik,0 ´

k“1

j ÿ

¸ i Ik,T

j ÿ

“

k“1

i Ik,0 .

k“1

řj řj ř i i • If for all t P B zA, we have Sti ď k“1 Ik,t´1 , then we can obtain k“1 tPBzA m̂k,t “ ! ) ř ř ř j i i i tPBzA min St , k“1 Ik,t´1 “ tPBzA St . Therefore, we have j ÿ ÿ

m̂ik,t “

k“1 tPB

j ÿ ÿ k“1 tPBzA

m̂ik,t `

j ÿ ÿ

m̂ik,t ě

k“1 tPA

This completes the proof of Lemma 1. EC.1.2.

ÿ tPBzA

Sti ` min

ÿ tPA

Sti ,

j ÿ k“1

+ i Ik,0

# ě min

ÿ tPB

Sti ,

j ÿ

+ i Ik,0 .

k“1

Proof of Theorem 2

Given the number of FDCs K and fixed costs of FDCs and RDC pf0 , f1 , . . . , fK q, we denote the minimal fixed cost among all FDCs as f “ minkPrKs fk . Without loss of generality, we assume f “ f1 ď f 2 ď ¨ ¨ ¨ ď f K . ! ) f0 f0 We first prove that RpALGq ě 41 maxn min n, f `na , f `2a . We construct two instances to prove

the lower bound. In both instances, there are n items, indexed by i “ 1, 2, . . . , n. The initial inventory i of FDC 1 is I1,0 “ 1 for all items i “ 1, 2, . . . , n, and the initial inventory of other FDCs are all zero.

The variable costs are set to be constant among all DCs, items and time periods: ci0,t “ cik,t “ a for all FDCs k “ 1, 2, . . . , K. At time period t “ 1, the customer order requests one unit of items

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

ec3

i “ 1, 2, . . . , n. At each time period t “ 2, 3, . . . , n ` 1, the customer order requests one unit of items i “ t ´ 1. For the first instance I1 , we set the time period to be T “ 1, and for the second instance I2 , we set the time period to be T “ n ` 1. Let ALG be any online fulfillment policy. We consider the following two cases based on the decision of ALG at time period t “ 1. Case 1. Suppose ALG uses the RDC at time period t “ 1 with probability at least 12 . Then for instance I1 , the expected cost incurred by ALG is at least ALGpI1 q ě 12 f0 . The optimal offline policy for instance I1 uses only FDC 1 to fulfill the order, and its cost is OPTpI1 q “ f ` na. Therefore, the competitive ratio of ALG is at least ALGpI1 q 1 f0 ě . OPTpI1 q 2 f ` na Case 2. Suppose ALG uses the RDC at time period t “ 1 with probability less than 12 . Then for instance I2 , whenever ALG uses only FDC 1 at time t “ 1, it must use the RDC at all periods t “ 2, 3, . . . , n ` 1 because FDC 1 is exhausted. Therefore, the expected cost incurred by ALG is at least ALGpI2 q ě 12 nf0 . The policy that uses the RDC at time t “ 1 and then uses FDC 1 at periods t “ 2, 3, . . . , n ` 1 incurs cost f0 ` nf ` 2na. Hence the optimal offline policy satisfies OPTpI2 q ď f0 ` nf ` 2na, and the competitive ratio of ALG is at least * " nf0 1 f0 ALGpI2 q 1 . ě ě min n, OPTpI2 q 2 f0 ` npf ` 2aq 4 f ` 2a

Combining the above two cases, we have " " ** " * 1 f0 1 f0 1 f0 f0 RpALGq ě min , min n, ě min n, , . 2 f ` na 4 f ` 2a 4 f ` na f ` 2a Since we can choose n arbitrarily, we obtain the desired lower bound: " * f0 f0 1 RpALGq ě max min n, , . 4 n f ` na f ` 2a Since the ratio is at least 1, so we further have ** " " 1 f0 RpALGq ě max 1, max min n, . 4 ně2 f ` na b Now we prove that RpALGq ě 4a . We also construct two instances to prove the lower bound. In

both instances, there is only one type of items n “ 1. The initial inventories of FDC 1 and FDC 2 is N , where N is a large integer to be specified later, and the initial inventories of other FDCs are all zero. Note that we can construct such instance only when K ě 2. The time period is set to be T “ 2. At time period t “ 1, the customer order requests N units of the item, and the variable cost is c10,1 “ b, c11,1 “ a, c12,1 “ a.

ec4

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

For the first instance I1 , the customer order requests N units of the item at time period t “ 2, and the variable cost is c10,2 “ b, c11,2 “ b, c12,2 “ a. For the second instance I2 , the customer order requests N units of the item at time period t “ 2, and the variable cost is c10,2 “ b, c11,2 “ a, c12,2 “ b. Let m0 , m1 , m2 be the number of items fulfilled from RDC, FDC 1 and FDC 2 at time period t “ 1 by ALG, respectively. Here m0 , m1 , m2 may be random variables. Then the cost incurred at time t “ 1 is at least b ¨ m0 , and the remaining inventories of FDC 1 and FDC 2 at time t “ 2 are N ´ m1 and N ´ m2 , respectively. For instance I1 , the cost incurred at time t “ 2 is at least b ¨ m2 , and for instance I2 , the cost incurred at time t “ 2 is at least b ¨ m1 . Therefore, we have ALGpI1 q ě b ¨ Erm0 ` m2 s,

ALGpI2 q ě b ¨ Erm0 ` m1 s.

Combining the fact that m0 ` m1 ` m2 “ N , we have b bN 1 pALGpI1 q ` ALGpI2 qq ě ¨ Erm0 ` m1 ` m2 s “ . 2 2 2 The optimal offline policy of both instances is to use FDC 1 and FDC 2 to fulfill the orders solely, and the cost incurred by the optimal offline policy is OPTpI1 q “ OPTpI2 q “ f1 ` f2 ` 2aN . Therefore, we have

* ALGpI1 q ALGpI2 q bN max , ě . OPTpI1 q OPTpI2 q 2pf1 ` f2 ` 2aN q Letting N Ñ 8, we obtain the desired lower bound: "

RpALGq ě

b . 4a

Combining the above two lower bounds, we complete the proof. EC.1.3.

Proof of Proposition 1

For simplicity, we denotebf “ minkPrKs fk as the minimal fixed cost among all FDCs. Note that ! ) f0 f2 f maxně2 min n, f `na “ fa0 ` 4a 2 ´ 2a . Thus we only need to prove "b * pf ´bq2 f0 f ´b b ` 4a2 ´ 2a , a max a ? " ˆb ˙* ď 2p1 ` 5q (EC.2) f0 f2 f b max 4a , 41 ` ´ a 4a2 2a for all f0 ě 0, f ě 0 and b ě a ą 0. 0 Let u “ af and v “ fb . Then we only need to prove b2 "b * pv´1q2 v´1 ? max u` 4 ´ 2 , 1 1` 5 "b * ď 2 v2 v max u ` 4 ´ 2, 1

for all u ě 0, b v ě 0. Note that

2 u ` v4 ´ v2 ě 1 is equivalent to u ě v ` 1, and

u ě v. We consider the following three cases:

(EC.3)

u ` pv´1q ´ v´1 ě 1 is equivalent to 4 2

ec5

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

b b 2 v2 v • If u ě v ` 1, then we have u ` 4 ´ 2 ě 1 and u ` pv´1q ´ v´1 ě 1. Therefore, we have 4 2

max

* 2 u ` pv´1q ´ v´1 , 4 2

b b pv´1q2 v´1 u ` 14 ` 12 1 ` ?5 u` 4 ´ 2 b ? ď . “ ď 2 u 2 u ` v4 ´ v2

"b * v2 v max u ` 4 ´ 2, 1

• If v ď u ă v ` 1, then we have

b b 2 2 v´1 u ` pv´1q ´ ě 1 and u ` v4 ´ v2 ă 1. Therefore, we have 4 2

"b * pv´1q2 v´1 c c ? max u` 4 ´ 2 , 1 pv ´ 1q2 v ´ 1 pv ´ 1q2 v ´ 1 1 ` 5 "b * “ u` ´ ď v`1` ´ ď . 4 2 4 2 2 v2 v max u ` 4 ´ 2, 1 b b 2 2 v´1 • If u ă v, then we have ´ ă 1 and u ` pv´1q u ` v4 ´ v2 ă 1. Therefore, we have 4" 2 "b * * b 2 2 v´1 max u ` pv´1q u ` v4 ´ v2 , 1 “ 1. ´ , 1 { max 4 2

Combining the above three cases, we complete the proof. EC.1.4.

Proof of Claim 2

Fix an item i P rns. Without loss of generality, we assume that ci1 ď ¨ ¨ ¨ ď cik0 ă ci0 ď cik0 `1 ď ¨ ¨ ¨ ď ciK . Note that ˜ K ÿ ÿ tPB

˜ ÿ

cik ¨ m̂ik,t

´ tPB

k“0

« ÿ “

´ci0 ¨

tPB

K ÿ

K ÿ `

cik ¨ mi,˚ k,t

« ÿ “

ci0 ¨

m̂i0,t ´ mi,˚ 0,t

K ÿ

cik ¨

m̂ik,t ´ mi,˚ k,t

tPB k“1 ff K K ÿ ÿ ˘ ` ˘ ` ˘ ÿ` i ˘ m̂ik,t ´ mi,˚ cik ¨ m̂ik,t ´ mi,˚ “ cik ´ ci0 ¨ m̂k,t ´ mi,˚ k,t ` k,t k,t k“0

k“1

tPB

k0 ÿ ` i ˘ ÿ` i ˘ ď ck ´ ci0 ¨ m̂k,t ´ mi,˚ k,t ,

(EC.4)

tPB

k“1

where the inequality is because cik ě ci0 and m̂ik,t “ 0 for all k ą k0 , by the Cost-Comparison V-Priority algorithm. We further have Eq. (EC.4) “

k0 ÿ ` j“1

k0 ÿ j ÿ ˘ ÿ ` i ˘ ` i ˘ ÿ ` i ˘ i cij ´ cij`1 ¨ m̂k,t ´ mi,˚ ` c ´ c ¨ m̂k,t ´ mi,˚ k,t ď 0, k,t k0 0 k“1 tPB

(EC.5)

k“1 tPB

where the inequality is due to that cij ď cij`1 @j P t1, . . . , k0 ´ 1u, cik0 ď ci0 , and that ˘ řj ř ` i i,˚ k“1 tPB m̂k,t ´ mk,t ě 0 holds for all j P t1, . . . , k0 u (which is guaranteed by Lemma 1, as B contains all time periods in which the policy uses at least one FDC to fulfill the order). Combining Eq. (EC.4) and Eq. (EC.5), we prove the claim. EC.1.5.

Proof of Theorem 4

Given the number of FDCs K and fixed costs of FDCs and RDC pf0 , f1 , . . . , fK q. Without loss of generality, we assume f1 “ minkPrKs fk is the minimal fixed cost among all FDCs. For any fixed s, d, n,

ec6

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

we consider the following instance, illustrated in Table EC.1. Each block represents s or d types of i items, so the total number of item types is sn ` Kdn. The initial inventory of FDC 1 is I1,0 “ 1 for i all items i, and the initial inventory of other FDC k (k ě 2) is Ik,0 “ 1 for all items i in the k-th row i of the table, and Ik,0 “ 0 for other items. The variable costs are set to be the same among all items:

ci0 “ c0 , ci1 “ c1 , cik “ c2 for all k “ 2, . . . , K. FDC 1 s s ... s FDC 2 d d . . . .. .. .. . . . . . .

d .. .

FDC K d d . . . d d d ... d 1 2 ... n Table EC.1

Instance for Lower Bound with Time-Invariant Variable Costs (Theorem 4)

Now we consider two instances. For the first instance I1 , the time period is T “ 1, and the customer order requests one unit of each item in the first K row (i.e. except for the last row). For the second instance I2 , the time period is T “ n ` 1. The customer order at time period t “ 1 is the same as instance I1 . At each time period t “ 2, 3, . . . , n ` 1, the customer order requests one unit of each item in the pt ´ 1q-th column of the table. We first analyze the performance of the optimal offline policy in both instances. For instance I1 , the optimal offline policy uses only FDC 1 to fulfill the order, and the cost incurred by the optimal offline policy is OPTpI1 q “ f1 ` rsn ` pK ´ 1qdnsc1 . For instance I2 , we consider the following policy: at time t “ 1, the policy uses RDC to fulfill the items in the first row, and use FDC k (k ě 2) to fulfill the items in the k-th row; at each time period t “ 2, 3, . . . , n ` 1, the policy uses FDC 1 to fulfill the items in the pt ´ 1q-th column. The cost incurred řK by this policy is f0 ` k“2 fk ` snc0 ` dpK ´ 1qnc2 ` rf1 ` ps ` Kdqc1 sn. Thus the cost incurred by the optimal offline policy is no larger than OPTpI2 q ď f0 `

K ÿ

fk ` snc0 ` dpK ´ 1qnc2 ` rf1 ` ps ` Kdqc1 sn.

k“2

By Yao’s principle, the lower bound on the competitive ratio of any randomized online fulfillment policy is lower bounded by that of any deterministic online fulfillment policy under a worst-case distribution over the above two instances, i.e. * " ALGpI2 q ALGpI1 q ` p1 ´ pq ¨ . RpALGq ě max min p¨ pPr0,1s deterministic ALG OPTpI1 q OPTpI2 q

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

ec7

Let ALG be any deterministic online fulfillment policy. We can expect that if ALG uses more FDC k (k ě 2) or RDC at time t “ 1, then it behaves badly on instance I1 ; conversely, if ALG uses more FDC 1, then it behaves badly on instance I2 . To formally illustrate this idea, we consider the following events based on the decision of ALG at time period t “ 1: E1 “ tAt least θns item in the first row are fulfilled by RDC at time t “ 1u , Ek “ tAt least θnd items in the k-th row are fulfilled by RDC or FDC k at time t “ 1u , 2 ď k ď K. Here θ is a parameter to be specified later. Let E “

ŤK

k“1 Ek .

Case 1. Suppose event E occurs. Then, for instance I1 , the incurred cost by ALG is at least ALGpI1 q ě θn ¨ mintsc0 , dc2 u. Therefore, the competitive ratio of ALG is at least ALGpI1 q θn ¨ mintsc0 , dc2 u ě . OPTpI1 q f1 ` rsn ` pK ´ 1qdnsc1 If we further let n Ñ 8, then the competitive ratio of ALG is at least ALGpI1 q θ ¨ mintsc0 , dc2 u ě . nÑ8 OPTpI1 q rs ` pK ´ 1qdsc1 lim

Case 2. Suppose event E does not occur. Then at time t “ 1, at least p1 ´ θqns items in the first row are fulfilled by FDC 1, and at least p1 ´ θqnd items in row k are fulfilled by FDC 1 for each 2 ď k ď K. Thus, for the first row, there are at most θns{p 2s q “ 2θn blocks with at least 2s items left unused in FDC 1; similarly, for each row k “ 2, . . . , K, there are at most θnd{p d2 q “ 2θn blocks with at least d2 items left unused in FDC 1. Let P be the following set of columns: P “ tj P rns : FDC 1 remains at most half of items in k-th block of column j, @ 1 ď k ď K u . Then the number of elements in P can be bounded by |P | ě n ´ K ¨ 2θn “ p1 ´ 2Kθqn.

For each j P P , consider the fulfillment cost at time t “ j ` 1. Since FDC 1 retains at most half of the items in the first block of column j, the remaining items must be fulfilled by the RDC. For 2 ď k ď K, because FDC 1 retains at most half of the items in the k-th block of column j, either the RDC fulfills at least half of these items or FDC k is used. For k “ 1, because the order requests one

ec8

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

unit of each item in the last block of column j, either the RDC fulfills all of these items or FDC 1 is used. Therefore, the fulfillment cost incurred by ALG at time t “ j ` 1 is at least " * " * K K ÿ ÿ 1 1 f0 ` min fk , dc0 ` mintf1 , dc0 u ě f0 ` min fk , dc0 . 2 2 k“2 k“1 Therefore, for instance I2 , the total fulfillment cost by ALG is at least ˜ " *¸ K ÿ 1 , ALGpI2 q ě p1 ´ 2Kθqn ¨ f0 ` min fk , dc0 2 k“1 and the competitive ratio of ALG is at least ´ ␣ (¯ řK p1 ´ 2Kθqn ¨ f0 ` k“1 min fk , 12 dc0

ALGpI2 q . ě ř OPTpI2 q f0 ` K k“2 fk ` snc0 ` dpK ´ 1qnc2 ` rf1 ` ps ` Kdqc1 sn If we further let n Ñ 8, then the competitive ratio of ALG is at least ( ␣ řK f0 ` k“1 min fk , 21 dc0 ALGpI2 q lim ě p1 ´ 2Kθq ¨ . nÑ8 OPTpI2 q sc0 ` dpK ´ 1qc2 ` f1 ` ps ` Kdqc1 Combining the above two cases, since s, d, θ, c0 , c1 , c2 can be chosen arbitrarily, then the lower bound of the competitive ratio of ALG can be written as ´ $ ␣ 1 (¯ , řK & θ ¨ mintsc , dc u p 1 ´ 2Kθ q ¨ f min fk , 2 dc0 . 0` k“1 0 2 , p1 ´ pq ¨ RpALGq ě sup min p ¨ % rs ` pK ´ 1qdsc1 sc0 ` dpK ´ 1qc2 ` f1 ` ps ` Kdqc1 s,d,θ,p c0 ,c1 ,c2 ´ $ ␣ 1 (¯ , řK & θ ¨ mintsc , dc u p 1 ´ 2Kθ q ¨ f min fk , 2 dc0 . 0` k“1 0 2 ě sup lim min p ¨ , p1 ´ pq ¨ % rs ` pK ´ 1qdsc1 sc0 ` dpK ´ 1qc2 ` f1 ` ps ` Kdqc1 s,d,θ,p c1 Ñ0` c0 ,c2 ´ ␣ (¯ řK p1 ´ 2Kθq ¨ f0 ` k“1 min fk , 21 dc0 “ sup p1 ´ pq ¨ sc0 ` dpK ´ 1qc2 ` f1 s,d,θ,p c0 ,c2 ´ ␣ (¯ řK p1 ´ 2Kθq ¨ f0 ` k“1 min fk , 21 dc0 ě sup lim sc0 ` dpK ´ 1qc2 ` f1 s,d,c0 c2 Ñ0` θÑ0` ␣ 1 ( řK f0 ` k“1 min fk , 2 dc0 “ sup sc0 ` f1 s,d,c0 řK f0 ` k“1 fk “ . f1 This completes the proof. EC.1.6.

Proof of Claim 3

For each time period t, we need to prove #

f0 V̄t ď max 1 ` , 1 ` f1

c + b ¨ Vt˚ . a

(EC.6)

ec9

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Furthermore, we need to prove T ÿ

Vt ď

t“1

T ÿ

(EC.7)

V̄t .

t“1

We first prove Eq. (EC.6) for each period t. For time periods t where OPT uses only the RDC to řn fulfill the order, the cost of OPT is Vt˚ “ f0 ` i“1 ci0,t ¨ Sti . If Cost-Comparison AdjV-Priority uses only the RDC as well, then we have the intermediate cost V̄t “ Vt˚ . If Cost-Comparison AdjV-Priority uses at least one FDC, then we know that the gating condition is not triggered, “ ` řn ˘ řn ‰ ř řn i.e., k“0,1 fk ¨ I i“1 mik,t ą 0 ` i“1 cik,t ¨ mik,t ď f0 ` i“1 ci0,t ¨ Sti ; in this case, we have ˜

V̄t “ f0 ` f1 ¨ I

n ÿ

mi1,t ą 0

c `

i“1

˜ ˜ c ¸ n c ¸ n b ÿ i b ÿ i b i i ¨ c ¨ S ď 2f0 ` 1 ` c ¨S ď 1` Vt˚ . a i“1 0,t t a i“1 0,t t a

For time periods t where OPT uses at least one FDC to fulfill the order, we bound the intermediate cost as follows: c

V̄t “ f0 ` f1 `

˜ ¸ # c + n n ÿ ÿ b b f0 i,˚ i,˚ i i ¨ ¨ Vt˚ . c0,t ¨ mk,t ` c1,t ¨ mk,t ď max 1 ` , a f a 1 i“1 i“1

Combining both cases above, we prove the upper bound in Eq. (EC.6). Next, we prove Eq. (EC.7). Let A be the set of time periods that Cost-Comparison AdjVPriority uses at least one FDC to fulfill the order. řn • Case 1. For periods t R A, we have Vt “ f0 ` i“1 ci0,t ¨ Sti . — Case 1a. If OPT uses RDC only, then we further have Vt ď V̄t . — Case 1b. If OPT uses at least one FDC, since the gating condition is triggered, we have « ˜ ¸ ff n n n ÿ ÿ ÿ ÿ i i i i i Vt “ f0 ` c0,t ¨ St ď fk ¨ I m̂k,t ą 0 ` ck,t ¨ m̂k,t i“1

i“1

k“0,1

ď f0 ` f1 `

n ÿ

i“1

cik,t ¨ m̂ik,t “ V̄t `

k“0,1 i“1

n ÿ

cik,t ¨ m̂ik,t ´

k“0,1 i“1

¸ n b ÿ ÿ i i,˚ ¨ c ¨ mk,t . a k“0,1 i“1 k,t (EC.8)

• Case 2. For periods t P A, we have mik,t “ m̂ik,t for all k, i. If OPT uses RDC only, the definition ` řn ˘ b řn ř of V̄t implies that V̄t “ f0 ` f1 ¨ I i“1 mi1,t ą 0 ` ab ¨ i“1 k“0,1 cik,t ¨ mi,˚ k,t , and therefore «

Vt “

ÿ k“0,1

fk ¨ I

n ÿ

i“1

mik,t ą 0 `

n ÿ i“1

cik,t ¨ m̂ik,t ď V̄t `

n ÿ ÿ

k“0,1 i“1

cik,t ¨ m̂ik,t ´

¸ n b ÿ ÿ i ¨ c ¨ mi,˚ . k,t a k“0,1 i“1 k,t (EC.9)

If OPT uses at least one FDC, then we may also verify that have Eq. (EC.9) holds.

ec10

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Summarizing the cases above, let B Ě A be the set of time periods that either Cost-Comparison AdjV-Priority or OPT uses at least one FDC to fulfill the order, and we have that ˜ ¸ c n n ÿ ÿ ÿ b ÿ ÿ i i,˚ i i Vt ď V̄t ` ck,t ¨ m̂k,t ´ ¨ c ¨ mk,t . a k“0,1 i“1 k,t tPB k“0,1 i“1

(EC.10)

On the other hand, the following claim holds. Claim EC.1. For each item i P rns, we have ˜ ¸ c ˜ ¸ ÿ ÿ ÿ ÿ b i,˚ cik,t ¨ m̂ik,t ď ¨ cik,t ¨ mk,t . a tPB tPB k“0,1 k“0,1 The proof of Claim EC.1 follows arguments similar to those used for Claim 1 and is deferred to Section EC.1.7 of the e-companion. A major distinction between the proofs of Claim EC.1 and Claim 1 is that the former requires a modified version of our key technical Lemma 1. Specifically, the original Gated Priority-based Greedy framework and Lemma 1 are formulated only for timeindependent priority rules. To handle the present setting, we establish below a variant of Lemma 1 for the extended Gated Priority-based Greedy framework with time-dependent priority rules in the case K “ 1. This result is stated as Lemma EC.1. Its proof closely parallels that of Lemma 1 and is deferred to Section EC.1.8 of the e-companion. Lemma EC.1. Consider the case K “ 1. Suppose an algorithm satisfies the following conditions: ␣ ( i for any i, k, t, either mi1,t “ max Sti , I1,t´1 “: m̂i1,t , or mi1,t “ 0. Fix an item i. Define Ci “ tt : mi1,t ą 0u as the set of periods in which the actual fulfillment plan uses FDC to fulfill demand for item i. Then for any set B Ě Ci , we have ÿ ÿ i,˚ m̂i1,t ě m1,t . tPB

tPB

Combining Eq. (EC.10) and Claim EC.1, we establish Eq. (EC.7). EC.1.7.

Proof of Claim EC.1 ( ␣ a Fix an item i P rns. Let Ai “ t : ci1,t ă ab ¨ ci0,t . We consider the terms corresponding to t P B zAi b and t P B X Ai , respectively. For t P B zAi , we have ci0,t ď ab ¨ ci1,t , and m̂i0,t “ Sti , m̂i1,t “ 0. Therefore, c ÿ ˘ b ` i i,˚ i,˚ i,˚ i i i i i i i ¨ c0,t ¨ mi,˚ (EC.11) ck,t ¨ m̂k,t “ c0,t ¨ St “ c0,t ¨ mk,t ` c0,t ¨ m1,t ď 0,t ` c1,t ¨ m1,t . a k“0,1 b ? ? a a For t P B X Ai , we have ci1,t ă ab ¨ ci0,t , and thus ci1,t ă ab ¨ ci0,t ď ab and ci0,t ą ab ¨ ci1,t ě ab. Then we have ¯ ÿ ´ ÿ ` ? ˘ ci0,t ¨ m̂i0,t ` ci1,t ¨ m̂i1,t ď b ¨ m̂i0,t ` ab ¨ m̂i1,t , tPBXAi

tPBXA

tPBXAi

i ¯ ÿ ` ÿ ´? ˘ i,˚ i,˚ i,˚ i i c0,t ¨ m0,t ` c1,t ¨ m1,t ě ab ¨ mi,˚ 0,t ` a ¨ m1,t .

ec11

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Therefore, we only need to prove the following inequality: ¯ ¯ ÿ ´ ÿ ´ ? ? i,˚ b ¨ m̂i0,t ` ab ¨ m̂i1,t ď b ¨ mi,˚ ` ab ¨ m 0,t 1,t . tPBXAi

(EC.12)

tPBXAi

Note that ¯ ¯ ÿ ´ ÿ ´ ? ? i,˚ b ¨ m̂i0,t ` ab ¨ m̂i1,t ´ b ¨ mi,˚ ` ab ¨ m 0,t 1,t tPBXAi

“b¨

ÿ `

m̂i0,t ´ mi,˚ 0,t

? `

tPBXAi

ab ¨

tPBXAi

ÿ `

¯ ÿ ` ˘ ´? ˘ m̂i1,t ´ mi,˚ ab ´ b ¨ m̂i1,t ´ mi,˚ 1,t ď 1,t .

tPBXAi

Since B X Ai contains all the periods in which FDC is used to fulfill demand for item i, and B X Ai Ď Ai is contained in the set of periods in which FDC is prioritized over RDC for item i, we can apply ř ř Lemma EC.1 to B X Ai and obtain that tPBXAi m̂i1,t ě tPBXAi mi,˚ 1,t . This proves Eq. (EC.12). Combining Eq. (EC.11) and Eq. (EC.12), we prove the claim.

EC.1.8.

Proof of Lemma EC.1 ␣ř ( ř ř 1,˚ i,˚ i i i i It is clear that mi,˚ 1,t ď St and tPB St , I1,0 . tPB m1,t ď I1,0 , which implies that tPB m1,t ď min Now we only need to prove ÿ

m̂i1,t “

tPB

# + ÿ ␣ i i ( i i min St , I1,t´1 ě min St , I1,0 .

tPB

(EC.13)

tPB

We prove Equation (EC.13) via two steps. ) !ř ř i i S , I Step I. We prove that tPCi m̂i1,t “ min 1,0 . We consider the following two cases: tPCi t ř i . For periods t P Ci , the extended Gated Priority-based Greedy • Suppose tPCi Sti ď I1,0 policy fulfill the order by greedy quantities, so we have m̂i1,t “ mi1,t . Then we have i i I1,t´1 “ I1,0 ´

t´1 ÿ

i mi1,τ “ I1,0 ´

τ “1

m̂i1,τ ,

τ ďt´1 τ PCi

and then i i I1,t´1 “ I1,0 ´

i m̂i1,τ ě I1,0 ´

τ ďt´1 τ PCi

Sτi ě

Sti .

τ ět tPCi

τ ďt´1 τ PCi

␣ ( i Therefore, we have min Sti , I1,t´1 “ Sti for t P Ci , and thus # ÿ

m̂i1,t “

tPCi

• Suppose

ÿ tPCi

␣ ( ÿ i i min Sti , I1,t´1 “ St “ min tPCi

+ ÿ

i Sti , I1,0 .

tPCi

i i i i i tPCi St ą I1,0 . We first prove I1,T “ 0. Assume not, i.e. I1,T ą 0, then I1,t ą 0 for all

t. Then for all t P Ci , the extended Gated Priority-based Greedy fulfillment policy fulfills orders from the FDCs, ␣ ( i i i i “ m̂i1,t “ mi1,t “ I1,t´1 ´ I1,t ă I1,t´1 . min Sti , I1,t´1

ec12

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

i i i i i This implies that for all t P Ci , Sti ă I1,t´1 and I1,t “ I1,t´1 ´ Sti . For t R C, we have I1,t “ I1,t´1 .

Therefore, we have ÿ

i i I1,T “ I1,0 ´

Sti ď 0,

tPCi i i which contradicts the assumption that I1,T ą 0. Thus we have I1,T “ 0, and therefore,

m̂i1,t “

tPCi

␣ ( i i i i min Sti , I1,t´1 “ I1,0 ´ I1,T “ I1,0 .

tPCi

Step II. We prove Equation (EC.13). We consider the following two cases: řj ř i i i • If there exists t P B zCi such that Sti ą I1,t´1 , since Ik,t´1 ě k“1 Ik,T , then we have tPBzCi m̂i1,t “ ␣ i i ( ř i tPBzCi min St , I1,t´1 ě I1,T . Therefore, we have ÿ

m̂i1,t “

tPB

m̂i1,t `

` i ˘ i i i m̂i1,t ě I1,T ` I1,0 ´ I1,T “ I1,0 .

tPCi

tPBzCi

i • If for all t P B zCi , we have Sti ď I1,t´1 , then we can obtain ␣ i i ( ř ř i tPBzCi min St , I1,t´1 “ tPBzCi St . Therefore, we have

# ÿ tPB

m̂i1,t “

m̂i1,t `

m̂i1,t ě

tPCi

tPBzCi

Sti ` min

i Sti , I1,0

i tPBzCi m̂1,t

ě min

“

tPCi

tPBzCi

i Sti , I1,0 .

tPB

This completes the proof of Lemma EC.1.

EC.1.9.

Proof of Theorem 6 ␣ ( řn i Define A “ tt : t“1 St ď θu and Bt “ i : ci1,t ď ci0,t {η , and m̂i1,t “ mintSti , It´1 u. Step I. We construct intermediate values V̄t . Consider the following four cases: Case 1. t R A. Note that Vt ď f0 ` f1 `

ci0,t ¨ Sti `

iRBt

ÿ`

˘ ci0,t ¨ mi0,t ` ci1,t ¨ mi1,t .

iPBt

Define " i * ÿ` ˘ c0,t V̄t “ max a, ¨ Sti ` ηa ¨ mi0,t ` a ¨ mi1,t . η iPBt iRBt řn Since t R A, then we have i“1 Sti ą θ. For i P Bt , we have ci1,t ď ci0,t {η ď b{η. Then we have ÿ

Vt f0 ` f1 ď ` max V̄t V̄t

i i iRBt c0,t ¨ St ␣ ( i, ř i iRBt max a, c0,t {η ¨ St

" * f0 ` f1 b ď ` max η, “: R1 . aθ ηa

` i ˘+ c0,t ¨ mi0,t ` ci1,t ¨ mi1,t ` ˘ ř i i iPBt ηa ¨ m0,t ` a ¨ m1,t

iPBt

(EC.14)

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

ec13

␣ ( For i R Bt , we have ci1,t ě max a, ci0,t {η . For i P Bt , we have ci0,t ě η ¨ ci1,t ě ηa and mi1,t “ m̂i1,t .

Comparing with OPT, we have n ÿ `

" i * ÿ` ˘ c0,t ¨ Sti ´ ηa ¨ mi0,t ` a ¨ mi1,t ´ max a, η i“1 iPBt iRBt * ˙ ÿ ˆ " i ÿ ` ˘ c 0,t i,˚ i,˚ i i i ¨ Sti ` ηa ¨ mi,˚ ě ci0,t ¨ mi,˚ 0,t ` a ¨ m1,t ´ ηa ¨ m0,t ´ a ¨ m1,t 0,t ` c1,t ¨ m1,t ´ max a, η iPBt iRBt ÿ ÿ ` i ˘ ` i ˘ i,˚ pηa ´ aq ¨ m1,t ´ m1,t “ pηa ´ aq ¨ m̂1,t ´ mi,˚ ě (EC.15) 1,t .

Vt˚ ´ V̄t ě

i,˚ i ci0,t ¨ mi,˚ 0,t ` c1,t ¨ m1,t

iPBt

Case 2. t P A, OPT only uses FDC and Order-Size AdjV-Priority uses RDC to fulfill the order at time t. We denote these time periods as A1 . Note that ÿ ÿ` ˘ Vt ď f0 ` f1 ` ci0,t ¨ Sti ` ci0,t ¨ mi0,t ` ci1,t ¨ mi1,t . iPBt

iRBt

Define V̄t “

ÿ` ˘ ÿ` ˘ ηa ¨ m̂i0,t ` ci1,t ¨ m̂i1,t ` ηa ¨ mi0,t ` a ¨ mi1,t . iPBt

iRBt

Since Order-Size AdjV-Priority uses RDC to fulfill the order at time t, we have m̂i0,t ą 0 for some i. For i R Bt , we have ci0,t ď η ¨ ci1,t . For i P Bt , we have ci1,t ď ci0,t {η ď b{η. Then we have # ` i ˘+ ř ř i i i i i Vt f0 ` f1 iRBt c0,t ¨ St iPBt c0,t ¨ m0,t ` c1,t ¨ m1,t ` ` ˘ ˘, ř ď ` max ř i i i i i V̄t V̄t iRBt ηa ¨ m̂0,t ` c1,t ¨ m̂1,t iPBt ηa ¨ m0,t ` a ¨ m1,t * " f0 ` f1 b “: R2 . (EC.16) ď ` max η, ηa ηa řn i i i Since OPT only uses FDC, then Vt˚ “ f1 ` i“1 ci1,t ¨ Sti , mi,˚ 1,t “ St . For i P Bt , we have m1,t “ m̂1,t . Comparing with OPT, we have Vt˚ ´ V̄t ě

n ÿ

ÿ`

ci1,t ¨ Sti ´

i“1

˘ ÿ` ˘ ηa ¨ m̂i0,t ` ci1,t ¨ m̂i1,t ´ ηa ¨ mi0,t ` a ¨ mi1,t iPB

iRB

t t ÿ` ˘ ÿ` ˘ i i i i i ě c1,t ¨ St ´ ηa ¨ m̂0,t ´ c1,t ¨ m̂1,t ` a ¨ Sti ´ ηa ¨ mi0,t ´ a ¨ mi1,t

iPBt

iRBt

pηa ´ aq ¨

ě iRBt n ÿ

m̂i1,t ´ Sti

ÿ `

` ˘ pηa ´ aq ¨ mi1,t ´ mi,˚ 1,t

iPBt

` ˘ pηa ´ aq ¨ m̂i1,t ´ mi,˚ 1,t .

“

(EC.17)

i“1

Case 3. t P A, both OPT and Order-Size AdjV-Priority only use FDC to fulfill the order at time t. We denote these time periods as A2 . Then we have Vt “ Vt˚ and mi1,t “ m̂i1,t “ mi,˚ 1,t for all i. Define V̄t “ Vt . Case 4. t P A and OPT uses RDC to fulfill the order at time t. We denote these time periods as A3 . Define

n ÿ 1 V̄t “ f0 ` a ¨ Sti . 2 i“1

ec14

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Since t P A, we have

řn

i i“1 St ď θ. Then we have

řn Vt f0 ` f1 ` i“1 ci0,t ¨ Sti f0 ` f1 ` bθ řn ď “: R4 . (EC.18) ď f0 {2 ` a ¨ i“1 Sti f0 {2 ` aθ V̄t ‰ ˘ řn “` i,˚ i Since OPT uses RDC and t P A, then we have Vt˚ ě f0 {2 ` i“1 ci0,t ` f0 {p2θq ¨ mi,˚ 0,t ` c1,t ¨ m1,t .

Comparing with OPT, we have Vt˚ ´ V̄t ě

n „ˆ ÿ

f0 ci0,t `

2θ

i“1 n ˆ ÿ

ȷ i,˚ i i ¨ mi,˚ 0,t ` c1,t ¨ m1,t ´ a ¨ St

f0 ´a ci0,t `

2θ

i“1

(EC.19)

` ˘ ¨ St ´ mi,˚ 1,t .

If we choose θ, η such that f0 {p2θq ě ηa, then we have Vt˚ ´ V̄t ě

Step II. We prove

řT

n ÿ

n ` ˘ ÿ ` ˘ pηa ´ aq ¨ St ´ mi,˚ pηa ´ aq ¨ m̂i1,t ´ mi,˚ ě 1,t . 1,t

i“1

˚ t“1 Vt ě

(EC.20)

řT

t“1 V̄t . For item i, define

Ti “ tt : pt R A ^ i P Bt q _ pt P Aqu Combining Eqs. (EC.15), (EC.17), (EC.20), we have T ÿ

pVt˚ ´ V̄t q ě

t“1

ÿÿ

pηa ´ aq ¨ pm̂i1,t ´ mi,˚ 1,t q `

n ÿ

pηa ´ aq ¨ pm̂i1,t ´ mi,˚ 1,t q

tPA1 YA3 i“1

tRA iPBt

“ pηa ´ aq ¨

n ÿ ÿ

pm̂i1,t ´ mi,˚ 1,t q.

i“1 tPTi

Since Ti contains the set of periods that Order-Size AdjV-Priority uses FDC to fulfill the order, by Lemma EC.1,we have ÿ

m̂i1,t ě

tPTi

Therefore, we conclude that

řT

˚ t“1 Vt ě

mi,˚ 1,t .

tPTi

řT

t“1 V̄t .

Step III. Now we analysis the competitive ratio. By definition, we have řT Vt Vt t“1 Vt RpOrder-Size AdjV-Priorityq “ sup řT ď sup řTt“1 ď sup max . ˚ tPrT s V̄t I I I t“1 Vt t“1 V̄t řT

Combining with the bounds in Eqs. (EC.14), (EC.16), (EC.18), we have RpOrder-Size AdjV-Priorityq ď maxtR1 , R2 , R4 u " " * " * * b f0 ` f1 b f0 ` f1 ` bθ f0 ` f1 ` max η, , ` max η, , , “ max aθ ηa ηa ηa f0 {2 ` aθ

(EC.21)

ec15

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

with the constraint that f0 {p2θq ě ηa. Now we choose c

η“

max tf0 {2, bu , a

f0 θ“ “ 2aη

" * f0 f0 min 1, . a 2b

Note that we assume f0 ě f1 . Then we have " " * * f0 ` f1 b b 2f0 R1 “ ` max η, ` max η, ď “ 5η, aθ ηa aθ ηa " " * * b b 2f0 f0 ` f1 ` max η, ` max η, ď ď 5η, R2 “ ηa ηa ηa ηa c 2b f0 ` f1 ` bθ 2f0 2bθ ď ` . R4 “ ď 4η ` f0 {2 ` aθ aθ f0 a

Therefore, we have RpOrder-Size AdjV-Priorityq ď maxtR1 , R2 , R4 u # c c c c + ? max tf0 {2, bu max tf0 {2, bu 2b max tf0 {2, bu ď max 5 , 4 ` ď p4 ` 2q . a a a a This completes the proof. EC.1.10.

Proof of Corollary 1

The first inequality in the corollary is straightforward. We only prove the second inequality. When f0 ă f1 , we have #

RpBetter-of-Twoq ď 1 ` max

f0 , f1

c + c b b ď1` . a a

(EC.22)

When f0 ě f1 , we have #

#c c + c ++ ? b f0 b , p4 ` 2q max , RpBetter-of-Twoq ď min 1 ` max a 2a a # # #c c + c ++ ? ? f0 b f0 b ď min max 2 ¨ , p4 ` 2q , p4 ` 2q max , f1 a 2a a # # c + c + ? ? f0 f0 b “ max min 2 ¨ , p4 ` 2q , p4 ` 2q . (EC.23) f1 2a a

f0 , f1

Note that, by Eq. (EC.22), the competitive ratio in the case f0 ă f1 also satisfies the upper bound in Eq. (EC.23). Therefore, Eq. (EC.23) serves as a global upper bound of the competitive ratio of the algorithm, and we prove the second inequality in the corollary.

ec16

EC.1.11.

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Proof of Theorem 7

In the proof of Theorem 2, the following lower bound does not require the number of FDCs K to be at least 2:

" " ** f0 1 RpALGq ě max 1, max min n, . 4 ně2 f1 ` na b So we only need to prove RpALGq ě 31 ab . We also construct two instances to prove the lower bound.

In both instances, there is only one type of items n “ 1, and the initial inventories of FDC 1 is N , where N is a large integer that can be chosen arbitrarily. For the first instance I1 , the time period is set to be T “ 1. At time period t “ 1, the customer order requests N units of the item, and ? the variable costs are c10,1 “ ab, c11,1 “ a. For the second instance I2 , the time period is set to be T “ 2. At time period t “ 1, the customer order and the variable costs are the same as instance I1 . At time period t “ 2, the customer order requests N units of the item, and the variable costs are c10,2 “ b, c11,2 “ a. Let m0 , m1 be the number of items fulfilled from RDC and FDC 1 at time period t “ 1 by ALG, respectively. Here m0 , m1 may be random variables. Then the cost incurred at time t “ 1 is at least ? ab ¨ m0 ` a ¨ m1 . For instance I2 , the remaining inventory of FDC 1 at time t “ 2 is N ´ m1 , and the cost incurred at time t “ 2 is at least b ¨ m1 . Therefore, we have ALGpI1 q ě

ab ¨ Erm0 s,

ALGpI2 q ě b ¨ Erm1 s “ b ¨ pN ´ Erm0 sq.

For instance I1 , the cost of the optimal offline policy is OPTpI1 q “ f1 ` aN . For instance I2 , the optimal offline policy is to use RDC to fulfill the order at time t “ 1 and use FDC 1 to fulfill the order ? at time t “ 2, and the cost incurred by the optimal offline policy is OPTpI2 q ď f0 ` f1 ` abN ` aN . Therefore, we have * ALGpI1 q ALGpI2 q RpALGq ě sup max , OPTpI1 q OPTpI2 q N #? + ab ¨ Erm0 s b ¨ pN ´ Erm0 sq ? , “ sup max f1 ` aN N f0 ` f1 ` abN ` aN #? + ab ¨ x b ¨ pN ´ xq ? ě sup min max , f1 ` aN f0 ` f1 ` 2 abN N 0ďxďN c ? ab ¨ bN 1 b “ sup ? . ě N abpf0 ` f1 q ` bf1 ` 3abN 3 a "

We complete the proof of the lower bound. EC.1.12.

Proof of Proposition 2

We first prove that for any t P p0, 1q, we have # c + " * f0 f0 f 0 max min n, ě min t ¨ , p1 ´ t2 q ¨ . n f1 ` na a f1

(EC.24)

ec17

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

) b ! f2 f1 f0 , so we only need to prove Note that maxn min n, f1 `na “ fa0 ` 4a12 ´ 2a c

Let r “ ff01 ¨

# c + f0 f12 f1 f0 f0 2 ` 2´ ě min t ¨ , p1 ´ t q ¨ . a 4a 2a a f1

(EC.25)

a . Then Eq. (EC.25) is equivalent to f0

" * r2 r 1 ´ t2 1 ` ´ ě min t, . 4 2 r

If t ď p1 ´ t2 q{r, i.e. r ď p1 ´ t2 q{t, then we have c c r2 r p1 ´ t2 q2 1 ´ t2 1` ´ ě 1` ´ “ t. 4 2 4t2 2t If t ą p1 ´ t2 q{r, i.e. r ą p1 ´ t2 q{t, then we have c r 2 r 1 ´ t2 1` ´ ě 4 2 r

ðñ

r2 ě

p1 ´ t2 q2 . t2

Combining the above two cases, we prove Eq. (EC.24). Now we compare the upper and lower bounds. Combining Eq. (EC.24) with the lower bound in Theorem 7, we have #

1 RpALGq ě max 1, 3

# c ++ b 1 f0 f 0 , min t ¨ , p1 ´ t2 q ¨ . a 4 a f1

Therefore, the ratio between the upper and lower bounds is at most b ) ! ! ? ? bb) ? f0 f0 " * max min 2 ¨ f1 , p2 2 ` 1q a , p4 ` 2q a ? 8 2`4 8 b ! ! b )) ď max 3p4 ` 2q, . , t 1 ´ t2 max 1, 13 ab , 14 min t ¨ fa0 , p1 ´ t2 q ¨ ff01 a ? ? We choose t “ p 10 ` 4 2 ´ 1q{p2 2 ` 1q « 0.772. Then we have ? ? " * ? 4 ¨ p9 ` 4 2q 8 2`4 8 max 3p4 ` 2q, ďa ď 19.828. , ? t 1 ´ t2 10 ` 4 2 ´ 1

We complete the proof of the proposition. EC.1.13.

Proof of Claim 4

The first inequality in Eq. (20). By the definition of Randomized-Cost-Comparison VPriority, if θt “ 1, then the algorithm uses only the RDC. For i P I, we have ci1 ă ci0 . Thus we have V̄t ´ Vt “ f0 `

ÿ iPI

ÿ “ iPI

˘` i

pci1 ´ ci0 q ¨ mi,˚ 1,t ´ m̂1,t `

pci1 ´ ci0 q ¨

n ÿ

ci0 ¨ Sti ´ f0 `

n ÿ

ci0 ¨ Sti

i“1 i“1 ˘` ÿ i ` i,˚ ˘ i,˚ i i i m1,t ´ m̂1,t ď pc1 ´ c0 q ¨ m1,t ´ m̂1,t . iPI

(EC.26)

ec18

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

If θt “ 0, then the algorithm uses the greedy allocation, and mi1,t “ 0 for i R I. we have ˜ ¸ n n n ÿ ÿ ÿ ÿ ÿ ` ˘ i i i i i i i V̄t ´ Vt “ pci1 ´ ci0 q ¨ mi,˚ ` c ¨ S ´ c ¨ m ` c ¨ m “ pci1 ´ ci0 q ¨ mi,˚ 1,t 1,t ´ m1,t . 0 t 0 0,t 1 1,t i“1

iPI

i“1

iPI

(EC.27)

Combining Eqs. (EC.26) and (EC.27), we have T ÿ

pV̄t ´ Vt q “

t“1

By Lemma 1, we have

pci1 ´ ci0 q ¨

T ÿ

(EC.28)

i pmi,˚ 1,t ´ m̂1,t q.

t“1

iPI

řT

i,˚ i t“1 pm1,t ´ m̂1,t q ď 0 for all i P I. Combining with Eq. (EC.28), we establish

the first inequality in Eq. (20). The second inequality in Eq. (20). We first give an upper bound of ErV̄t |Ft´1 s for any t P rT s. Let řn ř qt “ i“1 pci0 ´ ci1 q ¨ m̂i1,t “ iPI pci0 ´ ci1 q ¨ m̂i1,t . We consider the following two cases. řn ˚ • Case 1. If i“1 mi,˚ 1,t “ 0, then cost of optimal fulfillment policy at time period t is Vt “ f0 ` řn i i i“1 c0 ¨ St . By the definition of V̄t , we have řn ErV̄t |Ft´1 s ppqt q ¨ f0 ` p1 ´ ppqt qq ¨ pf0 ` f1 q ` i“1 ci0 ¨ Sti f0 ` p1 ´ ppqt qq ¨ f1 ` qt řn ď ď . Vt˚ f0 ` i“1 ci0 ¨ Sti f0 ` qt (EC.29) řn i,˚ • Case 2. If i“1 m1,t ą 0, then the value of the optimal policy is at least Vt˚ ě f1 `

n ÿ ` i ˘ i,˚ i c0 ¨ mi,˚ 0,t ` c1 ¨ m1,t . i“1

We consider the value of θt . — Case 2a. If θt “ 1, then by the definition of V̄t , we have n ÿ ` ˘ ÿ i V̄t ď f0 ` pci1 ´ ci0 q ¨ mi,˚ ´ m̂ ` ci0 ¨ Sti 1,t 1,t i“1

iPI

“ f0 `

pci1 ´ ci0 q ¨

i mi,˚ 1,t ´ m̂1,t

ÿ `

iPI

ď f0 `

i,˚ ci0 ¨ pmi,˚ 0,t ` m1,t q `

iPI

n ÿ `

i,˚ ci0 ¨ pmi,˚ 0,t ` m1,t q

iRI

˘ i,˚ i ci0 ¨ mi,˚ 0,t ` c1 ¨ m1,t ` qt .

i“1

Here the first inequality holds since ci1 ă ci0 for all i P I; the second inequality holds since ci1 ě ci0 for all i R I. Thus we have ˘ řn ` " * i,˚ i f0 ` i“1 ci0 ¨ mi,˚ f0 ` qt V̄t 0,t ` c1 ¨ m1,t ` qt ˘ ď max ď ,1 . řn ` i,˚ i Vt˚ f1 f1 ` i“1 ci0 ¨ mi,˚ 0,t ` c1 ¨ m1,t

(EC.30)

— Case 2b. If θt “ 0, then by the definition of V̄t , we have ˜ ¸ ˜ ¸ n n n ÿ ÿ ÿ ÿ i,˚ i i i i V̄t “ f0 ¨ I m0,t ą 0 ` f1 ¨ I m1,t ą 0 ` pc1 ´ c0 q ¨ m1,t ` ci0 ¨ Sti i“1

ď f0 ` f1 `

i“1

ÿ iPI

pci1 ´ ci0 q ¨ mi,˚ 1,t `

n ÿ i“1

i“1

iPI

n ÿ ` i ˘ i,˚ i ci0 ¨ Sti ď f0 ` f1 ` c0 ¨ mi,˚ 0,t ` c1 ¨ m1,t . i“1

ec19

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Thus we have ˘ řn ` i,˚ i f0 ` f1 ` i“1 ci0 ¨ mi,˚ V̄t f ` f1 0,t ` c1 ¨ m1,t ˘ ď 0 ď . řn ` i i,˚ i,˚ i Vt˚ f1 f1 ` i“1 c0 ¨ m0,t ` c1 ¨ m1,t

(EC.31)

Combining Eq. (EC.29), Eq. (EC.30) and Eq. (EC.31), we have " * ErV̄t |Ft´1 s f0 ` f1 f0 ` qt f0 ` f1 f0 ` p1 ´ ppqt qq ¨ f1 ` qt ď max , ppqt q ¨ ` p1 ´ ppqt qq ¨ , . Vt˚ f1 f1 f1 f0 ` qt

Now we define w“

qt f0 , r“ . f1 f1

Then we have * " ErV̄t |Ft´1 s 1 1 . ď max 1 ` w, 1 ` w ` p p q q ¨ p r ´ 1 q , 1 ` ´ p p q q ¨ t t Vt˚ w`r w`r

We consider the following three cases based on the definition of the probability function pp¨q: • If r ď 1, i.e. qt ď f1 , we have ppqt q “ 1. Then we have ErV̄t |Ft´1 s ď 1 ` w. Vt˚

(EC.32)

) ! ␣ ( f2 • If r ą max 1, w1 ´ w , i.e. qt ą max f1 , f10 ´ f0 , we have ppqt q “ 0. Then we have " * ErV̄t |Ft´1 s 1 ď max 1 ` w, 1 ` ď 1 ` w. Vt˚ w`r

(EC.33)

• If 1 ă r ď w1 ´ w, i.e. f1 ă qt ď f10 ´ f0 , we have ppqt q “

1 ´w f12 ´ pf0 ` qt qf0 w`r “ . 1 ` r ´ 1 f12 ` pf0 ` qt qpqt ´ f1 q w`r

Then we have ErV̄t |Ft´1 s w`r´1 1 ? ď1` ď1` . ˚ 2 Vt 1 ` wr ` r ´ w ´ r 1´w`2 1´w

(EC.34)

Combining Eq. (EC.32), Eq. (EC.33) and Eq. (EC.34), we have # ? 1 ` 1´w`21?1´w , if w ă 5´1 ErV̄t |Ft´1 s ?2 ď , Vt˚ 1 ` w, if w ě 5´1 2

This proves the claim.

@ t P rT s. ˝

ec20

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

EC.1.14.

Proof of Theorem 9

Note that the proof of Theorem 4 also holds when there is only one FDC. So we only need to prove 1 that Rinv pALGq ě 54 . Without loss of generality, we assume 54 ě f0f`f , i.e. f1 ě 4f0 . 1

Given the fixed costs of FDC and RDC pf0 , f1 q, we consider the following two instances. In both instances, there is only one type of items n “ 1. The initial inventory of FDC is M N , and the variable costs are set to be c10 “ ϵ, c11 “ 0, where M , N and ϵ are determined later. For the first instance I1 , the time period is set to be T “ 1. At time period t “ 1, the customer order requests N units of the item. For the second instance I2 , the time period is set to be T “ 2. At time period t “ 1, the customer order is the same as instance I1 , and at time period t “ 2, the customer order requests M N units of the item. By Yao’s principle, the lower bound on the competitive ratio of any randomized online fulfillment policy is lower bounded by that of any deterministic online fulfillment policy under a worst-case distribution over the above two instances, i.e. * " ALGpI2 q ALGpI1 q ` p1 ´ pq ¨ . Rinv pALGq ě max min p¨ pPr0,1s deterministic ALG OPTpI1 q OPTpI2 q

Let ALG be any deterministic online fulfillment policy. We consider the following two cases based on ALG’s decision at time period t “ 1. Case 1. Suppose that at time period t “ 1, ALG uses only the RDC to fulfill the order. For instance I1 , the optimal policy is to use the FDC to fulfill the order, and the cost incurred by the optimal offline policy is OPTpI1 q “ f1 . Since ALG uses only the RDC to fulfill the order, its incurred cost is at least ALGpI1 q ě f0 ` N ϵ. Then we have ALGpI1 q f0 ` N ϵ ALGpI1 q ALGpI2 q f0 ` N ϵ ě , and p ¨ ` p1 ´ pq ¨ ěp¨ ` p1 ´ pq. OPTpI1 q f1 OPTpI1 q OPTpI2 q f1 Case 2. Suppose at time period t “ 1, FDC is used by ALG to fulfill the order. For instance I2 , the optimal fulfillment policy is to use RDC solely to fulfill the order at time t “ 1 and use FDC solely to fulfill the order at time t “ 2, and the cost incurred by the optimal offline policy is OPTpI2 q “ f0 ` f1 ` N ϵ. Since FDC is used by ALG to fulfill the order at time t “ 1, the remaining inventory of FDC at time t “ 2 is strictly less than M N , so RDC must be used to fulfill part of the order at time t “ 2. If ALG uses only the RDC to fulfill the order at time t “ 2, then the cost incurred by ALG is at least ALGpI2 q ě f0 ` f1 ` M N ϵ. Otherwise, ALG uses both the RDC and the FDC to fulfill the order at time t “ 2, in which case the cost is at least ALGpI2 q ě f1 ` pf0 ` f1 ` N ϵq “ f0 ` 2f1 ` N ϵ. Thus, we have ALGpI2 q ě mintf0 ` f1 ` M N ϵ, f0 ` 2f1 ` N ϵu. Therefore, we have ALGpI2 q mintf0 ` f1 ` M N ϵ, f0 ` 2f1 ` N ϵu ě , OPTpI2 q f0 ` f1 ` N ϵ

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

ec21

and p¨

ALGpI1 q ALGpI2 q mintf0 ` f1 ` M N ϵ, f0 ` 2f1 ` N ϵu ` p1 ´ pq ¨ ě p ` p1 ´ pq ¨ . OPTpI1 q OPTpI2 q f0 ` f1 ` N ϵ

If we choose M such that f0 ` f1 ` M N ϵ ě f0 ` 2f1 ` N ϵ, i.e. M ě 1 ` Nf1ϵ , then we have ALGpI1 q ALGpI2 q f0 ` 2f1 ` N ϵ ALGpI2 q f0 ` 2f1 ` N ϵ ě , and p ¨ ` p1 ´ pq ¨ ě p ` p1 ´ pq ¨ . OPTpI2 q f0 ` f1 ` N ϵ OPTpI1 q OPTpI2 q f0 ` f1 ` N ϵ ϵ Combining the above two cases, let λ “ f0 `N , we have f1

" * ALGpI2 q ALGpI1 q max min ` p1 ´ pq ¨ p¨ pPr0,1s deterministic ALG OPTpI1 q OPTpI2 q " * f0 ` N ϵ f0 ` 2f1 ` N ϵ ě max min p ¨ ` p1 ´ pq, p ` p1 ´ pq ¨ pPr0,1s f1 f0 ` f1 ` N ϵ * " λ`2 “ max min pλ ` p1 ´ pq, p ` p1 ´ pq ¨ p λ`1 " * 1 1 “ max min 1 ` pλ ´ 1qp, 1 ` ´ p pPr0,1s λ`1 λ`1 # 1 ` λ1 ´ λ12 , λ ě 1 . “ 1, λă1

Since f1 ě 4f0 , we can choose N and ϵ such that λ “ 2, i.e., N ϵ “ 2f1 ´ f0 . Then we have Rinv pALGq ě 1 `

1 1 5 ´ “ . 2 4 4

This completes the proof.

EC.2.

Details of Numerical Experiments

This section complements the theoretical results with numerical experiments. Section EC.2.1 describes the experimental design. Section EC.2.2 presents results for the time-varying variable cost setting. Section EC.2.3 presents results for the time-invariant variable cost setting and includes comparisons with forecast-based LP policies. Finally, Section EC.2.4 reports a set of stress-test instances showing that, under certain time-varying demand patterns, the proposed policy can substantially outperform the myopic baseline. Furthermore, section EC.2.5 describes the baseline algorithms, including the myopic policy and the LP-based policies. EC.2.1.

Experiment Settings

Unless otherwise specified, the numerical experiments use the following baseline parameter setting. Basic Network Setting. We set the number of items to n “ 50, the number of FDCs to K “ 10, and the baseline time horizon to T “ 2000.

ec22

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Cost Structure. The fixed cost of each FDC is fk “ 5 for all k “ 1, . . . , K, and the fixed cost of the RDC is f0 “ 50. The lower and upper bounds of the variable costs are a “ 8 and b “ 30. In the timevarying setting, for each period t, item i, and DC k, the variable cost cik,t is independently drawn from the uniform distribution on ra, bs. In the time-invariant setting, we first independently draw cik from the uniform distribution on ra, bs for each item i and DC k, and then set cik,t “ cik for all periods t. Order Distribution. We specify the order distribution by the order size, the number of order types for each size, and the arrival probability of each order size. The possible order sizes are 1, 2, 3, 10, 15, 20. The corresponding numbers of order types are 50, 50, 30, 20, 20, 10, and the corresponding arrival probabilities are 0.4, 0.2, 0.1, 0.1, 0.1, 0.1. Conditional on an order size, all order types of that size are equally likely. For comparability with the baseline algorithms, we follow the standard binary-demand convention in these experiments: each item quantity in an order is either 0 or 1. At each period t, the customer order St is independently drawn from this distribution. i Inventory Level. The initial inventory of item i at FDC k is Ik,0 “ τ ¨ pi T {K, where pi T denotes

the expected demand for item i over the selling horizon and τ controls the inventory scale. We set τ “ 0.2, so FDC inventory is scarce relative to expected demand, while the RDC remains an unlimited backup. This setting is stylized, but it is chosen to reflect several practical features of online fulfillment. The fixed cost of RDC is higher than that of FDCs, reflecting the high activation costs of the central distribution center. The order distribution is dominated by small orders, while still allowing occasional larger multi-item orders, consistent with the fact that most e-commerce orders are small but large orders do occur. Finally, the FDC inventory level is deliberately limited, which makes the intertemporal value of local inventory nontrivial. Thus, the experiments evaluate the policies in a regime where real-time decisions must balance current fulfillment cost against future inventory availability. In all experiments, we report average fulfillment costs and running time over 100 independent replications. When LP-based policies are included, they are given the true demand distribution used to generate orders, and the time of solving LP is also contained in the reported running time. EC.2.2.

Time-varying Variable Costs

We first study the setting with time-varying variable costs. We compare Order-Size F-Priority with the generalized myopic policy in Algorithm 8 for multi-FDC networks, and we also report a single-FDC experiment for the corresponding refined policy.

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

ec23

For the multi-FDC case, we first vary the time horizon. Specifically, we set T “ 200 ¨ i for i “ 1, 2, . . . , 10, while keeping the remaining parameters at their baseline values. Figure EC.1 reports the average total fulfillment costs and total running times. The results show that Order-Size FPriority achieves fulfillment costs that are comparable to, and in several cases lower than, those of the myopic policy. At the same time, its running time is much smaller. This confirms that the proposed policy can preserve the cost performance of a more expensive myopic benchmark while providing a substantial computational advantage.

Figure EC.1

The cost and the total running time of Order-Size F-Priority and the myopic policy as the time horizon T increases.

We next vary the number of FDCs by setting K “ 2i ` 1 for i “ 1, 2, . . . , 7. Figure EC.2 shows that the running time of the myopic policy grows exponentially as K increases, consistent with the NP-hardness result in Proposition EC.1. In contrast, the running time of Order-Size F-Priority remains nearly flat as the network expands. Importantly, this computational gain does not come at a large cost penalty: Order-Size F-Priority continues to deliver cost performance close to, and sometimes better than, that of the myopic policy.

Figure EC.2

The cost and the total running time of Order-Size F-Priority and the myopic policy as the number of FDCs K increases.

ec24

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

We also consider the single-FDC setting. We compare Order-Size AdjV-Priority with the myopic policy as T increases, again using T “ 200 ¨ i for i “ 1, 2, . . . , 10. Figure EC.3 shows that Order-Size AdjV-Priority achieves costs comparable to, and often lower than, those of the myopic policy. This suggests that the benefit of the proposed Gated Priority-based Greedy framework is not limited to large networks; it also helps in the single-FDC setting by moderating the use of scarce local inventory.

Figure EC.3

The cost of Order-Size AdjV-Priority and the myopic policy as the time horizon T increases.

Overall, the time-varying experiments show the main superiority of our approach: the proposed algorithms are substantially more computationally efficient, while their fulfillment costs remain close to or even lower than those of the myopic benchmark. EC.2.3.

Time-invariant Variable Costs

We next study the time-invariant variable cost setting. This setting is the standard benchmark in much of the online fulfillment literature and allows comparison with both myopic and LP-based forecast-driven policies. We compare Cost-Comparison V-Priority, the generalized myopic policy in Algorithm 8, and four LP-based policies with perfect demand forecasts: IPFC and DPFC from Jasin and Sinha (2015), and Dilate and ForceOpen from Ma (2023) as specified in Section EC.2.5. We first vary the time horizon by setting T “ 200 ¨ i for i “ 1, 2, . . . , 10. Figure EC.4 reports the results. Cost-Comparison V-Priority achieves cost performance comparable to the myopic policy and the LP-based policies, even though the LP-based policies are supplied with the true demand distribution. At the same time, Cost-Comparison V-Priority is much faster, highlighting the value of a simple online rule when real-time implementation is important. We then vary the number of FDCs by setting K “ 2i ` 1 for i “ 1, 2, . . . , 7. Figure EC.5 shows a clear scalability pattern. The myopic policy becomes increasingly slow as K grows, again reflecting the combinatorial nature of per-order cost minimization. The LP-based policies also become

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Figure EC.4

ec25

The cost and the total running time of Cost-Comparison V-Priority, the myopic policy, and LP-based policies as the time horizon T increases.

slower as the number of FDCs increases because the underlying linear programs contain more decision variables. By contrast, the running time of Cost-Comparison V-Priority remains nearly unchanged. Its fulfillment cost remains close to those of the benchmark policies, demonstrating that the computational advantage is achieved without sacrificing much cost performance.

Figure EC.5

The cost and the total running time of Cost-Comparison V-Priority, the myopic policy, and LP-based policies as the number of FDCs K increases.

Finally, we examine the single-FDC setting. We compare Randomized-Cost-Comparison VPriority, the myopic policy, and the same LP-based forecast benchmarks as T increases. Figure EC.6 shows that Randomized-Cost-Comparison V-Priority also achieves cost performance comparable to the benchmark policies. Together with the multi-FDC results, this indicates that the proposed policies perform well not only in the adversarial worst-case analysis but also in stochastic simulations with time-invariant cost structures. EC.2.4.

Stress Test under Extreme Cases

The preceding experiments use stochastic instances intended to be practically motivated. We now complement them with an adversarially stressful family of instances within the time-varying framework. These instances are not intended to represent typical daily operations; instead, they isolate a

ec26

Figure EC.6

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

The cost and the total running time of Randomized-Cost-Comparison V-Priority, the myopic policy, and LP-based policies as the time horizon T increases.

failure mode of myopic fulfillment: using scarce FDC inventory for a large early order can be costly when many smaller future orders would have benefited more from FDCs. Suppose there is one FDC and one RDC. The fixed cost of the FDC is 0, and the fixed cost of the RDC is f0 ą 0. We set a “ b “ 1, so all variable costs are identical and equal to 1; this removes variable ? cost heterogeneity and isolates the inventory-depletion effect. The number of items is n “ r f0 s, and the horizon is T “ n ` 1. In the first period, the order is S1 “ p1, 1, . . . , 1q, requesting one unit of every item. In each subsequent period t “ 2, . . . , n ` 1, the order requests one unit of item t ´ 1. The initial inventory of each item at the FDC is one unit. This construction creates a sharp intertemporal trade-off. Serving the first large order from the FDC is attractive from a one-period perspective, but doing so exhausts all local inventory and forces the later single-item orders to use the RDC repeatedly. A policy that protects FDC inventory can avoid this repeated fixed-cost burden. We compare Order-Size F-Priority with the myopic policy as f0 varies from 50 to 500. Figure EC.7 shows that Order-Size F-Priority achieves a substantial cost advantage over the myopic policy. The widening gap as f0 grows illustrates the stability benefit of the gating mechanism: the proposed policy is less vulnerable to temporal demand patterns that induce premature depletion of scarce FDC inventory. Taken together, the experiments support the main empirical message of the paper. In practically motivated stochastic settings, the proposed policies are much more computationally efficient than the myopic and LP-based benchmarks while maintaining similar fulfillment costs. In more adversarial time-varying settings, the same gating idea can also yield markedly better cost performance than myopic fulfillment, demonstrating greater stability under challenging demand sequences. EC.2.5.

Baseline Algorithms

Myopic Policy. Zhao et al. (2025) study the two-layer multi-item online order fulfillment problem with a single FDC and variable costs that are independent of both item and time, i.e. cik,t ” ck , @i, t. They

ec27

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Figure EC.7

The cost of Order-Size F-Priority and the myopic policy in the extreme case with time-varying variable costs.

propose a myopic policy that minimizes the fulfillment cost of each incoming order independently, without accounting for future costs, which is described in Algorithm 7. Algorithm 7 Myopic Policy in Zhao et al. (2025) for each time period t “ 1, 2, . . . , T do Observe customer order St ; Solve the following optimization problem to determine the fulfillment quantities: ˜ ¸ ˜ ¸ n n n n ÿ ÿ ÿ ÿ i i i i tmk,t uk,i “ arg min f0 ¨ I m0,t ą 0 ` c0 ¨ m0,t ` f1 ¨ I m1,t ą 0 ` c1 ¨ mi1,t ; tmik,t uk,i

i“1

Fulfill the order according to the optimal fulfillment quantities tmik,t uk,i ; i i Update inventory levels: I1,t Ð I1,t´1 ´ mi1,t for all i P rns.

For the setting with multiple FDC and item-specific, time-varying variable costs, the myopic policy in Zhao et al. (2025) can be directly extended, which is described in Algorithm 8. A natural question is whether the myopic policy can be computed in polynomial time. The answer is no; the difficulty is closely related to the NP-hardness of the Set Cover problem. See Proposition EC.1. Proposition EC.1. For any customer order St , it is NP-hard to calculate the myopic fulfillment quantities tmik,t uk,i that minimize the fulfillment cost of this order. Proof of Proposition EC.1.

Given any instance of Set Cover, we show how it can be represented

by an instance of the fulfillment problem. Suppose we have a universe U “ t1, . . . , nu and a collection of subsets C “ tC1 , . . . , CK u, where Ck Ď U for all k. We can construct an instance of the fulfillment problem as follows: we have n items and K FDCs, where the inventory of item i in FDC k is 1 if and only if i P Ck for all k “ 1, . . . , K. The fixed cost of FDC k is set to be 1 for all k “ 1, . . . , K, and the

ec28

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

Algorithm 8 Generalized Myopic Policy for Multiple-FDC Case for each time period t “ 1, 2, . . . , T do Observe customer order St ; Solve the following optimization problem to determine the fulfillment quantities: « ˜ ¸ ff K n n ÿ ÿ ÿ tmik,t uk,i “ arg min fk ¨ I mik,t ą 0 ` cik,t ¨ mik,t ; tmik,t uk,i

i“1

k“0

i“1

Fulfill the order according to the optimal fulfillment quantities tmik,t uk,i ; i i Update inventory levels: Ik,t Ð Ik,t´1 ´ mik,t for all k P rK s and i P rns.

fixed cost of RDC is set to be a sufficiently large number (e.g., larger than K). The variable costs are set to be 0 for all DCs. The customer order St is set to be p1, 1, . . . , 1q, i.e., one unit of each item is ordered. In this instance, the myopic policy selects a subset of FDCs to fulfill the order, and the fulfillment cost equals the number of selected FDCs. Therefore, computing the myopic policy is equivalent to finding a minimum set cover of U using the subsets in C, which is NP-hard. This completes the proof. ˝

As we can see, the myopic policy is not computationally efficient for the case with multiple FDCs, which motivates us to design more efficient policies such as Order-Size F-Priority and CostComparison V-Priority on both time-varying and time-invariant cases. LP-based Policies. We revisit the LP-based policies proposed in Jasin and Sinha (2015) and Ma (2023). These policies are designed for time-invariant variable costs and require a demand forecast, modeled as a probability distribution over customer orders. Orders are indexed by order type q P SQ , where SQ is the set of all possible order types. We write i P q (or q Q i) if order type q contains item i. Following their setting, we allow at most one unit of each item per order in this section. Let λq ř denote the arrival probability of order type q in any period t, satisfying q λq “ 1. The stochastic version of the online order fulfillment problem can then be formulated as the following stochastic optimization problem: C ˚ pT q “ min

T ÿ ÿ

E Dtq ¨

t“1 qPSQ

s.t.

T ÿ t“1 K ÿ

K ÿ k“0

i,q i Dtq Xk,t ď Ik,0 ,

i,q Xk,t “ 1,

k“0 i,q Xk,t P t0, 1u,

¸ff

fk ¨ max Xk,t ` ␣

( i,q

iPq

i,q cik ¨ Xk,t

iPq

@k P rK s, i P rns,

@t P rT s, q P SQ , i P q, @k P rK s, t P rT s, q P SQ , i P rns.

ec29

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

i,q where the decision variables Xk,t indicate whether item i in order type q is fulfilled by DC k at time

t, and Dtq is the indicator variable of whether order type q arrives at time t, satisfying ErDtq s “ λq for all t P rT s and q P SQ . The objective is to minimize the expected total fulfillment cost over the time horizon. Jasin and Sinha (2015) develop an approximate deterministic linear-program formulation of the i,q original stochastic optimization problem by replacing the random variables Xk,t and Dtq with their q expectations xi,q k,t and λ , respectively, and relaxing the integrality constraints. The linear program is

given as follows: ˚ CLP pT q “ min

T ÿ ÿ

λq

t“1 qPSQ

s.t.

T ÿ t“1 K ÿ

K ÿ

iPq

k“0

i λq xi,q k,t ď Ik,0 ,

xi,q k,t “ 1,

k“0 xi,q k,t ě 0,

¸ff

␣ ( ÿ i i,q fk ¨ max xi,q ck ¨ xk,t k,t `

iPq

@k P rK s, i P rns,

@t P rT s, q P SQ , i P q,

@k P rK s, t P rT s, q P SQ , i P rns.

Let xi,q k denote the average number of times item i in order type q is fulfilled from the DC k during the selling horizon and let ykq denote the average number of times order type q is (partially) fulfilled ˚ from the DC k during the selling horizon. The time-aggregate formulation of CLP pT q is given as

follows: « ˚ C̃LP pT q “ min T ¨

λq

qPSQ

K ÿ

k“0

¸ff

fk ¨ ykq `

cik ¨ xi,q k

iPq

i s.t. T ¨ λq xi,q @k P rK s, i P rns, k ď Ik,0 , K ÿ i,q xk “ 1, @t P rT s, q P SQ , i P q, k“0

ykq ě xi,q k ,

@k P rK s, q P SQ , i P q,

xi,q k ě 0,

@k P rK s, q P SQ , i P rns.

˚ ˚ It is not difficult to see that C̃LP pT q “ CLP pT q ď C ˚ pT q using Jensen’s inequality. After solving q the linear program and obtaining the optimal solution txi,q k , yk uk,i,q , Jasin and Sinha (2015) and Ma

(2023) propose different correlated rounding schemes to round the fractional solution to an integral solution, which can be implemented as an online fulfillment policy. In Jasin and Sinha (2015), they propose two rounding schemes. The first one is the independent rounding scheme, namely IPFC (Independent Probabilistic Fulfillment Control) policy, which indei,q i,q i,q K pendently rounds txi,q k uk“0 to 0 or 1 with probability xk , i.e. PrrXk,t “ 1s “ xk . The second one

is the dependent rounding scheme, namely DPFC (Dependent Probabilistic Fulfillment Control)

ec30

e-companion to : Gated Priority-based Greedy Policies for Two-layer Multi-item Order Fulfillment

policy, which rounds xi,q k in a dependent manner to ensure that the fulfillment decisions of different items in the same order type are correlated. They show that both IPFC and DPFC policies achieve an expected competitive ratio growing linearly with the expected order size Er|q |s. We refer readers to Jasin and Sinha (2015) for more details of the DPFC rounding scheme and their theoretical analysis. In Ma (2023), the authors propose two alternative correlated-rounding schemes, namely the Dilate policy and the ForceOpen policy. These policies construct new rounding rules and achieve improved expected competitive ratios, with growth rates that are logarithmic in the expected order size and linear in the number of FDCs, respectively. We refer readers to Ma (2023) for details of these rounding schemes and their theoretical analysis.

Record · ID 224534 · SHA-256 8b3e076579169cc1
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.