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.