Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules. Issue 4 (24th February 2014)

• Record Type: Journal Article
• Authors: Nurre, Sarah G.; Sharkey, Thomas C.
• Is Part Of: Networks. Volume 63:Issue 4(2014:Jul.)
• Page Start: 306
• Page End: 326
• Publication Date: 2014-02-24
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21547
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>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 <italic>NP</italic>‐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</p> </abstract>