Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules

Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules

0.00 Avg rating0 Votes
Article ID: iaor201522248
Volume: 63
Issue: 4
Start Page Number: 306
End Page Number: 326
Publication Date: Jul 2014
Journal: Networks
Authors: ,
Keywords: design, combinatorial optimization, scheduling, heuristics
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.Copyrigh.

Reviews

Required fields are marked *. Your email address will not be published.