Abstract

Centralized computer networks are hierarchical communication infrastructures in which a central computer services a large number of terminals or workstations. For a large network, some concentrators are commonly used to increase the cost efficiency. Several terminals are connected to a concentrator via low capacity lines, and each concentrator is connected to the central computer via a high capacity line. A concentrator is generally subject to technological constraints on the amount of traffic it can manage, and each terminal has its capacity requirement. The problem then is to determine the number and location of concentrators and to allocate the terminals to these concentrators at minimum cost. This is known as the concentrator location problem. If the number and location of concentrators are already known beforehand, the problem then reduces to determining the allocation of terminals only. This is known as the terminal assignment problem. These problems are NP-complete. Therefore, finding a polynomial time algorithm to solve them to optimality is highly unlikely. This study aims to develop some efficient algorithms based on simulated annealing to solve these problems. The results are compared to those given by some existing heuristics.