Scheduling algorithms are infiltrating all aspects of life, as I recently found out when trying to order a dishwasher to be delivered on a particular date. (The retailer’s vehicle scheduling and route planning algorithm said no.) The research community is also tackling more challenging problems, problems that have more practical applications.

The authors of this paper “consider the problem of finding a [cyclic] schedule with a minimal period.” Each task needing scheduling requires one or more resources. Resources are heterogeneous, and there can be more than one resource of each type. Tasks will not require more than one resource of any type and precedence delays exist.

The main contribution by the authors is to extend the decomposed software pipelining approach of Gasperoni and Schwiegelshohn [1] to deal with the unitary resource constrained modulo scheduling problem (introduced by Dupont de Dinechin et al. [2]) with the addition of arbitrary “non-negative start to start precedence delays.”

A brief problem formulation is followed by an example of a “for” loop written in the C programming language that has been complied into an assembler. The assembler instructions are then scheduled based on which central processing unit (CPU) resources they require and their precedence requirements. Although not the key focus of this paper, I was very pleasantly surprised to see that the optimal periodic schedule was achieved. The bulk of the paper then covers the worst-case analysis with three theorems, one corollary, and five lemmas, so it is not the easiest read.