Optimal allocation of two fixed service units acting as M/G/1 queues

Optimal allocation of two fixed service units acting as M/G/1 queues

0.00 Avg rating0 Votes
Article ID: iaor19962169
Country: United States
Volume: 30
Issue: 1
Start Page Number: 60
End Page Number: 74
Publication Date: Feb 1996
Journal: Transportation Science
Authors: ,
Keywords: queues: applications
Abstract:

The authors consider a districting problem placed in the general context of optimal allocation of urgent services in the presence of congestion. Customers are located in fixed points of a physical space and ask for urgent service according to Poisson processes. Two facilities, located in fixed points, supply the service by acting as M/G/1 queues. Each customer shall be assigned to one of the two facilities so that the mean expected response time is minimized, where the response time is the sum of the transportation time, the wait-in-queue time and the service time. The authors formalize the problem as an integer nonlinear programming model and they exactly solve it by a suitable branch-and-bound procedure. The authors show that the problem, if relaxed with respect to integrality constraints, can be reduced to an equivalent convex minimization problem with only one variable. Actually, each step of the branch-and-bound procedure is performed by quickly solving a continuous single-variable minimization problem. The authors ranodmly generate a large amount of instances of practial size, and they solve then on a workstation. Short computing times (¸<50 secs CPU for the worst experimeted case) are evidenced. Since the problem is recognized to be NP-hard, the authors also suggest a simple heuristic method with low complexity.

Reviews

Required fields are marked *. Your email address will not be published.