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

Efficiently Computed Periodic Ordering Heuristics in Stochastic Distribution Systems 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 models that are easier to scrutinize. In “Heuristic (S,T) Solutions via an FPTAS for a One-Warehouse Multiretailer Problem,” Najy, Elbassioni, and Diabat show how to efficiently compute competitive solutions for such systems based on an approximate formulation of the inventory problem proposed by Chu and Shen (2010) and build on the assumption of power-of-two (POT) policies. The authors first devise a fully polynomial-time approximation scheme for the continuous relaxation of the model and then show how to round it to a POT solution within an improved approximation factor relative to the present literature. These solutions are shown via simulation to be highly competitive with optimal (S,T) solutions and are derived in a tiny fraction of the time needed by the current best (S,T) algorithms.