Задача оптимизации вычислений в сетевых структурах

Аннотация

Рассматривается вычислительная сеть из n вершин (это вершины, в которых решаются те или иные задачи), m входных вершин и m выходных вершин (m – число решаемых задач). Каждой задаче соответствует путь в сети с входом H и выходом K, соответствующий некоторому алгоритму решения задачи. Одновременно в каждом узле может решаться только одна задача. Поэтому может возникнуть конфликтная ситуация, когда в момент прихода в вершину некоторой задачи эта вершина занята решением другой задачи. Узлы, в которых могут решаться несколько задач, будем называть проблемными. Рассматриваются задачи составления расписания выполнения задач по критериям минимизации времени решения всех задач и минимизации максимального отклонения от требуемых времен решения. Для их решения предложены методы локальной оптимизации, ветвлений, ветвей и границ.