Abstract:
We study existence conditions for an admissible schedule with interruptions on one processor for a system of two tasks $(p_1,d_1,c_1)$ and $(p_2,d_2,c_2)$, in which each of the tasks $i\in\{1,2\}$ becomes ready for the $k$th execution at time $(k-1)p_i$, must be completed before $d_i+(k-1)p_i$ and requires for its execution $c_i$ units of processor time. We present two methods for testing the existence of an admissible schedule, including a polynomial method for the number of binary digits necessary for coding input data, and an algorithm of Euclidean type.
Fulltext:
PDF file (766 kB)