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.