An approximation algorithm for a facility location problem with stochastic demands

Research output: Book/ReportReportProfessional

77 Downloads (Pure)

Abstract

In this article we propose, for any $\epsilon>0$, a $2(1+\epsilon)$-approximation algorithm for a facility location problem with stochastic demands. This problem can be described as follows. There are a number of locations, where facilities may be opened and a number of demand points, where requests for items arise at random. The requests are sent to open facilities. At the open facilities, inventory is kept such that arriving requests find a zero inventory with (at most) some pre-specified probability. After constant times, the inventory is replenished to a fixed order up to level. The time interval between consecutive replenishments is called a reorder period. The problem is where to locate the facilities and how to assign the demand points to facilities at minimal cost per reorder period such that the above mentioned quality of service is insured. The incurred costs are the expected transportation costs from the demand points to the facilities, the operating costs (opening costs) of the facilities and the investment in inventory (inventory costs).
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages17
Publication statusPublished - 2004

Publication series

NameMemorandum Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
No.1741
ISSN (Print)0169-2690

Keywords

  • MSC-68W25
  • MSC-90B06
  • EWI-3561
  • MSC-60K30
  • METIS-220775
  • IR-65925

Fingerprint

Dive into the research topics of 'An approximation algorithm for a facility location problem with stochastic demands'. Together they form a unique fingerprint.

Cite this