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.