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

Задача распределения работ в системе с $m$ идентичными параллельными процессорами, при котором минимизируется загруженность максимально загруженного процессора, является NP-трудной проблемой. Для этой задачи разработано много приближенных алгоритмов, но для версии этой задачи, в которой работы поступают и распределяются в реальном времени, нельзя разработать приближенный алгоритм, гарантированная оценка которого меньше $1+1/\sqrt2$ при $m\geq4$ и стремится к $1{,}837$ при $m\to\infty$. В статье исследуется версия задачи, в которой работы поступают одна за другой и решение о их распределении принимается в реальном времени при дополнительном условии, что суммарная длительность работ известна. Для такой версии задачи предлагается алгоритм с гарантированной оценкой, равной 5/3.