×

Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems. (English) Zbl 1272.90014

Summary: We consider the problem faced by managers of critical civil interdependent infrastructure systems of restoring essential public services after a non-routine event causes disruptions to these services. In order to restore the services, we must determine the set of components (or tasks) that will be temporarily installed or repaired, assign these tasks to work groups, and then determine the schedule of each work group to complete the tasks assigned to it. These restoration planning and scheduling decisions are often undertaken in an independent, sequential manner. We provide mathematical models and optimization algorithms that integrate the restoration and planning decisions and specifically account for the interdependencies between the infrastructure systems. The objective function of this problem provides a measure of how well the services are being restored over the horizon of the restoration plan, rather than just focusing on the performance of the systems after all restoration efforts are complete. We test our methods on realistic data representing infrastructure systems in New York City. Our computational results demonstrate that we can provide integrated restoration and scheduling plans of high quality with limited computational resources. We also discuss the benefits of integrating the restoration and scheduling decisions.

MSC:

90B35 Deterministic scheduling theory in operations research
90B22 Queues and service in operations research

Software:

NEOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs: Prentice-Hall. · Zbl 1201.90001
[2] Dolan, E. D., Fourer, R., Moré, J. J., & Munson, T. S. (2002). Optimization on the NEOS server. SIAM News, 35(6), 8–9.
[3] Gong, J., Lee, E. E., Mitchell, J. E., & Wallace, W. A. (2009). Logic-based multi-objective optimization for restoration planning. In W. Chaovalitwongse, K. C. Furman, & P. M. Pardalos (Eds.), Optimization and logistics challenges in the enterprise. Berlin: Springer. Chap. 11.
[4] Lee, E. E. (2006). Assessing vulnerability and managing disruptions to interdependent infrastructure systems: A network flows approach. PhD thesis, Rensselaer Polytechnic Institute, Troy, NY.
[5] Lee, E. E., Mitchell, J. E., & Wallace, W. A. (2007). Restoration of services in interdependent infrastructure systems: A network flows approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 37(6), 1303–1317. · doi:10.1109/TSMCC.2007.905859
[6] Lee, E. E., Mitchell, J. E., & Wallace, W. A. (2009). Network flow approaches for analyzing and managing disruptions to interdependent infrastructure systems. In J. G. Voeller (Ed.), Wiley handbook of science and technology for Homeland Security (Vol. 2, pp. 1419–1428). New York: Wiley.
[7] Lougee-Heimer, R. (2003). The common optimization interface for operations research. IBM Journal of Research and Development, 47(1), 57–66. · Zbl 05420370 · doi:10.1147/rd.471.0057
[8] Mendonca, D., & Wallace, W. A. (2006). Impacts of the 2001 World Trade Center attack on New York City critical infrastructures. Journal of Infrastructure Systems, 12(4), 260–270. · doi:10.1061/(ASCE)1076-0342(2006)12:4(260)
[9] O’Rourke, T. D. (2007). Critical infrastructure interdependencies, and resilience. The Bridge: National Academy of Engineering, 37(1), 22–29.
[10] Pinedo, M. L. (2008). Scheduling: Theory, algorithms, and systems. New York: Springer. · Zbl 1155.90008
[11] Rinaldi, S. M., Peerenboom, J. P., & Kelly, T. K. (2001). Identifying, understanding, and analyzing critical infrastructure interdependencies. IEEE Control Systems Magazine, 21(6), 11–25. · doi:10.1109/37.969131
[12] Savelsbergh, M. W. P., Uma, R. N., & Wein, J. (2005). An experimental study of LP-based approximation algorithms for scheduling problems. INFORMS Journal on Computing, 17, 123–136. · Zbl 1239.90053 · doi:10.1287/ijoc.1030.0055
[13] Sousa, J. P., & Wolsey, L. A. (1992). A time indexed formulation of non-preemptive single machine scheduling problems. Mathematical Programming, 54(3), 353–367. · Zbl 0768.90041 · doi:10.1007/BF01586059
[14] Wallace, W. A., Mendonca, D., Lee, E., Mitchell, J. E., & Chow, J. (2003). Managing disruptions to critical interdependent infrastructures in the context of the 2001 World Trade Center attack. In Beyond September 11th: An account of post-disaster research (pp. 165–198).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.