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

Рассматривается задача теории расписаний, в которой необходимо минимизировать суммарное взвешенное запаздывание на одном приборе с равными продолжительностями обслуживания требований и неодновременным поступлением требований на обслуживание. Эта задача упомянута как минимальная, статус вычислительной сложности которой не-известен: http://www2.informatik.uni-osnabrueck.de/knust/class/dateien/classes/ein_ma/ein_ma. Последние результаты по данной задаче опубликованы в 2000 и 2005 гг., а именно, алгоритмы решения частных случаев задачи. В данной статье представлены некоторые свойства задачи и пути дальнейших исследований.