New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Multi-Objective Scheduling: An Agent-based Approach

SpeakerJoachim Lepping

We apply naturally inspired parallel model for multi-objective optimization to a single machine scheduling problem. Exemplarily, we optimize sequences of 50 jobs for an instance of the bi-criteria scheduling problem 1|d_j|sum{C_j},L_{max} with this approach. The modular building block architecture of the optimization model and the distribution of acting entities enables the analysis of separated problem knowledge and the design of corresponding variation operators. The actual modules are derived from local heuristics that tackle fractions of the complete problem. We unveil that it is possible to cover different areas of the Pareto-front with special property operators and make evident that the whole front can be covered if those operators are applied simultaneously. Further, we extend this concept to more important multi-objective scheduling problems like e.g. MaxAndSum that include also parallel machines.