Background: Resource allocation and scheduling in multiple domains use assignment problems which are free from conflict and therefore form the core of the problem class. The theory of graph coloring is a very useful combinatorial model for these types of constraint-satisfaction problem. The development of a more comprehensive theoretical and practical framework to integrate these two fields into a consistent study will require further research.
Objective: The objective of this paper is to show how graph coloring can be formulated as an independent framework. It demonstrates that there are a variety of problems (exam schedules, scheduling jobs on processors, allocating wireless frequencies, and allocating registers for compilers) that can be recast as vertex and edge coloring problems.
Methods: In this dissertation, we employ a chromatic decomposition method by using vertices to represent entities needing assignment and edges to define conflicts between entities on a conflict graph. We use feasible graph colourings to find a valid assignment of entities to available resources. The analysis of this research includes computing time performance analysis of various heuristics and metaheuristics, including use of a DSATUR heuristic, genetic algorithms and simulated annealing algorithms.
Results: The results show that chromatic number χ(G) establishes an exact lower bound for the minimum number of resources required and provides evidence that the overall graph coloring problem is NP-complete so exact solutions are computationally impractical when instance sizes are large. Comparison of heuristic and meta-heuristic methods demonstrated that near-optimal solutions can be produced in an efficient manner, thereby providing strong practical utility in several different disciplines.
Conclusion: Graph coloring provides an exact mathematical description (and computational extension) of several different types of assignments under one mathematical model. By abstracting these problems into one common form, different optimization strategies can be applied regardless of the application area, thus alleviating the need to create a specialised solution for each problem