Skip to main content
SpringerLink
Log in

A comparison of annealing techniques for academic course scheduling

  • Conference paper
  • First Online:
Practice and Theory of Automated Timetabling II (PATAT 1997)

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

Abstract

In this study we have tackled the NP-hard problem of academic class scheduling (or timetabling) at the university level. We have investigated a variety of approaches based on simulated annealing, including mean-field annealing, simulated annealing with three different cooling schedules, and the use of a rule-based preprocessor to provide a good initial solution for annealing. The best results were obtained using simulated annealing with adaptive cooling and reheating as a function of cost, and a rule-based preprocessor. This approach enabled us to obtain valid schedules for the timetabling problem for a large university, using a complex cost function that includes student preferences. None of the other methods were able to provide a complete valid schedule.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Aarts, E. H., J. Korst, and P. J. van Laarhoven, “Simulated annealing,” in Local Search in Combinatorial Optimization, E. H. Aarts and J. K. Lenstra (eds.), John Wiley and Sons, 1997.

    Google Scholar 

  2. Abramson, D., “Constructing school timetables using simulated annealing: sequential and parallel algorithms,” Management Science 37(1), 98–113, 1991.

    MathSciNet  Google Scholar 

  3. Abramson, D., H. Dang, and M. Krishnamoorthy, “An Empirical Study of Simulated Annealing Cooling Schedules,” Griffith Univ. report, Nathan, Qld, Aus. 1994; “Simulated Annealing Cooling Schedules for the School Timetabling Problem,” submitted to Asia Pacific Journal of Operations Research, 1996.

    Google Scholar 

  4. Burke, E., and P. Ross, eds., Practice and Theory of Automated Timetabling, First International Conference, Edinburgh, 1995: Selected Papers, Lecture Notes in Computer Science no. 1153, Springer, New York, 1996.

    Google Scholar 

  5. de Werra, D., “An introduction to timetabling,” European Journal of Operational Research 19, 151–162, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  6. Diekmann, R., R. Lüling, and J. Simon, “Problem independent distributed simulated annealing and its applications,” in Applied Simulated Annealing, R. V. Vidal ed., Lecture Notes in Economics and Mathematical Systems, no. 396, Springer-Verlag, 1993.

    Google Scholar 

  7. Dowsland, K., “Using Simulated Annealing for Efficient Allocation of Students to Practical Classes”, Working Paper, Statistics and OR Group, European Business Management School, University College of Swansea, UK, 1994.

    Google Scholar 

  8. Dowsland, K. and J. Thompson, “Variants of Simulated Annealing for the Examination Timetabling Problem,” Working Paper, Statistics and OR Group, European Business Management School, University College of Swansea, UK, 1994.

    Google Scholar 

  9. Eiselt H. A., and G. Laporte, “Combinatorial Optimization Problems with Soft and Hard Requirements,” J. Operational Research Society, vol. 38, No. 9, pp. 785–795, 1987.

    Article  MATH  Google Scholar 

  10. Elmohamed, S., G. C. Fox, P. Coddington, “Course Scheduling using Mean-Field Annealing, Part I: algorithm and Part II: implementation,” Northeast Parallel Architectures Center technical report SCCS-782, Syracuse University, Syracuse, NY, 1996.

    Google Scholar 

  11. Elmohamed, S., P. Coddington, G.C. Fox, “Academic Scheduling using Simulated Annealing with a Rule-Based Preprocessor”, Northeast Parallel Architectures Center technical report SCCS-781, Syracuse University, Syracuse, NY, 1997.

    Google Scholar 

  12. Gee, Andrew, private communication.

    Google Scholar 

  13. Gislén, L., B. Söderberg, C. Peterson, “Teachers and Classes with Neural Nets,” International Journal of Neural Systems 1, 167 (1989).

    Article  Google Scholar 

  14. Gislén, L., B. Söderberg, C. Peterson, “Complex scheduling with Potts neural networks,” Neural Computation, 4, 805–831, 1992.

    Google Scholar 

  15. Hertz, J., A. Krogh and R. Palmer, Introduction to the Theory of Neural Computation, Addison-Wesley, Redwood City, CA, 1991.

    Google Scholar 

  16. Hogg, T., B. Huberman, and C. Williams (editors), Artificial Intelligence, special issue on Phase transitions and the search space, p. 81, 1996.

    Google Scholar 

  17. Hopfield, J. J., and D. W. Tank, “Neural Computation of Decisions in Optimization Problems,” Biological Cybernetics 52, 141 (1985).

    MATH  MathSciNet  Google Scholar 

  18. Huang, M., F. Romeo, and A. Sangiovanni-Vincentelli, “An efficient general cooling schedule for simulated annealing,” Proc. of the IEEE International Conference on Computer Aided Design (ICCAD), pp. 381–384, 1986.

    Google Scholar 

  19. Johnson, D., C. Aragon, L. McGeoch, and C. Schevon, “Optimization by Simulated Annealing: an Experimental Evaluation, Part I (Graph Partitioning),” Operations Research 37, 865–892 (1989).

    Article  MATH  Google Scholar 

  20. Johnson, D., C. Aragon, L. McGeoch, and C. Schevon, “Optimization by Simulated Annealing: an Experimental Evaluation, Part II (Graph Coloring and number partitioning),” Operations Research 39, No. 3, 865–892 (1991).

    Google Scholar 

  21. Johnson, D., and L. McGeoch, “The Traveling Salesman Problem: A Case Study in Local Optimization,” in Local Search in Combinatorial Optimization, E. H. Aarts and J. K. Lenstra (eds.), Wiley and Sons, 1997.

    Google Scholar 

  22. Kirkpatrick, S., C. D. Gelatt, Jr., and M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671–680, (13 May 1983).

    MathSciNet  Google Scholar 

  23. Kirkpatrick, S., “Optimization by simulated annealing: Quantitative studies,” J. Stat. Physics 34, 976–986 (1984).

    Article  Google Scholar 

  24. Lister, R., “Annealing Networks and Fractal Landscapes,” Proc. IEEE International Conference on Neural Nets, March 1993, Vol. I, pp 257–262.

    Google Scholar 

  25. Miner, S., S. Elmohamed, and H. W. Yau, “Optimizing Timetabling Solutions Using Graph Coloring,” 1995 NPAC REU program, NPAC, Syracuse University, Syracuse, NY, 1995.

    Google Scholar 

  26. Mouritsen, O. G., Computer Studies of Phase Transitions and Critical Phenomena, Springer-Verlag, Berlin, 1984.

    Google Scholar 

  27. Otten, R., and L. van Ginneken, The Annealing Algorithm, Kluwer Academic Publishers, 1989.

    Google Scholar 

  28. Peterson, C., and B. Söderberg, “Artificial Neural Networks and Combinatorial Optimization Problems,” Local Search in Combinatorial Optimization, E.H.L. Aarts and J.K. Lenstra (eds.), Wiley and Sons, 1997.

    Google Scholar 

  29. Peterson, C., and B. Söderberg, “A New Method for Mapping Optimization Problems onto Neural Nets”, International Journal of Neural Systems 1, 3 (1989).

    Article  MATH  Google Scholar 

  30. Schaerf, A., “A survey of automated timetabling,” Department of Software Technology, Report CS-R9567, CWI, Amsterdam, The Netherlands.

    Google Scholar 

  31. Simmen, Martin, Personal Communication.

    Google Scholar 

  32. Sorkin, G., Theory and Practice of Simulated Annealing on Special Energy Landscapes, PhD. Thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, July 1991.

    Google Scholar 

  33. Thompson, J., and K. Dowsland, “General Cooling Schedules for Simulated Annealing Based Timetabling Systems,” Proceedings of the 1st International Conf. on the Practice and Theory of Automated Timetabling, Napier Univ., Edinburgh 1995.

    Google Scholar 

  34. van Laarhoven, P. J. and E. H. Aarts, Simulated Annealing: Theory and Applications. D. Reidel, Dordrecht, 1987.

    MATH  Google Scholar 

  35. Vidal, R. V. ed., Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems no. 396, Springer-Verlag, 1993.

    Google Scholar 

  36. White, S. R., “Concepts of scale in simulated annealing,” Proceedings of the IEEE International Conference on Circuit Design, pp 646–651, 1984.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Northeast Parallel Architectures Center, Syracuse University, 13244, Syracuse, NY, USA

    M. A. Saleh Elmohamed & Geoffrey Fox

  2. Department of Computer Science, University of Adelaide, 5005, S.A., Australia

    Paul Coddington

Authors
  1. M. A. Saleh Elmohamed
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paul Coddington
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Geoffrey Fox
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Edmund Burke Michael Carter

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Elmohamed, M.A.S., Coddington, P., Fox, G. (1998). A comparison of annealing techniques for academic course scheduling. In: Burke, E., Carter, M. (eds) Practice and Theory of Automated Timetabling II. PATAT 1997. Lecture Notes in Computer Science, vol 1408. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055883

Download citation

  • DOI: https://doi.org/10.1007/BFb0055883

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64979-3

  • Online ISBN: 978-3-540-49803-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation