Минимизация взвешенной суммы запаздывающих требований при обслуживании одним прибором

Рассматривается задача, которая является обобщением известной задачи теории расписаний на случай, когда обслуживаются не единичные требования, а их партии. Показывается ее NP-трудность, и предлагаются псевдополиномиальный и быстрый $\varepsilon$-приближенный алгоритмы решения. Для частных случаев описываются полиномиальные алгоритмы.