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

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

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〉

Partager

Métriques

Consultations de la notice

168