CAJ | 학술논문

在确定性的容错设施布局问题中,给定顾客的集合和地址的集合.在每个地址上可以开设任意数目的不同设施.每个顾客j有连接需求rj.允许将顾客j连到同一地址的不同设施上.目标是开设一些设施并将每个顾客j连到rj个不同的设施上,使得总开设费用和连接费用最小.研究两阶段随机容错设施布局问题(SFTFP),顾客的集合事先不知道,但是具有有限多个场景并知道其概率分布.每个场景指定需要服务的顾客的子集.并且每个设施有两种类型的开设费用.在第一阶段根据顾客的随机信息确定性地开设一些设施,在第二阶段根据顾客的真实信息再增加开设一些设施.给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.
재학정성적용착설시포국문제중,급정고객적집합화지지적집합.재매개지지상가이개설임의수목적불동설시.매개고객j유련접수구rj.윤허장고객j련도동일지지적불동설시상.목표시개설일사설시병장매개고객j련도rj개불동적설시상,사득총개설비용화련접비용최소.연구량계단수궤용착설시포국문제(SFTFP),고객적집합사선불지도,단시구유유한다개장경병지도기개솔분포.매개장경지정수요복무적고객적자집.병차매개설시유량충류형적개설비용.재제일계단근거고객적수궤신식학정성지개설일사설시,재제이계단근거고객적진실신식재증가개설일사설시.급출수궤용착포국문제적선성정수규화화기우선성규화사입적5-근사산법.
In the deterministic fault-tolerant facility placement problem (FTFP),we are given a set of locations and a set of clients.We can open any number of different facilities with the same opening cost at each location.Each client j has an integer requirement rj.Connecting client j to different facilities at the same location is permitted.The objective is to open some facilities and connect each client j to rj different facilities such that the total cost is minimized.In this paper,we consider the two-stage stochastic fault-tolerant facility placement problem (SFTFP) with recourse in which the set of clients are unknown in advance.But there are finite scenarios materialized by a probability distribution.Each scenario specifies a subset of clients to be assigned.Moreover,each facility has two kinds of opening cost.In the first stage,we open a subset of facilities according to the stochastic information of the clients.In the second stage,we can open additional number of facilities when the actual information of the clients is revealed.We give a linear integral program and an LP-rounding based 5-approximation algorithm for the SFTFP.