Skip to Main content Skip to Navigation
Book sections

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.
Complete list of metadata
Contributor : Grégory Mounié Connect in order to contact the contributor
Submitted on : Friday, December 20, 2013 - 11:50:00 AM
Last modification on : Tuesday, August 2, 2022 - 4:24:38 AM


  • HAL Id : hal-00921362, version 1


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⟩



Record views