The following paper provides an insight into application of the contemporary heuristic methods to graph coloring problem. Variety of algorithmic solutions for the Graph Coloring Problem (GCP) are discussed and recommendations for their implementation provided. The GCP is the NP-hard problem, aiming at finding the minimum number of colors for vertices in such a way that none of two adjacent vertices are marked with the same color. With the advent of modern processing units metaheuristic approaches to solve GCP were extended to discrete optimization here. To explain the phenomenon of these methods, a thorough survey of AI-based algorithms for GCP is provided, with the main differences between specific techniques pointed out.

The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|pj  = 1, G = bisubquartic|Cmax. The second one is Algorithm 3 which is 4-approximate for the problem Qm|pj  = 1, G = bisubquartic|ΣCj, where m ∈ {2, 3, 4}. The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.