Многопроцессорные расписания и комбинаторные конфигурации

Показано, что несуществование некоторых расширителей с большим коэффициентом расширения влечет для достаточно больших $d$ и $p$ существование плотных $p$-процессорных расписаний (в которых все процессоры заняты выполнением существенных операций в каждый момент времени) для ациклических орграфов с максимальной степенью входа вершин $d$ и размером каждого яруса не менее
$$ \frac{pd(1+2\ln\ln d/\ln d)}{\ln d}. $$
Установлены связи между расширителями и $\lambda$-упаковками.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 93–01–00459.