On the Integration of Theoretical Single-Objective Scheduling Results for Multi-objective Problems

Christian Grimme 1 Markus Kemmerling 2 Joachim Lepping 3
1 TU - Technische Universität Dortmund [Dortmund]
2 Dortmund University of Technology
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : We present a modular and flexible algorithmic framework to enable a fusion of scheduling theory and evolutionary multi-objective combinatorial optimization. For single-objective scheduling problems, that is the optimization of task assignments to sparse resources over time, a variety of optimal algorithms or heuristic rules are available. However, in the multi-objective domain it is often impossible to provide specific and theoretically well founded algorithmic solutions. In that situation, multi-objective evolutionary algorithms are commonly used. Although several standard heuristics from this domain exist, most of them hardly allow the integration of available single-objective problem knowledge without complex redesign of the algorithms structure itself. The redesign and tuned application of common evolutionary multi-objective optimizers is far beyond the scope of scheduling research. We therefore describe a framework based on a cellular and agent-based approach which allows the straightforward construction ofmulti-objective optimizers by compositing single-objective scheduling heuristics. In a case study, we address strongly NP-hard parallel machine scheduling problems and compose optimizers combining the known single-objective results. We eventually show that this approach can bridge between scheduling theory and evolutionary multi-objective search.
Type de document :
Chapitre d'ouvrage
Tantar, Emilia and Tantar, Alexandru-Adrian and Bouvry, Pascal and Del Moral, Pierre and Legrand, Pierrick and Coello Coello, Carlos A. and Schütze Oliver. EVOLVE - A bridge between probability, set oriented numerics and evolutionary computation, 447, Springer Berlin Heidelberg, pp.333-363, 2013, Studies in Computational Intelligence
Liste complète des métadonnées
https://hal.inria.fr/hal-00921362
Contributeur : Grégory Mounié <>
Soumis le : vendredi 20 décembre 2013 - 11:50:00
Dernière modification le : jeudi 11 octobre 2018 - 08:48:03

Identifiants

  • HAL Id : hal-00921362, version 1

Collections

INRIA | UGA | LIG_SRCPR_MOAIS | LIG_SRCPR | LIG

Citation

Christian Grimme, Markus Kemmerling, Joachim Lepping. On the Integration of Theoretical Single-Objective Scheduling Results for Multi-objective Problems. Tantar, Emilia and Tantar, Alexandru-Adrian and Bouvry, Pascal and Del Moral, Pierre and Legrand, Pierrick and Coello Coello, Carlos A. and Schütze Oliver. EVOLVE - A bridge between probability, set oriented numerics and evolutionary computation, 447, Springer Berlin Heidelberg, pp.333-363, 2013, Studies in Computational Intelligence. 〈hal-00921362〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

168

Contact


archive-ouverte@inria.fr