Premium
Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
Author(s) -
Nurre Sarah G.,
Sharkey Thomas C.
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21547
Subject(s) - computer science , scheduling (production processes) , heuristic , network planning and design , distributed computing , mathematical optimization , artificial intelligence , computer network , mathematics
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 2014