Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
Authors:
Abstract
We consider the class of integrated network design and scheduling (INDS) problems that focus on selecting and scheduling operations that will change the characteristics of a network, while being specifically concerned with the performance of the network over time. Motivating applications of INDS problems include infrastructure restoration after an extreme event and building humanitarian logistics networks. We examine INDS problems under a parallel identical machine scheduling environment where the performance of the network is evaluated by solving classic network optimization problems. We prove that all considered INDS problems are NP‐hard. We propose a novel heuristic dispatching rule algorithm framework that selects and schedules sets of arcs based on their interactions in the network. These interactions are measured by examining network optimality conditions. Computational testing of these dispatching rules on realistic data sets representing infrastructure networks of lower Manhattan, New York demonstrates that they arrive at near‐optimal solutions in real‐time.Copyright © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 306–326 2014Keywords
Funding Information
- Sandia National Laboratories and Rensselaer Polytechnic Institute (RPI)
This publication has 21 references indexed in Scilit:
- The flowtime network construction problemIIE Transactions, 2012
- Emergency path restoration problemsDiscrete Optimization, 2012
- Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systemsAnnals of Operations Research, 2011
- Electricity storage for grid-connected household dwellings with PV panelsSolar Energy, 2010
- Transit network design and scheduling: A global reviewTransportation Research Part A: Policy and Practice, 2008
- Optimizing scheduling of post‐earthquake electric power restoration tasksEarthquake Engineering & Structural Dynamics, 2006
- Service network design in freight transportationEuropean Journal of Operational Research, 2000
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- A dual ascent approach for steiner tree problems on a directed graphMathematical Programming, 1984
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979