Skip to main content
SpringerLink
Log in

University Course Timetabling with Soft Constraints

  • Conference paper
Practice and Theory of Automated Timetabling IV (PATAT 2002)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2740))

Abstract

An extension of constraint logic programming that allows for weighted partial satisfaction of soft constraints is described and applied to the development of an automated timetabling system for Purdue University. The soft-constraint solver implemented in the proposed solution approach allows constraint propagation for hard constraints together with preference propagation for soft constraints. A new repair search algorithm is proposed to improve upon initially generated (partial) assignments of the problem variables. The model and search methods applied to the solution of the large lecture room component are presented and discussed along with the computational results.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abdennadher, S., Marte, M.: University Course Timetabling Using Constraint Handling Rules. J. Appl. Artif. Intell. 14, 311–326 (2000)

    Article  Google Scholar 

  2. Aubin, J., Ferland, J.A.: A Large Scale Timetabling Problem. Comput. Oper. Res. 16, 67–77 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  3. Banks, D., van Beek, P., Meisels, A.: A Heuristic Incremental Modeling Approach to Course timetabling. In: Proc. Artif. Intell. 1998, Canada (1998)

    Google Scholar 

  4. Bistarelli, S., Frühwirth, T., Martel, M., Rossi, F.: Soft Constraint Propagation and Solving in Constraint Handling Rules. In: Proc. ACM Symp. Appl. Comput. (2002)

    Google Scholar 

  5. Bistarelli, S., Montanari, U., Rossi, F.: Semiring-Based Constraint Solving and Optimization. J. ACM 44, 201–236 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  6. Carlsson, M., Ottosson, G., Carlson, B.: An Open-Ended Finite Domain Constraint Solver. In: Hartel, P.H., Kuchen, H. (eds.) PLILP 1997. LNCS, vol. 1292. Springer, Heidelberg (1997)

    Google Scholar 

  7. Carter, M.W.: A Comprehensive Course Timetabling and Student Scheduling System at the University of Waterloo. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 64–82. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  8. Carter, M.W., Laporte, G.: Recent Developments in Practical Course Timetabling. In: Burke, E.K., Carter, M. (eds.) PATAT 1997. LNCS, vol. 1408, pp. 3–19. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  9. Dubois, D., Fargier, H., Prade, H.: Possibility Theory in Constraint Satisfaction Problems: Handling Priority, Preference and Uncertainty. Appl. Intell. 6, 287–309 (1996)

    Article  Google Scholar 

  10. Freuder, E.C., Wallace, R.J.: Partial Constraint Satisfaction. Artif. Intell. 58, 21–70 (1992)

    Article  MathSciNet  Google Scholar 

  11. Frühwirth, T.: Constraint Handling Rules. In: Podelski, A. (ed.) Constraint Programming: Basics and Trends. LNCS, vol. 910. Springer, Heidelberg (1995)

    Google Scholar 

  12. Galinier, P., Hao, J.-K.: Tabu Search for Maximal Constraint Satisfaction Problems. In: Smolka, G. (ed.) CP 1997. LNCS, vol. 1330, pp. 196–208. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  13. Georget, Y., Codognet, P.: Compiling Semiring-Based Constraints with clp(FD,S). In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 205–219. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  14. Goltz, H.-J., Küchler, G., Matzke, D.: Constraint-Based Timetabling for Universities. In: Proc. INAP 1998, 11th Int. Conf. on Applications of Prolog, pp. 75–80 (1998)

    Google Scholar 

  15. Guéret, C., Jussien, N., Boizumault, P., Prins, C.: Building University Timetables Using Constraint Logic Programming. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 130–145. Springer, Heidelberg (1996)

    Google Scholar 

  16. Henz, M., Würtz, J.: Using Oz for College Timetabling. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 162–177. Springer, Heidelberg (1996)

    Google Scholar 

  17. IC-Park. ECL i PS e Constraint Library Manual, Release 5.5 (2002), http://www.icparc.ic.ac.uk/eclipse

  18. Jaffar, J., Maher, M.J.: Constraint Logic Programming: a Survey. J. Logic Program. 19, 503–581 (1994)

    Article  MathSciNet  Google Scholar 

  19. Meseguer, P., Larrosa, J., Sánchez, M.: Lower Bounds for Non-binary Constraint Optimization Problems. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 317–331. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  20. Mooney, E.: Tabu Search Heuristics for Resource Scheduling. Ph.D. Thesis, Purdue University (1991)

    Google Scholar 

  21. Le Pape, C.: Implementation of Resource Constraints in ILOG SCHEDULE: a Library for the Development of Constraint-Based Scheduling Systems. Intell. Syst. Engng. 3, 55–66 (1994)

    Article  Google Scholar 

  22. Robert, V., Hertz, A.: How to Decompose Constrained Course Scheduling Problems into Easier Assignment Type Subproblems. In: Burke, E.K., Ross, P. (eds.) PATAT 1995. LNCS, vol. 1153, pp. 364–373. Springer, Heidelberg (1996)

    Google Scholar 

  23. Rudová, H.: Constraint Satisfaction with Preferences. Ph.D. Thesis, Faculty of Informatics, Masaryk University (2001), http://www.fi.muni.cz/~hanka/phd.html

  24. Rudová, H.: Soft CLP(FD). In: Haller, S., Russell, I. (eds.) Proc. 16th Int. Florida Artif. Intell. Symp (FLAIRS 2003), AAAI Press, Menlo Park (2003) (accepted for publication)

    Google Scholar 

  25. Rudová, H., Matyska, L.: Constraint-Based Timetabling with Student Schedules. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 109–123. Springer, Heidelberg (2001)

    Google Scholar 

  26. Sampson, S.E., Freeland, J.R., Weiss, E.N.: Class Scheduling to Maximize Participant Satisfaction. Interfaces 25, 30–41 (1995)

    Article  Google Scholar 

  27. Schaerf, A.: A Survey of Automated Timetabling. Technical Report CS-R9567. CWI, Amsterdam (1995)

    Google Scholar 

  28. Van Hentenryck, P.: Constraint Satisfaction in Logic Programming. MIT Press, Cambridge (1989)

    Google Scholar 

  29. Veřmiřovský, K., Rudová, H.: Limited Assignment Number Search Algorithm. In: Student Res. Forum of the 29th Annu. Conf. on Curr. Trends in Theory and Practice of Informatics, SOFSEM 2002 (2002), See http://www.fi.muni.cz/~hanka/publications

Download references

Author information

Authors and Affiliations

  1. Faculty of Informatics, Masaryk University, Botanická 68a, Brno, 602 00, Czech Republic

    Hana Rudová

  2. Space Management and Academic Scheduling, Purdue University, 400 Centennial Mall Drive, West Lafayette, IN, 47907-2016, USA

    Keith Murray

Authors
  1. Hana Rudová
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Keith Murray
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Automated Scheduling, Optimisation and Planning Group, School of Computer Science & IT, University of Nottingham, NG8 1BB, Nottingham, UK

    Edmund Burke

  2. Information Technology, KaHo St-Lieven, Gebr. Desmetstraat 1, 9000, Gent, Belgium

    Patrick De Causmaecker

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Rudová, H., Murray, K. (2003). University Course Timetabling with Soft Constraints. In: Burke, E., De Causmaecker, P. (eds) Practice and Theory of Automated Timetabling IV. PATAT 2002. Lecture Notes in Computer Science, vol 2740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45157-0_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-45157-0_21

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-40699-0

  • Online ISBN: 978-3-540-45157-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation