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

Рассматривается традиционная система распределения заданий, состоящая из диспетчера, нескольких параллельно работающих однопроцессорных узлов, каждый из которых имеет FIFO очередь неограниченной ёмкости. Задания поступают в систему по рекуррентному потоку и имеют случайный размер c известной плотностью распределения. В момент поступления очередное задание в соответствии с некоторой стратегией направляется в один из узлов и после окончания обслуживания навсегда покидает систему. Скорости процессоров различны и фиксированы. Ставится задача нахождения стратегии, минимизирующей среднее время пребывания заявки в системе.

Optimal dispatching of arbitrarily-sized tasks in heterogeneous systems with parallel service on single-processor machines

Consideration is given to a classical distributed processing system with one dispatcher, arbitrary number of infinite capacity FIFO queues, each served by a single processor. Processors' speeds in the queues are different and known to the dispatcher. Tasks' inter-arrival times are i.i.d. with a given arbitrary distribution; tasks' sizes are also i.i.d. with a given probability density and do not depend on inter-arrival times. When a task arrives at the system the dispatcher, based on current values of queues' backlogs and task's size, immediately routes it to one of the queues. Having received service in a queue a task quits the system. Optimal dispatching policy minimizing social mean response time is being investigated.