Online scheduling problems with flexible release dates: Applications to infrastructure restoration

摘要

We consider scheduling problems with the new concept of flexible release dates under an online optimization framework. A flexible release date is one where the traditional release date of a specific operation can be moved earlier in time, specifically to the completion time of an associated supplementary operation. In this context, we examine two classes of parallel identical machines: those that perform supplementary operations to alter release dates and those that perform installation operations to change the network characteristics. We further consider multi-function machines that can perform both supplementary and installation operations. The release date of an operation is often determined by events outside the knowledge of the decision-maker. Therefore, we consider scheduling problems in an online setting to model the lack of- and evolution of information about the release dates of tasks. Motivated by infrastructure restoration after an extreme event, we consider flexible release dates for an integrated network design and scheduling problem that seeks to improve the performance of a network over time by selecting and scheduling operations that will change the network characteristics. To solve these problems, we propose heuristic dispatching rules whose solutions are benchmarked against the solutions of a mixed integer programming formulation. Using a realistic infrastructure network, we perform computational tests; the results of these tests demonstrate the ability of the dispatching rule to find high-quality solutions in real time and quickly adapt to the arrival of new information. From the analysis of these results, we deduce policy insights regarding the role of flexible release dates and the machine fleet configuration. (C) 2017 Elsevier Ltd. All rights reserved.