The design of service systems with queueing time cost, workload capacities and backup service

This paper studies a reliable service system design problem that involves locating service facilities, determining their number of capacities and assigning user nodes to those facilities. The goal is to minimize total costs made of the costs of accessing facilities by users and waiting for service at these facilities as well as the cost of setting up and operating the facilities. The service system is designed in such a way that backup service is provided to user nodes while controlling facility workload. This problem arises mainly in the area of telecommunication network design. But it is quite general and can be encountered in several planning contexts such as transportation planning, siting of emergency service facilities and refuse collection and disposal in the public sector. The paper represents a significant improvement over previous research by presenting a unified model of the problem that includes the number, locations, and capacities of service facilities as variables to be determined, incorporates in the total cost to be minimized the user waiting time (queueing) cost, and provides backup service to user nodes. An integer programming formulation of the problem with a nonlinear objective function is presented. Two heuristic solution procedures based on a Lagrangean relaxation of the problem are developed. Extensive computational results across a variety of problem structures are reported. These results indicate that the second solution procedure is very effective for a wide range of problem structures and traffic loads.