Алгоритм составления расписания для одного процессора с гарантированной оценкой точности $3/2$

Рассматривается задача составления расписания для одного процессора $1|r_i,q_i|C_{\max}$, в которой для каждого задания известны времена поступления, времена выполнения и времена доставки. Предлагается новый приближенный алгоритм решения задачи $1|r_i,q_i|C_{\max}$ с гарантированной оценкой точности $3/2$ и вычислительной сложностью $O(n\log n)$. Приводятся пример, показывающий, что данная оценка асимптотически достигается, и результаты вычислительного эксперимента, свидетельствующие о быстродействии и практической точности алгоритма.