We study the capacity planning and allocation decisions for multiple heterogeneous resources, considering potential demand scenarios, where each demand requests a subset of the available resource types simultaneously at a specified time, location, and duration (smRmD). We model this problem as a two-stage stochastic integer program and consider two variants for the objective function: (a) maximize the expected reward of demands met over all scenarios, subject to a budget B for resources, and (b) maximize the expected reward of demands met over all scenarios minus the cost of resources. Contributions of this work include (i) a thorough complexity analysis of smRmD and its variants, (ii) analysis of structural properties, (iii) development of various approximation algorithms using the unique structural properties of smRmD and its variants, and (iv) an extensive computational study to explore the ease with which exact and approximate solutions may be found. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This research has been supported in part by National Science Foundation (NSF) Graduate Research Fellowship [DGE-1650044], NSF [Grants CMMI-1538860, NSF-AF:1910423, and NSF-AF:1717947], and the following Georgia Tech benefactors: William W. George, Andrea Laliberte, Richard ”Rick” E. & Charlene Zalesky, and Claudia & Paul Raines.

We consider the problem of allocating multiple heterogeneous resources geographically and over time to meet demands that require some subset of the available resource types simultaneously at a specified time, location, and duration. The objective is to maximize the total reward accrued from meeting (a subset of) demands. We model this problem as an integer program, show that it is NP-hard, and analyze the complexity of various special cases. We introduce approximation algorithms and an extension to our problem that considers travel costs. Finally, we test the performance of the integer programming model in an extensive computational study.

We discuss the evaluation of expected tardiness of an order at the time of arrival in an M/M/c queuing system with N priority classes, considering both nonpreemptive and preemptive service disciplines. Upon arrival, a customer order is quoted a lead time of d, and placed in the queue according to the priority class of the customer. Orders within the same priority class are processed on a first-come, first-served basis. We derive the Laplace transforms of the expected tardiness of the order given the quoted lead time, priority class of the order, and system status. For the special case of single priority class, the Laplace transform can be inverted into a closed-form expression. For the case with multiple priority classes, a closed-form expression cannot be obtained, hence, we develop three customized numerical inverse Laplace transformation algorithms. Two of these algorithms provide upper and lower bounds for the expected tardiness under a simple condition on system parameters. Using this property, we obtain error bounds for our customized algorithms; such bounds are not available for general purpose numerical inversion algorithms in the literature. Next, we develop a novel methodology to compare the precision of general purpose numerical inversion algorithms and analyze the performances of three algorithms from the literature. Finally, we provide a recommendation scheme given computational time and error tolerances of the decision maker. The methods developed in this paper for the accurate estimation of expected tardiness establish an important step toward developing due date quotation policies in a multiclass queue, contributing to the due date quotation literature that has been largely focused on single-class queues.

OBJECTIVE: To evaluate the benefit of a health information exchange (HIE) between hospitals, we examine the rate of crossover among neurosurgical inpatients treated at Emory University Hospital (EUH) and Grady Memorial Hospital (GMH) in Atlanta, Georgia. To inform decisions regarding investment in HIE, we develop a methodology analyzing crossover behavior for application to larger more general patient populations. DESIGN: Using neurosurgery inpatient visit data from EUH and GMH, unique patients who visited both hospitals were identified through classification by name and age at time of visit. The frequency of flow patterns, including time between visits, and the statistical significance of crossover rates for patients with particular diagnoses were determined. MEASUREMENTS: The time between visits, flow patterns, and proportion of patients exhibiting crossover behavior were calculated for the total population studied as well as subpopulations. RESULTS: 5.25% of patients having multiple visits over the study period visited the neurosurgical departments at both hospitals. 77% of crossover patients visited the level 1 trauma center (GMH) before visiting EUH. LIMITATIONS: The true patient crossover may be under-estimated because the study population only consists of neurosurgical inpatients at EUH and GMH. CONCLUSION: We demonstrate that detailed analysis of crossover behavior provides a deeper understanding of the potential value of HIE.

