PERIODIC ASSIGNMENT AND GRAPH-COLORING

We analyse the problem of executing periodic operations on a minimum n umber of identical processors under different constraints. The analysi s is based on a reformulation of the problem in terms of graph colouri ng. It is shown that different constraints result in colouring problem s defined on different classes of graphs, viz. interval graphs, circul ar-arc graphs and periodic-interval graphs. We discuss the complexity of these colouring problems in detail.