Задача о двух периодических работах

Исследуются условия существования допустимого расписания с прерываниями на одном процессоре для системы из двух работ $(p_1,d_1,c_1)$ и $(p_2,d_2,c_2)$, в которой каждая из работ $i\in\{1,2\}$ становится готовой к $k$-му исполнению в момент $(k-1)p_i$, должна завершиться до $d_i+(k-1)p_i$ и требует для своего исполнения $c_i$- единиц процессорного времени. Предложено два метода проверки существования допустимого расписания, в том числе полиномиальный от числа двоичных разрядов, необходимых для кодирования входных данных, алгоритм типа алгоритма Евклида.