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

Sofianopoulou, Stella

J. Oper. Res. Soc. 41, No. 4, 329-337 (1990).

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.

MSC:

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

Keywords:

process allocation problem; telecommunications; implicit enumeration algorithm; optimum message-passing allocation