Assignment and Prioritization of Tasks with Uncertain Durations for Satisfying Makespans in Decentralized Execution

Abstract

Task assignment under execution uncertainty and temporal/resource constraints is a standard problem for many organizations. Existing approaches in the AI planning & scheduling and operations research literature predominantly focus on dynamic controllability, and non-preemptive execution of tasks. Such solutions are appropriate for teams of agents under tight control requirements. However, in most organizations with human teams, once tasks have been assigned, humans tend to execute their assignments without a constant central oversight (which is needed for dynamic controllability). In this paper we define a problem in which execution of tasks is distributed (without central oversight), and assumes humans can preempt their tasks when other tasks of higher priority are ready to be worked on. We present two algorithms based on Tabu search and Monte Carlo Tree Search to assign and prioritize tasks for such problems. Experimental results show the improved efficacy of these approaches for this problem setting over non-preemptive strategies.