Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Solving Scheduling Problems by Evolutionary Algorithms for Graph Coloring Problem
verfasst von : Pawel B. Myszkowski
Erschienen in: Metaheuristics for Scheduling in Industrial and Manufacturing Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This chapter presents a new evolutionary approach to the Graph Coloring Problem (GCP) as a generalization of some scheduling problems: timetabling, scheduling, multiprocessor scheduling task and other assignment problems. The proposed evolutionary approach to the Graph Coloring Problem utilizes information about the conflict localization in a given coloring. In this context a partial fitness function (
pff
) and its usage to specialize genetic operators (IBIS and BCX) and phenotypic measure of diversity in population are described. The particular attention is given to the practical usage of GCP. The performance of the proposed algorithm is verified by computer experiments on the set of benchmark graphs instances (DIMACS). Additional experiments were done on benchmark graph for timetabling problem.