Problem of Calculations Optimization in the Network Structure

Abstract

A computer network consisting of n vertices (vertices, which solved some problems), m input vertices and m output vertices (m is the number of tasks) is considered. Each task matches to way in the network with input H and output K, corresponding to some algorithm of problem solving. At the same time only one task can be solved in each vertex. Therefore, it may be a conflict in the moment of arrival to the vertex of a task if this vertex is busy with another task. The vertices in which several tasks may be solved at the same time, will be called problem vertices. The problems of tasks scheduling according to criteria of minimizing the time required to solve all the problems or minimize the maximum deviation from the required solution time are examined. Methods of local optimization, branch, branch and bound are proposed for their solution.