Solving Facility Location Problem on Cluster Computing

Computation of facility location problem for every location in the country is not easy simultaneously. Solving the problem is described by using cluster computing. A technique is to design parallel algorithm by using local search with single swap method in order to solve that problem on clusters. Parallel implementation is done by the use of portable parallel programming, Message Passing Interface (MPI), on Microsoft Windows Compute Cluster. In this paper, it presents the algorithm that used local search with single swap method and implementation of the system of a facility to be opened by using MPI on cluster. If large datasets are considered, the process of calculating a reasonable cost for a facility becomes time consuming. The result shows parallel computation of facility location problem on cluster speedups and scales well as problem size increases.

Authors:

• Ei Phyo Wai
• Nay Min Tun

Keywords:

• cluster
• cost
• demand
• facility location

References:

[1] Anath Granma, Anshul Gupta, George Karypis and vipin Kumar,
"Introduction to Parallel Computing", 2nd ed.., 2003.
[2] Emir Imamagi, Damir Danijel Žagar, "Cluster Distributions Review," in
Department of Computer Systems,University Computing Centre,
Croatia, p. 1.
[3] Fraigniaud, Anne Mignotte, and Yves Robert, editors, Euro-Par '96
Parallel Processing, volume 1 of Lecture Notes in Computer Science, in
Luc Bouge, Springer Verlag, p 128-130., 1996.
[4] Candace Arai Yano, "On the Equivalence of an Equipment
Replcacement Problem and a Facility Location Problem," in department
of Industrial and Operations Engineering, December, 1984.
[5] Hai Jin, Rajkumar Buyya, Mark Baker, "Cluster Computing Tools,
Applications, and Australian Initiatives for Low Cost Supercomputing,"
in School of Computer Science, University of Portsmouth, Portsmouth,
Hants, UK, 2001, p. 2.
[6] E. Lusk. Programming with MPI on clusters. In 3rd IEEE
International Conference on Cluster Computing (CLUSTER-01),
October 2001.
[7] N. Ruest and D. Ruest, Deploying and Managing Microsoft Windows
Compute Cluster Server 2003, p.5-10, November 2005.