MailPal: Min-Max Optimization for Multi-Agent Task Scheduling in Heterogeneous Systems
Abstract
We consider the Heterogeneous Task Allocation Problem (HTAP) where a set of type specific and generic tasks must be allocated among a fleet of heterogeneous agents so as to minimize the maximum tour cost incurred by any agent. Building on the work of Prasad et al. (2018), we implement a 2-approximate TSP (via MST doubling) and a simple split tour routine. Then we run the HeteroMinMaxSplit algorithm (binary-searching the max-cost bound) to allocate tasks and minimize the worst tour, and evaluate its performance in a simulated environment. Our results demonstrate that accounting for type-specific load during generic task allocation yields significantly lower max-tour costs.