Scheduling high-level tasks among cooperative agents

Abstract

Scheduling tasks among cooperative agents requires tradeoffs between various factors including task priorities and context-dependent execution times. We have specifically been investigating the space of functions for evaluating alternative distributed task schedules for multi-operator applications. In this paper, we describe some candidate functions and converge on intuitively appealing functions, which we show to lead to equivalent preferences over distributed schedules. We then look at the computational complexity of finding schedules that (approximately) optimize this function. When context switching costs are thrown into the mix moreover, the complexity becomes even more daunting. To address these problems, this paper summarizes our work on forging correspondences between our problems and those studied in operations research. Moreover, we have developed a new hill-climbing strategy for solving these problems, and we show that it performs well within the range of parameter settings that are representative of our application domain.