Abstract
In this chapter, we present an application of Constraint Logic Programming to the examination planning problem of our University. Each year, in June, 4000 students of various branches of instruction have to attend examination during a couple of weeks for academic reasons. The problem (for June 1993) consists of planning 308 different examinations on 33 half-days over 7 rooms of different capacities. A set of different and various constraints has to be satisfied. This problem has been identified by operations researchers as a scheduling problem with disjunctive and cumulative conjunctive constraints and classified as NP-complete (using a naive enumeration would lead to consider (7 * 33)308 possibilities). The solution has been reached using the finite domains of CHIP. We have developed two versions of the application: one using Chipv3, and one using Chipv4 which owns special kinds of new constraints like the cumulative constraint. After having described the specific problem of our university, we will present the two developments and compare them. Finally, we will illustrate the huge capacity of prototyping and implementation of real-life applications in Constraint Logic Programming.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Aggoun and N. Beldiceanu. Extending Chip in order to solve complex scheduling and placement problems. In Journées francophones de la programmation en logique, Lille, 1992.
J. Bellone, A. Chamard, and C. Pradelles. Plane: An evolutive system for aircraft production written in Chip. In First Int. Conference on Practical Applications of Prolog, London, 1992.
P. Boizumault, Y. Delon, and L. Péridy. Solving a real life exams problem using Constraint Logic Programming. In Manfred Meyer, editor, Constraint Processing: Proceedings of the international workshop at CSAM'93, DFKI Document D-94-13, German Research Center for Artificial Intelligence, Kaiserslautern, Germany, 1993.
P. Boizumault, Y. Delon, and L. Péridy. Planning exams using Constraint Logic Programming. In Second Int. Conference on Practical Applications of Prolog, London, 1994.
P. Baptiste, B. Legeard, and C. Varnier. Hoist scheduling problem: an approach based on Constraint Programming. In IEEE International Conference on Robotics and Automation, Nice, 1992.
A. Borning, M. Maher, A. Martingale, and M. Wilson. Constraint hierarchies and Logic Programming. In Sixth Int. Logic Programming Conference, Lisboa, 1989.
A. M. Barham and J. B. Westwood. A simple heuristic to facilitate course time-tabling. Journal of Operational Research Society, 29, 1978.
M. W. Carter. A survey of pratical applications of examination timetabling algorithms. Operations Research, 24(2), 1986.
A. Chamard and A. Fischler. A workshop scheduler written in Chip. In Second Int. Conference on Practical Applications of Prolog, London, 1994.
Cosytec SA, Orsay, France. Chip user's guide, 1993.
X. Cousin. Applications de la Programmation en Logique avec Contraintes au problème d'emploi du temps. PhD thesis, Rennes University, France, 1993.
M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, and F. Berthier. The Constraint Logic Programming language Chip. In International Conference on Fifth Generation Computer Systems, Tokyo, 1988.
S. Desroches and G. Laporte. Examination timetabling by computer. Operations Research, 1984.
S. Desroches, G. Laporte, and J.M. Rousseau. Horex: a computer program for the construction of examination schedules. INFOR 16, 1978.
M. Dincbas, H. Simonis, and P. Van Hentenryck. Solving large combinatorial problems in Logic Programming. Journal of Logic Programming, 8, 1990.
D. de Werra. An introduction to time tabling. European Journal of Operational Research, 19, 1985.
D. de Werra. Heuristics for graph coloring. Computing Suppl., 7, 1990.
R. Feldman and M. Golumbic. Optimization algorithms for student scheduling via constraint satisfiability. The Computer Journal, 33(4), 1990.
R. Harralick and G. Elliot. Increasing tree search efficiency for Constraint Satisfaction Problems. Artificial Intelligence, 14, 1980.
P. Van Hentenryck. Constraint Satisfaction in Logic Programming. MIT Press, 1989.
P. Van Hentenryck. The cardinality operator: a new logical connective for Constraint Logic Programming. In Eigth Int. Logic Programming Conference, Paris, 1991.
P. Van Hentenryck. Scheduling and packing in the constraint language cc(FD). Technical report, CS Department, Brown University, 1992.
P. Van Hentenryck, V. Saraswat, and Y. Deville. Implementation and evaluation of the constraint language cc(FD). Technical report, CS Department, Brown University, 1992.
F. Menez, P. Barahona, and P. Codognet. An incremental constraint solver applied to a time-tabling problem. In thirteenth conference on expert systems, Avignon France, 1993.
J. P. Le Pape and D. Ranson. Clef or programming with constraints, logic, equations and functions. In 4th Int. Conference on Software Engineering and its Applications, Toulouse, France, 1991.
M. Rueher and B. Legeard. Which role for CLP in software engineering? an investigation on the basis of first applications. In First International Conference on Practical Applications of Prolog, London, 1992.
M. Rueher. A first exploration of PrologIII's capabilities. Software-Practice and Experience, 23(2), 1993.
Rayward Smit and Shing. Bin packing. Bulletin of the IMA, 19, 1983.
A. Tripathy. School timetabling: a case in large binary integer linear programming. Management Science, 13(12), 1984.
E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
D. C. Wood. A system for computing university examination timetables. Computer Journal, 11, 1968.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boizumault, P., Delon, Y., Péridy, L. (1995). A CLP approach for examination planning. In: Meyer, M. (eds) Constraint Processing. CP CP 1994 1993. Lecture Notes in Computer Science, vol 923. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59479-5_20
Download citation
DOI: https://doi.org/10.1007/3-540-59479-5_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59479-6
Online ISBN: 978-3-540-49281-8
eBook Packages: Springer Book Archive