Reliability Analysis of Facility Systems Subject to Edge Failures: Based on the Uncapacitated Fixed-Charge Location Problem

ABSTRACT

A facility system can be modeled by a connected graph in which the vertices represent entities such as suppliers, distribution centers or customers and the edges represent facilities such as the paths of goods or information. The efficiency, and hence the reliability, of a facility system is to a large degree adversely affected by the edge failures in the network. Such failures may be caused by various natural disasters or terrorist attacks. In this paper, we consider facility systems’ reliability analysis based on the classical uncapacitated fixed-charge location problem when subject to edge failures. For an existing facility system, we formulate two models based on deterministic case and stochastic case to measure the loss in efficiency due to edge failures and give computational results and reliability envelopes for a specific example.

A facility system can be modeled by a connected graph in which the vertices represent entities such as suppliers, distribution centers or customers and the edges represent facilities such as the paths of goods or information. The efficiency, and hence the reliability, of a facility system is to a large degree adversely affected by the edge failures in the network. Such failures may be caused by various natural disasters or terrorist attacks. In this paper, we consider facility systems’ reliability analysis based on the classical uncapacitated fixed-charge location problem when subject to edge failures. For an existing facility system, we formulate two models based on deterministic case and stochastic case to measure the loss in efficiency due to edge failures and give computational results and reliability envelopes for a specific example.

Cite this paper

nullZ. Wei and H. Xiao, "Reliability Analysis of Facility Systems Subject to Edge Failures: Based on the Uncapacitated Fixed-Charge Location Problem,"*Open Journal of Discrete Mathematics*, Vol. 1 No. 3, 2011, pp. 153-159. doi: 10.4236/ojdm.2011.13019.

nullZ. Wei and H. Xiao, "Reliability Analysis of Facility Systems Subject to Edge Failures: Based on the Uncapacitated Fixed-Charge Location Problem,"

References

[1] J. C. James and S. A. Salhi, “Tabu Search Heuristic for the Location of Multi-Type Protection Devices on Electrical Supply Tree Networks,” Journal of Combinatorial Optimization, Vol. 6, No. 1, 2002, pp. 81-98. doi:10.1023/A:1013322309009

[2] H. A. Eiselt, M. Gendreau and G. Laporte, “Location of Facilities on a Network Subject to a Single-Edge Failure,” Networks, Vol. 22, No. 3, 1992, pp. 231-246. doi:10.1002/net.3230220303

[3] C. L. Monma, “Minimum-Weight Two Connected Spanning Networks,” Mathematical Programming, Vol. 46, No. 2, 1990, pp. 153-171. doi:10.1007/BF01585735

[4] C. L. Monma and D. F. Shalcross, “Methods for Designing Communications Networks with Certain 2-Connected Survivability Constraints,” Operations Research, Vol. 37, No. 4, 1989, pp. 531-541. doi:10.1287/opre.37.4.531

[5] D. E. Bienstock, E. F. Brickell and C. L. Monma, “On the Structure of Minimum Weight Kconnected Spanning Networks,” SIAM Journal on Discrete Mathematics, Vol. 3, No. 3, 1990, pp. 320-329. doi:10.1137/0403027

[6] B. Fortz and M. Labbe, “Polyhedral Results for Two-Connected Networks with Bounded Rings,” Mathematical Programming Series A, Vol. 93, No. 1, 2002, pp. 27- 54. doi:10.1007/s10107-002-0299-9

[7] M. Bundschuh, D. Klabjan and D. L. Thurston, “Modeling Robust and Reliable Supply Chains,” Working Paper, University of Illinois, Urbana-Champaign, IL. 2003.

[8] D. A. Erlenkotter, “A Dual-Based Procedure for Uncapacitated Facility Location,” Operations Research, Vol. 26, No. 6, 1978, pp, 992-1009. doi:10.1287/opre.26.6.992

[9] M. L. Balinski, “Integer Programming: Methods, Uses, Computation,” Management Science, Vol. 12, No. 3, 1965, pp. 253-313. doi:10.1287/mnsc.12.3.253

[10] R. D. Galvao and L. A. Raggi, “A Method for Solving to Optimality Un-Capacitated Location Problems,” Annals of Operations Research, Vol. 18, No. 1, 1989, pp. 225-244. doi:10.1007/BF02097805

[11] L. V. Snyder and Z. J. M. Shen, “Managing Disruptions to Supply Chains,” The Bridge National Academy of Enginee-Ring, Vol. 36, 2006, pp. 39-45 (Forthcoming).

[12] P. B. Mirchandani and R. L. Francis, “Discrete location Theory,” Wiley, New York, 1990.

