Optimal Location of Facilities on a Network in Which Each Facility is Operating as an M/G/1 Queue

Tomoki Hamaguchi, Koichi Nakade

.

DOI: 10.4236/jssm.2010.33036                

Abstract

In this paper, we consider a facility location problem in which customers and facilities are located on a network, and each facility is assumed to be operating as an M/G/1 queuing system. In many situations, the customer chooses the nearest facility to receive service. Customer satisfaction is evaluated by the probability of waiting less than or equal to a certain time for a customer that is chosen randomly from all customers who arrives to the system. By using a computational method for obtaining the probability on the waiting time, we propose the computational heuristic methods for finding the optimal location. Numerical results show the following. First, it is shown that the tabu search with an initial solution generated by random numbers gives the near-optimal solution with the highest probability among several algorithms. Second, the computation time and solution quality are not sensitive to the sharp of the service time distribution. Third, the computation time and solution quality are highly sensitive to the system utilization. Fourth, the complete enumeration might be the best solution methodology for highly utilized systems.

Keywords

Facility Location, M/G/1 Queues, Waiting Time, Tabu Search

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. Boffey, R. Galvao and L. Espejo, “A Review of Congestion Models in the Location of Facilities with Immobile Servers,” European Journal of Operational Research, Vol. 178, No. 3, 2007, pp. 643-662.
[2]	Q. Wang, R. Batta and C. Rump, “Algorithms for a Facility Location Problem with Stochastic Customer Demand and Immobile Servers,” Annals of Operations Research, Vol. 111, No. 1-4, 2002, pp. 17-34.
[3]	I. Castillo, A. Ingolfsson and T. Sim, “Social Optimal Location of Facilities with Fixed Servers, Stochastic Demand, and Congestion,” Production and Operations Management, Vol. 18, No. 6, 2010, pp. 721-736.
[4]	O. Berman, D. Krass and J. Wang, “Locating Service Facilities to Reduce Lost Demand,” IIE Transactions, Vol. 38, No. 11, 2006, pp. 33-946.
[5]	E. Elhedhli, “Service System Design with Immobile Servers, Stochastic Demand, and Congestion,” Manufacturing and Service Operations Management, Vol. 8, No. 1, 2006, pp. 92-97.
[6]	O. Baron, O. Berman and D. Krass, “Facility Location with Stochastic Demand and Constraints on Waiting Time,” Manufacturing and Service Operations Management, Vol. 10, No. 3, 2008, pp. 484-505.
[7]	H. Tijms, “A First Course in Stochastic Models,” Wiley, New York, 2003.