Modélisation et résolution de problèmes complexes
dans les domaines de la météorologie et de la confection d'horaires

FREDERIC AVIOLAT
Ecole Polytechnique Fédérale de Lausanne
Département de Mathématiques
CH - 1015 Lausanne

The first part of this thesis is concerned with a problem of recognition of sky condition. In order to automate this process, we use an artificial neural network model. We describe the model that we have developed and how it fits into a larger meteorological message generation system designed by the Swiss Meteorological Institute. Artificial neural network models are particularly suited to solve classification and recognition problems. Their apparent ease of use has given them great success in recent years. However, in order to fulfill their task, they require a good knowledge of their features and limitations and they involve other elements, such as a well-designed preprocessing.

In the second part, we deal with two problems of school timetabling: the EPFL course timetable and the EPFL examination timetable. Those are complex combinatorial problems that no existing general software tool is able to solve, as the particular constraints met with in every school cannot be all taken into account by an existing model. We propose new resolution models that include a large number of constraints. Although they have been developed for a specific school, they are general enough to be adapted to other colleges and universities. To build our model, we split both timetabling problems into simpler subproblems. The solution methods that we have retained are principally based on tabu search heuristics.

The examination timetable problem is manifold: it concerns both oral and written exams, which must be tackled in two different ways. Moreover, some data are not available until the timetable is published. Estimates of the missing data provides a basis to build up a set of virtual data. The model uses this set to construct the timetable. A theoretical result we have attained shows that, once the real data are gathered, they can be easily related to the virtual set.

Finally, we present the complete software programs that we have developed. They include automatic and manual timetable construction tools. In order to be effective, a timetable must be easily adaptable. It is then essential to allow space for human intervention. The combination of both automatic and manual elements provides great flexibility and control tools to develop a high-quality timetable. For the first time, a software offers a set of efficient tools that can be used in more that one school.

For further information, please contact Professor Alain Hertz (hertz@dma.epfl.ch)