Heuristic task assignment algorithms applied to multisensor-multitarget tracking
Robert L. Popp, Krishna Rao Pattipati, Richard R. Gassner · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1996
In this paper, we are concerned with the problem of assigning track tasks, with uncertain processing costs and negligible communication costs, across a set of homogeneous processors within a distributed computing system to minimize workload imbalances. Since the task processing cost is uncertain at the time of task assignment, we propose several fast heuristic solutions that are extensible, incur very little overhead, and typically react well to changes in the state of the workload. The primary differences between the task assignment algorithms proposed are: (i) the definition of a task assignment cost as a function of past, present, and predicted workload distribution, (ii) whether or not information sharing concerning the state of the workload occurs among processors, and (iii) if workload state information is shared, the reactiveness of the algorithm to such information (i.e., high-pass, moderate, low-pass information filtering). We show, in the context of a multisensor-multitarget tracking problem, that using the heuristic task assignment algorithms proposed can yield excellent results and offer great promise in practice.