Back to activities
GERAD seminar

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

iCalendar

Jun 26, 2017   10:30 AM — 11:30 AM

Nicolas Zufferey Full Professor, GSEM, University of Geneva, 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!

Location

Room 4488
André-Aisenstadt Building
Université de Montréal Campus
2920, chemin de la Tour Montréal QC H3T 1J4 Canada

Research Axis

Research application