论文部分内容阅读
设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中,受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障,故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法,是一个很大的进步.
The study of facility layout began in the 1960s with a focus on the location and number of facilities to be built and their distribution to the cities that need to be serviced so that the cost of the facility’s construction and the cost of connecting the facility to the city And in real life, due to natural disasters, workers strikes, terrorist attacks and other factors, the construction of facilities may be faulty, so the city connected to it can not be supplied, which directly affects the reliability of the entire system In view of how to improve the reliability of facility layout at a relatively small cost, the researchers put forward the problem of reliability facility layout.Reference to the greedy algorithm of classic facility layout problem, the original duality algorithm and the fault-tolerant problem, , A combinatorial algorithm is proposed to solve the problem of layout of reliability facilities.The algorithm not only has good constant approximation in theory but also has the advantage of low computational complexity.This is only a numerical experiment for the problem of layout of reliable facilities Algorithm, is a big step forward.