scheduling

[Evan W. Steeg]

>Does anyone have references to work on using connectionist techniques for
>solving scheduling problems - particularly timetabling?
>
>     David Pickles.


  The following was announced a while ago:
    ----------------------------------------------

                                                 October 1989

                                                 LU TP 89-19


      "TEACHERS AND CLASSES" WITH NEURAL NETWORKS


     Lars Gislen, Carsten Peterson and Bo Soderberg

  Department of Theoretical Physics, University of Lund
       Solvegatan 14A, S-22362 Lund, Sweden

   Submitted to International Journal of Neural Systems


Abstract:

A convenient mapping and an efficient algorithm for solving
scheduling problems within the neural network paradigm is
presented. It is based on a reduced encoding scheme and a
mean field annealing prescription, which was recently
successfully applied to TSP.

Most scheduling problems are characterized by a set of hard
and soft constraints. The prime target of this work is the
hard constraints. In this domain the algorithm persistently finds
legal solutions for quite difficult problems. We also make some
exploratory investigations by adding soft constraints with very
encouraging results. Our numerical studies cover problem sizes
up to O(5*10^4) degrees of freedom with no parameter sensitivity.

We stress the importance of adding certain extra terms to
the energy functions which are redundant from the encoding
point of view but beneficial when it comes to ignoring local
minima and to stabilizing the good solutions in the annealing
process.

For copies of this report send requests to: THEPCAP at SELDC52.
NOTICE: Those of you who requested our previous report, "A New
Way of Mapping Optimization.... (LU TP 89-1), will automatically
receive this one so no request is necessary.

-------------------------------------------------------

  -- Evan

Evan W. Steeg (416) 978-7321      steeg at ai.toronto.edu (CSnet,UUCP,Bitnet)
Dept of Computer Science          steeg at ai.utoronto    (other Bitnet)
University of Toronto,            steeg at ai.toronto.cdn (EAN X.400)
Toronto, Canada M5S 1A4           {seismo,watmath}!ai.toronto.edu!steeg