Improved scheduling of generalized pinwheel task systems

The generalized pinwheel scheduling problem is defined as follows: Given a multiset {(a₁, b₁), (a₂, b₂), ..., (a_n, b_n)} of ordered pairs of positive integers, determine whether there is an infinite sequence over the symbols {1, 2, 3, ..., n} such that, for each i, 1≤i≤n, any subsequence of b_i consecutive symbols contains at least a_i i's. Such an infinite sequence is called a schedule for the generalized pinwheel task system {(a₁, b₁), (a₂, b₂), ..., (a_n, b_n)}. When all the a_i's are equal to one, this problem has been previously studied as the pinwheel scheduling problem. A linear-time algorithm is presented for solving such instances which determines whether such an instance has a schedule. A fast on-line scheduler (FOLS) is also derived, which can actually generate the schedule in O(log n) time per slot given O(n) preprocessing time. When compared to traditional pinwheel scheduling algorithms, this new algorithm has a higher density threshold on a very large subclass of generalized pinwheel task systems.