О стохастической задаче компактного суммирования векторов

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