Constraint logic programming for examination timetabling

TitreConstraint logic programming for examination timetabling
Type de publicationArticle de revue
Année de publication1996
Titre de la revueThe Journal of Logic Programming
Volume26
Pagination217 - 233
Langueeng
Auteur(s)Boizumault, P., Delon Y. et Péridy L.
Numéro ISSN0743-1066
Résumé

In this paper, we present an application of constraint logic programming to the examination timetabling problem of our university. Each year, in June, 4000 students in various programs must attend examinations during a couple of weeks for academic reasons. A set of examinations must be planned on specific half-days over a collection of rooms of different capacities. Various kinds of constraints must be taken into account. In particular, several examinations can be assigned to the same room if they respect the capacity constraint. This problem has been identified by operations researchers as a scheduling problem with disjunctive and cumulative conjunctive constraints and is classified as NP-complete. However no classical operations research (OR) approach is directly applicable. Our application has been developed using constraint logic programming over finite domains. First, we give a brief overview of \{OR\} approaches for solving examination timetabling problems. Then we describe the examination timetabling problem for our university and show how constraint logic programming over finite domains can be used to solve it efficiently. Finally, we illustrate the important potentialities of constraint logic programming for the prototyping and implementation of real-life applications.

URLhttp://www.sciencedirect.com/science/article/pii/074310669500100X
DOI10.1016/0743-1066(95)00100-X