An efficient algorithm for a task allocation problem

Abstract

This paper presents an efficient algorithm to solve one of the task allocation problems. Task assignment in an heterogeneous multiple processors system is investigated. The cost function is formulated in order to measure the intertask communication and processing costs in an uncapacited network. A formulation of the problem in terms of the minimization of a submodular quadratic pseudo-Boolean function with assignment constraints is then presented. The use of a branch-and-bound algorithm using a Lagrangean relaxation of these constraints is proposed. The lower bound is the value of an approximate solution to the Lagrangean dual problem. A zero-duality gap, that is, a saddle point, is characterized by checking the consistency of a pseudo-Boolean equation. A solution is found for large-scale problems (e.g., 20 processors, 50 tasks, and 200 task communications or 10 processors, 100 tasks, and 300 task communications). Excellent experimental results were obtained which are due to the weak frequency of a duality gap and the efficient characterization of the zero-gap (for practical purposes, this is achieved in linear time). Moreover, from the saddle point, it is possible to derive the optimal task assignment.