Multi-criteria scheduling: an agent-based approach for expert knowledge integration

Authored by Christian Grimme, Joachim Lepping, Uwe Schwiegelshohn

Date Published: 2013-08

DOI: 10.1007/s10951-011-0256-7

Sponsors: No sponsors listed

Platforms: No platforms listed

Model Documentation: Other Narrative

Model Code URLs: Model code not found

Abstract

In this work, we present an agent-based approach to multi-criteria combinatorial optimization. It allows to flexibly combine elementary heuristics that may be optimal for corresponding single-criterion problems. We optimize an instance of the scheduling problem 1|d (j) |aC (j) ,L (max) and show that the modular building block architecture of our optimization model and the distribution of acting entities enables the easy integration of problem specific expert knowledge. We present a universal mutation operator for combinatorial problem encodings that allows to construct certain solution strategies, such as advantageous sorting or known optimal sequencing procedures. In this way, it becomes possible to derive more complex heuristics from atomic local heuristics that are known to solve fractions of the complete problem. We show that we can approximate both single-criterion problems such as P (m) |d (j) |aU (j) as well as more challenging multi-criteria scheduling problems, like P (m) ||C (max),aC (j) and P (m) |d (j) |C (max),aC (j) ,aU (j) . The latter problems are evaluated with extensive simulations comparing the standard multi-criteria evolutionary algorithm NSGA-2 and the new agent-based model.u

Tags

Evolutionary multi-criteria optimization Multi-criteria scheduling Parallel machine scheduling Predator-prey model