Диспетчеризация в системе с параллельным обслуживанием с помощью распределенного градиентного управления марковской цепью

Рассматривается система распределения заданий, состоящая из диспетчера и нескольких параллельно работающих однопроцессорных серверов, каждый из которых имеет очередь неограниченной емкости. Задания без внутренней структуры поступают в систему по рекуррентному потоку и имеют случайный размер. В момент поступления очередное задание в соответствии с некоторой стратегией направляется диспетчером, имеющим полную информацию о текущем состоянии системы, в один из серверов. Задания обслуживаются из очереди по одному в соответствии с дисциплиной FIFO (first in, first out), после чего навсегда покидают систему. Скорости процессоров фиксированы и, вообще говоря, различны. Ставится задача нахождения стратегии, минимизирующей стационарное среднее время пребывания задания в системе. Излагается способ решения подобного класса задач, основанный на использовании метода Монте-Карло в сочетании с оригинальным адаптивным алгоритмом управления марковскими цепями с континуальным множеством состояний. Его главная составляющая — динамическая дискретизация множества состояний и использование в каждой ячейке разбиения «локального» квазиградиентного алгоритма. На простых численных примерах показано, что построенная диспетчеризация успешно конкурирует с лучшими из известных решений, а сам метод рассчитан на более широкую область применения.