Service System Design with Immobile Servers, Stochastic Demand, and Congestion

The service system design problem seeks to locate a set of service facilities, allocate enough capacity, and assign stochastic customer demand to each of them, so as to minimize the fixed costs of opening facilities and acquiring service capacity, as well as the variable access and waiting costs. This problem is commonly known in the location literature as the facility location problem with immobile servers, stochastic demand, and congestion. It is often set up as a network of M/M/1 queues and modeled as a nonlinear mixed-integer program (MIP). Because of the complexity of the resulting model, the current literature focuses on approximate and/or heuristic solution methods. This paper proposes a linearization based on a simple transformation and piecewise linear approximations and an exact solution method based on cutting planes. This leads to the exact solution of models with up to 100 customers, 20 potential service facilities, and 3 capacity levels.