随机容错设施布局问题的近似算法

• 作者: 徐大川 邵嘉婷
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 设施布局问题 近似算法 线性规划舍入
• 年，卷（期）: 2012,（1）
• 页码范围: 13-20
• 分类号: O221.7
• 字数: 1922字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2012.01.002

摘要

在确定性的容错设施布局问题中,给定顾客的集合和地址的集合.在每个地址上可以开设任意数目的不同设施.每个顾客j有连接需求rj.允许将顾客j连到同一地址的不同设施上.目标是开设一些设施并将每个顾客j连到rj个不同的设施上,使得总开设费用和连接费用最小.研究两阶段随机容错设施布局问题(SFTFP),顾客的集合事先不知道,但是具有有限多个场景并知道其概率分布.每个场景指定需要服务的顾客的子集.并且每个设施有两种类型的开设费用.在第一阶段根据顾客的随机信息确定性地开设一些设施,在第二阶段根据顾客的真实信息再增加开设一些设施.给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐大川	北京工业大学数理学院	18	30	3.0	4.0
2	邵嘉婷	北京工业大学数理学院	3	4	1.0	2.0