Минимизация стоимости, связанной с переменными директивными сроками, в задаче теории расписаний с одним прибором

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