CALENDRIER

décembre 2017
L M M J V S D
        01 02 03
04 05 06 07 08 09 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

Partager cet événement

Enregistrer cet événement

Séminaire : A deconstruction-reconstruction metaheuristic and its application in graph coloring and job scheduling

Date
Lundi 26 juin 2017
Débute à 10:30

Prix
gratuit

Contact
Marilyne Lavoie
Site Web

Lieu
4488
2920, chemin de la Tour
Montréal, QC Canada
H3T 1N8

514 343-6111
Site Web | Itinéraire et carte

Catégories


Consulté 6256 fois
Séminaire : A deconstruction-reconstruction metaheuristic and its application in graph coloring and job scheduling

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

Conférencier : Nicolas Zufferey – Professeur titulaire, GSEM, Université de Genève, Suisse

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.

---

Entrée gratuite.
Bienvenue à tous!

© École Polytechnique de Montréal
Bottin | Plan du site | Recherche | Conditions | Besoin d'aide?