Problem of Calculations Optimization in the Network Structure
DOI:
https://doi.org/10.14529/ctcr160201Keywords:
network structures, problem vertices, problem of drawing up schedules, local optimizationAbstract
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.
References
Buyya, R. Economy driven resource management architecture for computational power grids / R. Buyya, D. Abramson, J. Giddy // PDPTA ’00: International Conference on Parallel and Distributed Processing Techniques and Applications, 2000.
Сигал, И.Х. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: учеб. пособие / И.Х. Сигал, А.П. Иванова. – 2-е изд. испр. и доп. – М.: Физматлит, 2007. – 304 с.
