An Introduction to Multiobjective Metaheuristics for Scheduling and Timetabling

In many real-world scheduling problems (eg. machine scheduling, educational timetabling, personnel scheduling, etc.) several criteria must be considered simultaneously when evaluating the quality of the solution or schedule. Among these criteria there are: length of the schedule, utilisation of resources, satisfaction of people’s preferences and compliance with regulations. Traditionally, these problems have been tackled as single-objective optimization problems after combining the multiple criteria into a single scalar value. A number of multiobjective metaheuristics have been proposed in recent years to obtain sets of compromise solutions for multiobjective optimization problems in a single run and without the need to convert the problem to a single-objective one. Most of these techniques have been successfully tested in both benchmark and real-world multiobjective problems. However, the number of reported applications of these techniques to scheduling problems is still relatively scarce. This paper presents an introduction to the application of multiobjective metaheuristics to some multicriteria scheduling problems.