Построение оптимальных расписаний для обслуживающих систем с множеством серверов

Рассматривается задача оптимального обслуживания множества требований на множестве идентичных параллельных приборов. Перед выполнением необходима загрузка, которая осуществляется сервером. Причем задано множество одинаковых серверов, каждый из которых годится для выполнения загрузки. Рассматриваются вопросы вычислительной сложности данной задачи при условии, что необходимо минимизировать время завершения обслуживания всех требований. Для случая с одинаковыми длительностями обслуживания и одинаковыми длительностями загрузки предлагается полиномиальный алгоритм. Для задачи с единичными временами загрузки при условии, что количество приборов на единицу превосходит количество серверов, предлагается псевдополиномиальный алгоритм. Доказывается $NP$-трудность в сильном смысле для задачи с фиксированным числом приборов и серверов при условии минимизации максимальной задержки. Обобщаются некоторые известные алгоритмы с фиксированными временами обслуживания на соответствующие задачи с сервером при фиксированных временах загрузки. Кроме того, сделана оценка эффективности для двух списочных алгоритмов при условии минимизации общего времени обслуживания.

Статья представлена к публикации членом редколлегии: А. А. Лазарев