Periodic assignment and graph colouring (Q1329789)

This paper deals with the problem of assigning periodic operations to a minimum number of identical processors under different constraints. The periodic assignment problem naturally arises in such diverse areas as real-time processing, vehicle scheduling and compiler design. The authors consider two different models of scheduling: (1) unconstrained periodic assignment, where different executions of an operation may be assigned to different processors, and (2) constrained periodic assignment, where all executions of an operation have to be assigned to the same processor. They show that the latter case leads to an NP-hard problem of coloring circular-arc graphs and periodic-interval graphs. These two classes of graphs include interval graphs. The authors then prove that two heuristics for coloring circular-arc graphs require less than twice the minimum number of colors. Surprisingly, each general graph is a periodic-interval graph, so no such polynomial algorithm for periodic-interval graph is likely to exist.