Task allocation in a distributed system and Lagrangean duality

This paper addresses the problem of allocating the tasks of a distributed program to the heterogeneous processors of a distributed system. The processors are linked by a completely meshed network and their capacities are limited. The purpose is to make the best uses of resources in the considered distributed system, i.e., for a given program to minimize the sum of processing and communication costs. After formulating the problem as the minimization of a quadratic pseudoboolean function subject to linear constraints, the authors thoroughly study the Langrangean dual of this mathematical programming problem in order to obtain relevant information about the primal lower bound that can be obtained in this way.