随机容错设施选址问题的原始-对偶近似算法

摘要：

研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现(在第一阶段不知道).两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合(称为场景).并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务.给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小.根据问题的特定结构,给出了原始-对偶(组合)3-近似算法.

关键词：设施选址问题、随机性、容错性、近似算法、原始-对偶算法

所属期刊栏目：18

分类号：O221.7(运筹学)

资助基金：国家自然科学基金11371001;北京市教育委员会科技计划面上项目KM2012-10005033;国家留学基金2011811166

在线出版日期：2014-08-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：17-28