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

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

Статья представлена к публикации членом редколлегии: П. Ю. Чеботарев