A Probabilistic Analysis of the Multi-period Single-sourcing Problem

H. Edwin Romeijn, Dolores Romero Morales

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TidsskriftDiscrete Applied Mathematics
Vol/bind112
Udgave nummer1-3
Sider (fra-til)301–328
ISSN0166-218X
DOI
StatusUdgivet - 2001
Udgivet eksterntJa

Emneord

  • Probabilistic analysis
  • Generalized Assignment Problem
  • Dynamic assignments

Citer dette

@article{b0f2c39785dd47beaa1ed181ebd03b55,
title = "A Probabilistic Analysis of the Multi-period Single-sourcing Problem",
abstract = "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.",
keywords = "Probabilistic analysis, Generalized Assignment Problem, Dynamic assignments",
author = "Romeijn, {H. Edwin} and {Romero Morales}, Dolores",
year = "2001",
doi = "10.1016/S0166-218X(00)00320-6",
language = "English",
volume = "112",
pages = "301–328",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier BV North-Holland",
number = "1-3",

}

A Probabilistic Analysis of the Multi-period Single-sourcing Problem. / Romeijn, H. Edwin; Romero Morales, Dolores .

I: Discrete Applied Mathematics, Bind 112, Nr. 1-3, 2001, s. 301–328.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

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

VL - 112

SP - 301

EP - 328

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-3

ER -