 |
Equitable coloring and Scheduling on identical machines
In this work we are interested in the complexity of the equitable coloring of the bipartite graph in which we prove that the problem of 2-equitable coloring of union of complete bipartite graphs and the 3-equitable coloring of a connected bipartite graph are NP-complete.
It also discusses the scheduling of conflicting jobs (that cannot be executed on the same machine) on identical machines while evenly distributing the load between them. The paper presents some complexities of subproblems and describes and evaluates a branch and bound algorithm, a Mixed Integer Programming formulations (that can solve some instances with 100 jobs) and six proposed heuristics where their good performance is shown in computational experiments. Such problem with identical processing times can be viewed as r-equitable k-coloring.