[13] J. Krarup and P. M. Pruzan, “The Simple Plant Location Problem: Survey and Synthesis,” European Journal of Operational Research, Vol. 12, No. 1, 1983, pp. 36-81. doi:10.1016/0377-2217(83)90181-9

[14] R. D. Carr, et al. “Robust Optimization of Contaminant Sensor Placement for Community Water Systems,” Mathematical Programming, Vol. 107, No.1-2, 2005. 337-356. doi:10.1007/s10107-005-0689-x

[15] R. L.Church, M. P. Scaparra and R. S. Middleton, “Identifying Critical Infrastructure, the Median and Covering Facility Interdiction Problems,” Annals of the Association of American Geographers, Vol. 94, No. 3, 2004, pp. 491- 502. doi:10.1111/j.1467-8306.2004.00410.x

[16] R. L. Church and M. P. Scaparra, “Critical Infrastructure,” Chapter 11, Springer Berlin Heidelberg, Berlin, 2007.

[1] J. C. James and S. A. Salhi, “Tabu Search Heuristic for the Location of Multi-Type Protection Devices on Electrical Supply Tree Networks,” Journal of Combinatorial Optimization, Vol. 6, No. 1, 2002, pp. 81-98. doi:10.1023/A:1013322309009

[2] H. A. Eiselt, M. Gendreau and G. Laporte, “Location of Facilities on a Network Subject to a Single-Edge Failure,” Networks, Vol. 22, No. 3, 1992, pp. 231-246. doi:10.1002/net.3230220303

[3] C. L. Monma, “Minimum-Weight Two Connected Spanning Networks,” Mathematical Programming, Vol. 46, No. 2, 1990, pp. 153-171. doi:10.1007/BF01585735

[4] C. L. Monma and D. F. Shalcross, “Methods for Designing Communications Networks with Certain 2-Connected Survivability Constraints,” Operations Research, Vol. 37, No. 4, 1989, pp. 531-541. doi:10.1287/opre.37.4.531

[5] D. E. Bienstock, E. F. Brickell and C. L. Monma, “On the Structure of Minimum Weight Kconnected Spanning Networks,” SIAM Journal on Discrete Mathematics, Vol. 3, No. 3, 1990, pp. 320-329. doi:10.1137/0403027

[6] B. Fortz and M. Labbe, “Polyhedral Results for Two-Connected Networks with Bounded Rings,” Mathematical Programming Series A, Vol. 93, No. 1, 2002, pp. 27- 54. doi:10.1007/s10107-002-0299-9

[7] M. Bundschuh, D. Klabjan and D. L. Thurston, “Modeling Robust and Reliable Supply Chains,” Working Paper, University of Illinois, Urbana-Champaign, IL. 2003.

[8] D. A. Erlenkotter, “A Dual-Based Procedure for Uncapacitated Facility Location,” Operations Research, Vol. 26, No. 6, 1978, pp, 992-1009. doi:10.1287/opre.26.6.992

[9] M. L. Balinski, “Integer Programming: Methods, Uses, Computation,” Management Science, Vol. 12, No. 3, 1965, pp. 253-313. doi:10.1287/mnsc.12.3.253

[10] R. D. Galvao and L. A. Raggi, “A Method for Solving to Optimality Un-Capacitated Location Problems,” Annals of Operations Research, Vol. 18, No. 1, 1989, pp. 225-244. doi:10.1007/BF02097805

[11] L. V. Snyder and Z. J. M. Shen, “Managing Disruptions to Supply Chains,” The Bridge National Academy of Enginee-Ring, Vol. 36, 2006, pp. 39-45 (Forthcoming).

[12] P. B. Mirchandani and R. L. Francis, “Discrete location Theory,” Wiley, New York, 1990.

[13] J. Krarup and P. M. Pruzan, “The Simple Plant Location Problem: Survey and Synthesis,” European Journal of Operational Research, Vol. 12, No. 1, 1983, pp. 36-81. doi:10.1016/0377-2217(83)90181-9

[14] R. D. Carr, et al. “Robust Optimization of Contaminant Sensor Placement for Community Water Systems,” Mathematical Programming, Vol. 107, No.1-2, 2005. 337-356. doi:10.1007/s10107-005-0689-x

[15] R. L.Church, M. P. Scaparra and R. S. Middleton, “Identifying Critical Infrastructure, the Median and Covering Facility Interdiction Problems,” Annals of the Association of American Geographers, Vol. 94, No. 3, 2004, pp. 491- 502. doi:10.1111/j.1467-8306.2004.00410.x

[16] R. L. Church and M. P. Scaparra, “Critical Infrastructure,” Chapter 11, Springer Berlin Heidelberg, Berlin, 2007.