Auctions are promising decentralized methods for teams of agents to allocate and re-allocate tasks among themselves in dynamic, partially known and time-constrained domains with positive or negative synergies among tasks. Auction-based coordination systems are easy to understand, simple to implement and broadly applicable. They promise to be efficient both in communication (since agents communicate only essential summary information) and in computation (since agents compute their bids in parallel). Artificial intelligence research has explored auction-based coordination systems since the early work on contract networks, mostly from an experimental perspective. This overview paper describes our recent progress towards creating a framework for the design and analysis of cooperative auctions for agent coordination.

We study multi-robot routing problems (MR-LDR) where a team of robots has to visit a set of given targets with linear decreasing rewards over time, such as required for the delivery of goods to rescue sites after disasters. The objective of MR-LDR is to find an assignment of targets to robots and a path for each robot that maximizes the surplus, which is defined to be the total reward collected by the team minus its total travel cost. We develop a mixed integer program that solves MR-LDR optimally with a flow-type formulation and can be solved faster than the standard TSP-type formulations but also show that solving MR-LDR optimally is NP-hard. We then develop an auction-based algorithm and demonstrate that it solves MR-LDR in seconds and with a surplus that is comparable to the surplus found by the mixed integer program with a 12 hour time limit.

Multiple robots are often faster and more fault- tolerant than single robots for applications such as planetary exploration and search and rescue. We study applications where robots move in two-dimensional terrain and have to visit targets of given priorities during given time windows that do not overlap. We analyze the complexity of these coordination tasks and, where possible, use techniques from operations research to develop coordination methods that are efficient and optimize the team performance. We then develop auction-based coordination methods that build on these results and show experimentally that they run in seconds and achieve good team performance for NP-hard coordination tasks.

Object-oriented (OO) technologies have become widely adopted in enterprise applications due to the additional functionality and flexibility they provide to these applications. At the same time, however, OO technologies also require significant amounts of computational power to support, greatly impacting the performance and scalability of such applications. A very popular solution to mitigate this problem is object caching. In this paper, we show how the application of object caching maps into an optimization problem. In particular, we focus on the design-time decision of determining which objects should be candidates for caching. Choosing the cacheable objects is an important decision since it can have a significant impact on application performance. We formulate this problem as a linear integer program and present a heuristic solution approach. We also demonstrate, through a set of experiments, that our heuristic provides solutions that are reasonably close to optimal. Our contribution is a model and an efficient solution approach for this model that can help application developers to make more informed cacheability decisions and thereby improve application performance and scalability.

We consider the problem of allocating a number of exploration tasks to a team of mobile robots. Each task consists of a target location that needs to be visited by a robot. The objective of the allocation is to minimize the total cost, that is, the sum of the travel costs of all robots for visiting all targets. We show that finding an optimal allocation is an NP-hard problem, even in known environments. The main contribution of this paper is PRIM ALLOCATION, a simple and fast approximate algorithm for allocating targets to robots which provably computes allocations whose total cost is at most twice as large as the optimal total cost. We then cast PRIM ALLOCATION in terms of a multi-round single-item auction where robots bid on targets, which allow for a decentralized implementation. To the best of our knowledge, PRIM ALLOCATION is the first auction-based allocation algorithm that provides a guarantee on the quality of its allocations. Our experimental results in a multi-robot simulator demonstrate that PRIM ALLOCATION is fast and results in close-to-optimal allocations despite its simplicity and decentralized nature. In particular, it needs an order of magnitude fewer bids than a computationally intensive allocation algorithm based on combinatorial auctions, yet its allocations are at least as good.

We study how to coordinate a team of mobile robots to visit a number of given targets in a partially unknown terrain. Robotics researchers have studied single-item auctions to perform this exploration task but these do not make synergies between the targets into account. We therefore design combinatorial auctions, propose different combinatorial bidding strategies and compare their performance with each other, as well as to single item auctions and an optimal centralized mechanism. Our computational results in teambots, a multi-robot simulator, indicate that combinatorial auctions generally lead to significantly superior team performance than single-item auctions, and generate very good results compared to an optimal centralized mechanism.