Optimum allocation of processes in a distributed environment: A process- to-process approach. (English) Zbl 0707.90033

Summary: The process allocation problem (PAP) concerned with the assignment of a number of communicating processes to a certain number (not known a priori) of identical processors in a telecommunications environment is examined. The objective is to minimize the total message-passing between processes residing on different processors subject to constraints on the processing power and storage capacity (code-, data-storage and occupancy) of the processors. Constraints imposed on the co-location of certain processes on the same processor are also included. The problem is formulated as a 0-1 linear maximization problem, taking into account only the number of processes involved, while the number of processors required is produced automatically with the optimum solution. An implicit enumeration algorithm is developed which produces an optimum message- passing allocation. Computational results of a set of random problems which have similar characteristics to a real-world application in telecommunications are also presented.


90B18 Communication networks in operations research
68M10 Network design and communication in computer systems
90C09 Boolean programming
90C90 Applications of mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C05 Linear programming
65K05 Numerical mathematical programming methods
Full Text: DOI