Thesis Title: Coordinated Resource Allocation

Advisors:

Dr. Pinar Keskinocak, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Mohit Singh, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Thesis Committee:

Dr. Mathieu Dahan, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Alejandro Toriello, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Ozlem Ergun, Department of Mechanical and Industrial Engineering, Northeastern University

Date and Time: Thursday, June 30th, 2022, at 10 am (EDT)

Location: Main 126

Meeting Link: Click here to join Teams meeting

Abstract: 

The efficient allocation and scheduling of scarce resources with the objective of minimizing total costs or maximizing total return is an important problem that arises in many diverse applications. In some instances, demands may rely on some level of coordination or collaboration between distinct resources (simultaneously or sequentially). Modeling resource interdependencies has vast applications in emergency response and healthcare management. For example, 911 centers may need to dispatch multiple ambulances, firetrucks, or police to larger incidents on a daily basis. Further, the management of natural and man-made disasters poses logistical challenges that lead to the need for coordination between distinct relief resources. Within the healthcare setting, hospital operations require coordinated scheduling of doctors, nurses, and operating rooms. Similarly, home health care patient visits may require various home health care professionals simultaneously (e.g., home health aides and registered nurses). In this thesis, we propose optimization-based techniques to examine the coordinated resource allocation problem: scheduling and planning distinct resource types to meet demands that request a subset of the available resource types simultaneously. The goal is to design optimal and approximate solutions under various levels of problem complexity that maximize the demands met while remaining feasible for the resource set.

In Chapter 2, we introduce the deterministic version of the coordinated resource allocation problem in a network setting. That is, we consider the heterogeneous multi-resource allocation problem (mRmD) where each demand requests a subset of resource types simultaneously at a specified time, location, and duration. The objective is to assign resources to demands to maximize the overall reward from satisfying demands. Emergency response decision-makers could apply this type of problem for capacity planning purposes. 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.

In Chapter 3, we extend our modeling from Chapter 2 to add demand uncertainty to the coordinated resource allocation problem in a network setting. We consider the problem of planning the capacity and allocation of multiple heterogeneous resources to meet a set of demands for given demand scenarios, where demands request a subset of the available resource types simultaneously at a specified time, location, and duration. The goals are to determine the number of resources of each resource type, assign resources to starting locations in each scenario, and assign resources to meet demands. We model this problem as a two-stage stochastic integer program and consider two variations for the objective function: (a) maximize the expected reward of demand met over all scenarios subject to a budget B for resources; (b) maximize the expected reward of demand met over all scenarios minus the cost of resources. We then show complexity, theoretical, algorithmic, and computational results for the problem definitions considered.

In Chapter 4, we consider the online coordinated resource allocation problem through the use of admission control. Specifically, we examine the special case of the coordinated resource allocation problem where demands request either a single resource type or all resource types, in the online setting. Using strong duality, we develop a complete characterization of the optimal policy for when there are two resource types. We then extend these results to present a partial characterization of the optimal policy for the general problem.