TOPOLOGICAL DESIGN OF A CENTRALIZED COMMUNICATION-NETWORK WITH UNRELIABLE LINKS AND NODE OUTAGE COSTS

作     者：DUTTA, A KAWATRA, R 

作者机构：MANKATO STATE UNIVCOLL BUSINESSPOB 8400MANKATOMN 56002 GEORGE MASON UNIVDEPT DECIS SCI & MISFAIRFAXVA 22030 

出 版 物：《EUROPEAN JOURNAL OF OPERATIONAL RESEARCH》 (欧洲运筹学杂志)

年 卷 期：1994年第77卷第2期

页      面：344-356页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：COMPUTERS COMMUNICATIONS NETWORK PROGRAMMING 

摘      要：In this paper, we present a mathematical formulation of a terminal layout problem in the design of a centralized communication network with unreliable links and node outage costs. The node outage cost associated with a terminal node is a cost incurred by the network user whenever that terminal node is unable to communicate with the central node due to failure of a link. We suggest a two-phase heuristic with a time complexity of O(N3) to solve the problem. We also present a Lagrangean relaxation method to find the lower bound of the objective function value. The lower bound given by the Lagrangean relaxation method is used to estimate the quality of the solution given by the two-phase heuristic. Experimental results over a wide range of problem structures show that the average solution given by the two-phase heuristic is within 10% of the optimal objective function value.