Fixed Cycle Scheduling: A Solvable Problem with Empty Precedence Structure

Fixed Cycle Scheduling (FCS) is a class of job scheduling problems in which all scheduling decisions (assignment of tasks to processors) are made on a cycle. That is, if task t is assigned to processor j at period h < n, then the same assignment is made at period h + in, for all integers i, where n is the cycle length. Possible applications of FCSs are given and a special case with uniform job arrivals and empty precedence structure is shown to be solvable analytically.