Coauthor: Joachim Lepping

Considering multiple criteria in scheduling usually leads to NP-hard problems when we strive for the Pareto set, i.e., the set of optimal compromise solutions regarding all criteria. Although NP-hardness itself is common in the domain of scheduling, we have a lot of good order-based rules (e.g., EDD, SPT, LPT, or more complex priority rules). Further, there exist theoretical insights into the problem structure that allows us to design algorithms to heuristically solve NP-hard single-criterion scheduling problems. In contrast, approaches to multi-criteria scheduling problems hardly ever benefit from the existing single-criterion findings. It is usually unknown how to combine the single-criterion knowledge to produce optimal compromises. In practical application, this leads to either simplification of the original problem or to a complex and very specific adaptation of a generic algorithm. However, both ways do not fulfill the user requirements for completeness of results and ease of use. In this talk, we motivate the integration of available knowledge or expertise as a major challenge in bridging the gap between single-criterion scheduling theory and its application in multi-criteria scheduling. We highlight this gap discussing the issues of standard approaches (e.g., epsilon constraint, zenith point method) and generic methods from evolutionary computation. As a solution to these issues, we propose an agent-based approach inspired by evolutionary computation that may lead to a rather flexible framework for integrating single-criteria expertise in a generic multi-criteria solution strategy. Finally, we present some promising results that emphasize the potential of this approach in practice and show perspectives for further efforts.