Metaheuristics for solving scheduling problems
A half-day tutorial at ICAPS '06
angelo.oddi@istc.cnr.it
Goal and content: despite much progress has been made in finding exact and
provably optimal solutions to scheduling problems, many hard scheduling
problems are still not solved exactly and require heuristic methods. In
addition, reaching optimal solutions is in some cases meaningless, as in
practice we are often dealing with models that are rough simplifications of
the working domain.
This tutorial introduces methods for solving scheduling problems that combine
heuristic search and constraint reasoning. Specifically, its goal is to
explain how heuristic search, in combination with constraint reasoning
techniques, has emerged as a robust methodology to quickly produce
good-quality solutions for a variety of scheduling problems. The focus is
first put on greedy algorithms based on temporal flexibility heuristics and to
local search approaches to scheduling optimization, including neighborhood
structures and heuristics for improving search efficiency. Secondly, some
metaheuristics will be described, i.e., high level procedures that coordinate
and combine simple heuristics to find solutions that are of better quality
than those found by the simple heuristics alone.
The tutorial is targeted to researchers and practitioners that would like to
use metaheuristic techniques for solving scheduling problems. No prior
knowledge on metaheuristics or constraint reasoning is required.