Задача оптимизации вычислений в сетевых структурах
Автор: Бурков Владимир Николаевич, Ляпунцова Елена Вячеславовна, Шихалиев Руслан Сираджеддинович
Рубрика: Информатика и вычислительная техника
Статья в выпуске: 2 т.16, 2016 года.
Бесплатный доступ
Рассматривается вычислительная сеть из n вершин (это вершины, в которых решаются те или иные задачи), m входных вершин и m выходных вершин (m - число решаемых задач). Каждой задаче соответствует путь в сети с входом H и выходом K, соответствующий некоторому алгоритму решения задачи. Одновременно в каждом узле может решаться только одна задача. Поэтому может возникнуть конфликтная ситуация, когда в момент прихода в вершину некоторой задачи эта вершина занята решением другой задачи. Узлы, в которых могут решаться несколько задач, будем называть проблемными. Рассматриваются задачи составления расписания выполнения задач по критериям минимизации времени решения всех задач и минимизации максимального отклонения от требуемых времен решения. Для их решения предложены методы локальной оптимизации, ветвлений, ветвей и границ.
Сетевые структуры, проблемные узлы, задача составления расписаний, локальная оптимизация
Короткий адрес: https://sciup.org/147155114
IDR: 147155114 | УДК: 519.863 | DOI: 10.14529/ctcr160201
Problem of calculations optimization in the network structure
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.
Список литературы Задача оптимизации вычислений в сетевых структурах
- 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 с.
