OPTIMAL ALLOCATION OF 2 FIXED SERVICE UNITS ACTING AS M G/1 QUEUES/

We consider a districting problem placed in. the general context of op timal allocation of urgent services in. the presence of congestion. Cu stomers are located in fixed points of a physical space and ash for ur gent service according to Poisson processes. Two facilities, located i n fixed points, supply the service by acting as M/G/1 queues. Each cus tomer shall be assigned to one of the two facilities so that the mean expected response time is minimized, where the response time is the su m of the transportation time, the wait-in-queue time and the service t ime. We formalize the problem as an integer nonlinear programming mode l and we exactly solve it by a suitable branch-and-bound procedure. We show that the problem, if relaxed with respect to integrality constra ints, can, be reduced to an equivalent convex minimization problem wit h only one variable. Actually, each step of the branch-and-bound proce dure is performed by quickly solving a continuous single-variable mini mization problem. We randomly generate a large amount of instances of practical size, and we solve them on a workstation. Short computing ti mes (<50 sees CPU for the worst experimented case) are evidenced. Sinc e the problem is recognized to be NP-hard, we also suggest a simple he uristic method with low complexity.