Robust Task Allocations by Distributing the Risk among Agents: Theory and Algorithms

We address the problem of generating robust solutions for the makespan minimization problem on identical agents (parallel machines), under the assumption that only interval bounds of processing times are known. While there are various concepts of robustness in the literature, we prove using pathological examples that any of these criteria may result in allocations with undesirable characteristics. We identify key properties that must be satisfied for a solution to be considered truly robust. Given a set of jobs with associated loads and uncertainties, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. Thus, robustness is achieved by distributing the uncertainty/risk among the agents along with the load. The problem of finding a robust allocation is reduced to a bi-criteria two-dimensional load balancing problem, with the two dimensions being the load and the uncertainty. We prove that for the case with 2 agents, an allocation that satisfies a 1.5-approximation on both dimensions simultaneously always exists and can be found efficiently, and is also the best possible guarantee. For the general case with any number of agents, we prove that an allocation that satisfies a 2-approximation on one dimension and a 2.5-approximation on the other always exists and can be found in pseudo-polynomial time. The approximation algorithms presented in this paper are complemented by interesting existential and structural results and contribute to the vector scheduling literature for two dimensions as well. Finally, an extensive numerical analysis is presented, where we demonstrate our algorithms' near-optimal performance and ability to generate allocations that satisfy multiple criteria of robustness simultaneously in a short amount of time. Note to Practitioners - This paper introduces a simple and provably effective methodology for generating robust allocations in the context of the makespan minimization problem, a critical challenge in operational management that significantly impacts the efficiency and productivity of various industries. We demonstrate using counter-examples that traditional concepts of robustness such as worst-case makespan and min-max regret can lead to overly conservative and practically inefficient allocations, even when solved optimally. Following this, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. This leads to a more attractive and practical concept of robustness. Efficient, fast, and provably good algorithms are presented that solve a 2D Load Balancing problem and generate allocations that are balanced with respect to both the loads as well as uncertainties for a large percentage of the possible scenarios. Numerical results provide practitioners confidence in our approach. The algorithm further classifies the jobs as critical and non-critical based on their completion times and uncertainties in a way that leads to provably good allocations. This classification can be further used to obtain intuition about the problem, thus providing managerial insights.