On Optimal Allocation in a Distributed Processing Environment

Distributed processing has been motivated by many objectives. Among these are a desire to share resources, reduce communications costs (as compared to a centralized processing scheme), increase performance and decrease response time by partitioning tasks and achieve higher system availability (fault tolerance). Typically, processes (tasks) within a single processor and across processors will communicate among themselves in such a distributed environment. It is desirable to be able to assign tasks to processors in some optimal manner. In this paper, a quadratic partitioning model is developed to represent this interaction of tasks in a distributed processing environment. Initially, no capacity constraints are considered at any processor. An optimal solution (in a probabilistic sense) is found for this uncapacitated problem using a probabilistic branch and bound technique. Capacity constraints for processors are then introduced. Three intuitively appealing heuristics are developed to obtain good, though not necessarily optimal, solutions to the capacitated problem.