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

В работе рассмотрена задача построения расписаний выполнения параллельных вычислительных задач на группах кластеров с одинаковым числом $w$ одинаковых процессоров, производительность которых для разных кластеров различная. Проведён вероятностный анализ задачи. Получены нижние оценки. Показано, что если число процессоров, необходимых для решения любой задачи имеет равномерное распределение на отрезке $[o,w]$ для любого алгоритма составления расписаний величина математического ожидания свободного объёма вычислений равна $\Omega(w\sqrt N)$. Получены верхние оценки. Был предложен онлайновый алгоритм построения расписаний с распределением задач в ограниченные области Limited Hash Scheduling для задачи построения расписаний, работающий в режиме closed-end, с математическим ожиданием свободного объёма вычислений, равным $O(w\sqrt{N ln N})$.