Heuristic (S, T) Solutions via an FPTAS for a One-Warehouse Multiretailer Problem

The difficulty of analyzing and optimizing the stochastic one-warehouse multiretailer problem under the (S, T) policy motivates the need to consider approximate but high-fidelity systems that are easier to scrutinize. We consider one such model in the setting in which retailers face independent normally distributed demand with given (nonidentical) means and variances. Safety stock is computed via a type-I service-level formula that ignores allocation issues, and the cost function is computed based on a power-of-two (POT) periodic ordering policy. A critical component of finding good solutions for this problem is solving the continuous relaxation of the optimization model involved. In doing so, the linking square root term introduced by the warehouse safety stock complicates this task as the cost does not decouple by individual retailers for a fixed warehouse replenishment interval. We alleviate this issue by substituting the linking term with an accurate piecewise linear estimator. We show how this helps us design a fully polynomial-time approximation scheme for the problem. From this, we can obtain a POT policy that has a guarantee of 1:061(1 + ε) for small ε and for any base planning period and 1:021(1 + ε) when the base planning period is optimally chosen, which is essentially the best possible guarantee up to the deterministic result. We show via an empirical study that the algorithm proposed returns heuristic (S, T) solutions that exhibit minimal suboptimality relative to the exact solution. Further, the time needed to compute these solutions is milliseconds for a handful of retailers (in contrast to the multiple hours required by the best existing methods) and just a few minutes for a system of one million retailers.