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

Рассматривается задача эффективного распределения единственного потока однородных заданий в “почти” ненаблюдаемых системах, состоящих из параллельно работающих серверов с очередями неограниченной емкости и одного диспетчера, немедленно распределяющего поступающие по одному задания по серверам. Эффективность понимается в смысле минимума стационарного среднего времени пребывания задания в системе. Для выбора сервера диспетчеру доступна лишь следующая информация: производительность серверов, распределение времени между поступлениями заданий, распределение их размеров, полная история совершенных действий и промежутки между ними. Динамическая информация о состоянии системы (как, например, длина очередей) диспетчеру неизвестна. Предполагается, что в серверах реализована дисциплина справедливого разделения процессора. Из классические диспетчеризаций для таких систем применимы лишь: случайный выбор и циклический выбор. В работе предлагается семейство новых стратегий, которые используют, помимо априорной информации о системе, оценки состояния серверов по результатам имеющихся наблюдений. На численных примерах показано, что, по сравнению с известными стратегиями, новые стратегии позволяют существенно уменьшить среднее время пребывания.

Minimizing mean response time in non-observable distributed processing systems with nodes, operating under egalitarian processor sharing policy

Consideration is given to the dispatching problem in an non-observable distributed processing system with M, M ≥ 2, single server queues operating in parallel, each under the processor sharing discipline. Jobs, having the same job size distribution, arrive one by one to the dispatcher, which immediately routes it to one of the queues. When making a routing decision the dispatcher does not have any online information about the system (like current queues’ sizes, size of the arriving job etc.). The only information available to the dispatcher is: job size distribution, job’s inter-arrival time distribution, server’s speeds, time instants of previously arrived jobs and previous routing decisions. Under these conditions, one is interested in the routing policies which minimize the job’s long-run mean response time. New class of dispatching policies is proposed which, according to the numerical experiments, may significantly outperform all classic dispatching policies available for such a system: (optimal) probabilistic policy and the round robin policy.