Title: A deconstruction-reconstruction metaheuristic and its application in graph coloring and job scheduling

Speaker: Nicolas Zufferey – Professeur titulaire, GSEM, Université de Genève, Switzerland

A new evolutionary population-based metaheuristic is proposed, based on the deconstruction-reconstruction paradigm. More precisely, at each generation, a solution s is selected from the population P of solutions and subjected to a tabu search strategic oscillation step consisting of deconstruction, reconstruction and improvement, after which the resulting solution replaces a solution of P. The adaptation of this algorithm is discussed for the well-known graph coloring problem, as well as one of its job-scheduling extensions.

Let G = (V, E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (i.e., a integer number chosen in [1, k]) to each vertex of V so that no edge of E has both endpoints with the same color. The graph coloring problem (GCP) consists in finding the smallest k for which a k-coloring exists. GCP can be viewed as a job scheduling problem on parallel machines, where all the jobs have the same duration, with the aim of minimizing the makespan. In the studied extension of the GCP, jobs of different durations are considered, as well as a different objective function.

---

Free entrance.
Welcome to everyone!