A time-dependent metaheuristic algorithm for post enrolment-based course timetabling

Article English OPEN
Lewis, Rhyd (2012)

A metaheuristic-based algorithm is presented for the post enrolment-based course timetabling problem used in track-2 of the Second International Timetabling Competition (ITC2007). The featured algorithm operates in three distinct stages—a constructive phase followed by two separate phases of simulated annealing—and is time dependent, due to the fact that various run-time parameters are calculated automatically according to the amount of computation time available. Overall, the method produces results in line with the official finalists to the timetabling competition, though experiments show that this algorithm also seems to find certain instances more difficult to solve than others. A number of reasons for this latter feature are discussed.
  • References (19)
    19 references, page 1 of 2

    Abramson, D., Krishnamoorthy, H., Dang, H., 1996. Simulated annealing cooling schedules for the school timetabling problem. Asia-Paci c Journal of Operational Research 16, 1{22.

    Atsuta, M., Nonobe, K., Ibaraki, T., 2008. Itc-2007 track 2: An approach using general csp solver. URL www.cs.qub.ac.uk/itc2007/winner/bestcoursesolutions/Atsuta et al.pdf

    Brelaz, D., 1979. New methods to color the vertices of a graph. Commun. ACM 22 (4), 251{256.

    Burke, E., Gendreau, M. (Eds.), 2008. Proceedings of the Seventh International Conference for the Practice and Theory of Automated Timetabling. Universite de Montreal, Canada. URL http://www.asap.cs.nott.ac.uk/patat/patat08

    Cambazard, H., Hebrard, E., Osullivan, B., A., P., 2008. Local search and constraint programming for the post-enrolment-based course timetabling problem. In: Burke and Gendreau (2008). URL http://www.asap.cs.nott.ac.uk/patat/patat08

    Chiarandini, M., Fawcett, C., Hoos, H., 2008. A modular multiphase heuristic solver for post enrolment course timetabling. In: Burke and Gendreau (2008). URL http://www.asap.cs.nott.ac.uk/patat/patat08

    Chiarandini, M., Stutzle, T., 2002. An application of iterated local search to graph coloring. In: Johnson, I. D., Mehrotra, A., Trick, M. (Eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations. New York, USA, pp. 112{125.

    Di Gaspero, L., McCollum, B., Schaerf, A., August 2007. The second international timetabling competition (itc-2007): Curriculum-based course timetabling (track 3). Tech. Rep. QUB/IEEE/Tech/ITC2007/CurriculumCTT/v1.0/1, School of Computing, Queens University, Belfast.

    Kirkpatrick, S., Gelatt, C., Vecchi, M., 1983. Optimization by simulated annealing. Science 4598, 671{680.

    Kostuch, P., 2005. The university course timetabling problem with a 3-phase approach. In: Burke, E., Trick, M. (Eds.), Practice and Theory of Automated Timetabling (PATAT) V. Vol. 3616. Springer-Verlag, Berlin, pp. 109{125.

  • Metrics
    0
    views in OpenAIRE
    0
    views in local repository
    37
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Online Research @ Cardiff - IRUS-UK 0 37
Share - Bookmark