Adaptive and Robust Resource Allocation and Scheduling

摘要

This grant explored the design and implementation of adaptive and robust resource allocation and scheduling. It was motivated by the widespread dissemination of telecommunication technologies that enable organizations to track their operations in real-time using technologies such as GPS, RFIDs, sensors, and high-performance networks. The ubiquity of telecommunication technologies has led to a paradigm shift in business processes that has produced integrated supply chains, sense-and-response logistics, and lean manufacturing. It also is producing a fundamental transformation in optimization and decision support systems. Organizations can now exploit a wealth of historical and real-time data, moving their traditional focus from a priori planning to real-time decision making under uncertainty. This grant has studied a wide variety of algorithms for decision making under uncertainty, large-scale optimization, and finding high-quality solutions to complex problems quickly. The main contributions have been as follows: (1) a framework of online stochastic combinatorial optimization algorithms (i.e., making decisions during operations, sampling the distributions of the uncertainty, optimizing the obtained scenarios, and aggregating their optimal solutions into robust solutions across all scenarios); (2) the design and analysis of one-step anticipatory algorithms and their applications to a variety of routing, scheduling, and resource allocation problems; (3) the design and analysis of multi-step anticipatory algorithms and their applications to resource allocation problems; and (4) the implementation of decomposition techniques for large-scale logistics applications and, in particular, the use of these techniques to find high-quality solutions quickly. This report includes a list of related publications and two patents.