TY - JOUR
T1 - A Probabilistic Analysis of the Multi-period Single-sourcing Problem
AU - Romeijn, H. Edwin
AU - Romero Morales, Dolores
PY - 2001
Y1 - 2001
N2 - The multi-period single-sourcing problem (MPSSP) is the problem of finding an assignment, over time, of customers to warehouses such that each customer is assigned to exactly one warehouse in each period, subject to capacity constraints, such that the total transportation and inventory costs are minimized. We propose a general stochastic model for the MPSSP, and derive a tight condition on this stochastic model under which the MPSSP is feasible with probability 1 when the number of customers goes to infinity. This result can be used to generate suitable experimental data. Moreover, we show that the normalized optimal value of the problem converges almost surely to a constant, for which we provide an explicit expression; this property can be useful in constructing asymptotically optimal heuristics for the problem. The rate of convergence to the limiting value is illustrated empirically.
AB - The multi-period single-sourcing problem (MPSSP) is the problem of finding an assignment, over time, of customers to warehouses such that each customer is assigned to exactly one warehouse in each period, subject to capacity constraints, such that the total transportation and inventory costs are minimized. We propose a general stochastic model for the MPSSP, and derive a tight condition on this stochastic model under which the MPSSP is feasible with probability 1 when the number of customers goes to infinity. This result can be used to generate suitable experimental data. Moreover, we show that the normalized optimal value of the problem converges almost surely to a constant, for which we provide an explicit expression; this property can be useful in constructing asymptotically optimal heuristics for the problem. The rate of convergence to the limiting value is illustrated empirically.
KW - Probabilistic analysis
KW - Generalized Assignment Problem
KW - Dynamic assignments
U2 - 10.1016/S0166-218X(00)00320-6
DO - 10.1016/S0166-218X(00)00320-6
M3 - Journal article
SN - 0166-218X
VL - 112
SP - 301
EP - 328
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1-3
ER -