Subject: ECAI-98 Tutorial on Local Search Techniques for Scheduling Problems

From: Andrea Schaerf <[email-masked]>
Date: Mon, 20 Jul 1998 17:01:10 +0200

I hope this tutorial can be of interest for people in these mailing
lists
---------------------------------------------------------------------
           
                       ECAI-98 TUTORIAL
             Brighton (UK), August 24th 1998, AM

TITLE: Local Search Techniques for Scheduling Problems

INSTRUCTOR: Andrea Schaerf

HOMEPAGE: http://www.cogs.susx.ac.uk/ecai98/tw/T3.html

ABSTRACT: 

Local search is an emerging paradigm for combinatorial search, which has
been recently shown to be very effective for a large number of
scheduling problems. It is based on the simple idea of navigating the
search space by iteratively stepping from one solution to one of its
neighbours. The neighbourhood of a solution is composed of the solutions
that can be obtained by applying an atomic local change to it. 

In this tutorial, we survey the basic local search techniques proposed
in the literature and implemented in many industrial scheduling systems:
simulated annealing, tabu search, and various forms of hill climbing. We
also illustrate some of the most promising improvements and variations
of such basic techniques which are currently investigated. Next, we
discuss the simultaneous exploitation of many neighbourhood relations
and the interleaving of different local search techniques. Finally, we
propose the combination of local search with other solution paradigms,
such as genetic algorithms and backtracking
search. 

Throughout the tutorial we illustrate three case studies of successful
applications of these techniques to real life problems: frequency
assignment in mobile radio systems, school timetabling, and workforce
scheduling. 

--
Andrea Schaerf                      http://www.dis.uniroma1.it/~aschaerf
Dip. di Informatica e Sistemistica  email: [email-masked]
Universita` di Roma "La Sapienza"   tel: +39-6-49918485
via Salaria 113, 00198 Roma, ITALY  fax: +39-6-85300849