Heterogeneous Multi-resource Allocation with Subset Demand Requests
Arden Baxter, Pinar Keskinocak, Mohit Singh
INFORMS Journal on Computing · 2022 · Volume 34 · Issue 5
Abstract
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.
Keywords
deterministic integer programming, resource allocation, network flows, complexity analysis
Enable JavaScript for citation tools and additional paper interactions.