A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule (Q633540)

In this paper cyclic scheduling problems without resource constraints are studied. Given is a set of tasks \(i=1,\ldots,n\) with processing times \(p_i>0\) which have to be processed infinitely often. The tasks are restricted by so-called uniform precedence relations \((i,j)\) with two integer parameters: a value \(V_{ij}\) and a height \(H_{ij}\). Respecting these relations means that \(t(i,k)+V_{ij} \leq t(j,k+H_{ij})\) must hold for all \(k\), where \(t(i,k)\) denotes the starting time of the \(k\)-th execution of task \(i\). After introducing the problem a necessary condition for the existence of a periodic schedule is given, which is not sufficient in general. Afterwards, the earliest start schedule is studied in more detail. It is shown that the minimum average cycle time is equal for the earliest start schedule and an optimal periodic schedule. Finally, an algorithm based on linear programming is presented which checks the existence of a schedule and computes the minimum average cycle time.