IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v240y2015i3p637-648.html
   My bibliography  Save this article

Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem

Author

Listed:
  • Lewis, R.
  • Thompson, J.

Abstract

This paper provides a mathematical treatment of the NP-hard post enrolment-based course timetabling problem and presents a powerful two-stage metaheuristic-based algorithm to approximately solve it. We focus particularly on the issue of solution space connectivity and demonstrate that when this is increased via specialised neighbourhood operators, the quality of solutions achieved is generally enhanced. Across a well-known suite of benchmark problem instances, our proposed algorithm is shown to produce results that are superior to all other methods appearing in the literature; however, we also make note of those instances where our algorithm struggles in comparison to others and offer evidence as to why.

Suggested Citation

  • Lewis, R. & Thompson, J., 2015. "Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem," European Journal of Operational Research, Elsevier, vol. 240(3), pages 637-648.
    • Handle: RePEc:eee:ejores:v:240:y:2015:i:3:p:637-648
    DOI: 10.1016/j.ejor.2014.07.041
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714006079
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.07.041?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Barry McCollum & Andrea Schaerf & Ben Paechter & Paul McMullan & Rhyd Lewis & Andrew J. Parkes & Luca Di Gaspero & Rong Qu & Edmund K. Burke, 2010. "Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 120-130, February.
    2. Lü, Zhipeng & Hao, Jin-Kao, 2010. "Adaptive Tabu Search for course timetabling," European Journal of Operational Research, Elsevier, vol. 200(1), pages 235-244, January.
    3. Eliashberg, Jehoshua & Hegie, Quintus & Ho, Jason & Huisman, Dennis & Miller, Steven J. & Swami, Sanjeev & Weinberg, Charles B. & Wierenga, Berend, 2009. "Demand-driven scheduling of movies in a multiplex," International Journal of Research in Marketing, Elsevier, vol. 26(2), pages 75-88.
    4. Clemens Nothegger & Alfred Mayer & Andreas Chwatal & Günther Raidl, 2012. "Solving the post enrolment course timetabling problem by ant colony optimization," Annals of Operations Research, Springer, vol. 194(1), pages 325-339, April.
    5. Rhyd Lewis, 2012. "A time-dependent metaheuristic algorithm for post enrolment-based course timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 273-289, April.
    6. Eliashberg, J. & Hegie, Q. & Ho, J. & Huisman, D. & Miller, S.J. & Swami, S. & Weinberg, C.B. & Wierenga, B., 2007. "Demand-Driven Scheduling of Movies in a Multiplex," ERIM Report Series Research in Management ERS-2007-033-MKT, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    7. J. Broek & C. Hurkens, 2012. "An IP-based heuristic for the post enrolment course timetabling problem of the ITC2007," Annals of Operations Research, Springer, vol. 194(1), pages 439-454, April.
    8. Alberto Caprara & Matteo Fischetti & Paolo Toth, 2002. "Modeling and Solving the Train Timetabling Problem," Operations Research, INFORMS, vol. 50(5), pages 851-861, October.
    9. Philippe Galinier & Jin-Kao Hao, 1999. "Hybrid Evolutionary Algorithms for Graph Coloring," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 379-397, December.
    10. Hadrien Cambazard & Emmanuel Hebrard & Barry O’Sullivan & Alexandre Papadopoulos, 2012. "Local search and constraint programming for the post enrolment-based course timetabling problem," Annals of Operations Research, Springer, vol. 194(1), pages 111-135, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ceschia, Sara & Di Gaspero, Luca & Schaerf, Andrea, 2023. "Educational timetabling: Problems, benchmarks, and state-of-the-art results," European Journal of Operational Research, Elsevier, vol. 308(1), pages 1-18.
    2. Alexander Kiefer & Richard F. Hartl & Alexander Schnell, 2017. "Adaptive large neighborhood search for the curriculum-based course timetabling problem," Annals of Operations Research, Springer, vol. 252(2), pages 255-282, May.
    3. Soria-Alcaraz, Jorge A. & Ochoa, Gabriela & Sotelo-Figeroa, Marco A. & Burke, Edmund K., 2017. "A methodology for determining an effective subset of heuristics in selection hyper-heuristics," European Journal of Operational Research, Elsevier, vol. 260(3), pages 972-983.
    4. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    5. Say Leng Goh & Graham Kendall & Nasser R. Sabar & Salwani Abdullah, 2020. "An effective hybrid local search approach for the post enrolment course timetabling problem," OPSEARCH, Springer;Operational Research Society of India, vol. 57(4), pages 1131-1163, December.
    6. Goh, Say Leng & Kendall, Graham & Sabar, Nasser R., 2017. "Improved local search approaches to solve the post enrolment course timetabling problem," European Journal of Operational Research, Elsevier, vol. 261(1), pages 17-29.
    7. Dhananjay Thiruvady & Rhyd Lewis & Kerri Morgan, 2020. "Tackling the maximum happy vertices problem in large networks," 4OR, Springer, vol. 18(4), pages 507-527, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fabian Dunke & Stefan Nickel, 2023. "A matheuristic for customized multi-level multi-criteria university timetabling," Annals of Operations Research, Springer, vol. 328(2), pages 1313-1348, September.
    2. Soria-Alcaraz, Jorge A. & Ochoa, Gabriela & Sotelo-Figeroa, Marco A. & Burke, Edmund K., 2017. "A methodology for determining an effective subset of heuristics in selection hyper-heuristics," European Journal of Operational Research, Elsevier, vol. 260(3), pages 972-983.
    3. Say Leng Goh & Graham Kendall & Nasser R. Sabar & Salwani Abdullah, 2020. "An effective hybrid local search approach for the post enrolment course timetabling problem," OPSEARCH, Springer;Operational Research Society of India, vol. 57(4), pages 1131-1163, December.
    4. Kadri Sylejmani & Edon Gashi & Adrian Ymeri, 2023. "Simulated annealing with penalization for university course timetabling," Journal of Scheduling, Springer, vol. 26(5), pages 497-517, October.
    5. Moritz Mühlenthaler & Rolf Wanka, 2016. "Fairness in academic course timetabling," Annals of Operations Research, Springer, vol. 239(1), pages 171-188, April.
    6. Hao, Jin-Kao & Benlic, Una, 2011. "Lower bounds for the ITC-2007 curriculum-based course timetabling problem," European Journal of Operational Research, Elsevier, vol. 212(3), pages 464-472, August.
    7. Mutsunori Banbara & Katsumi Inoue & Benjamin Kaufmann & Tenda Okimoto & Torsten Schaub & Takehide Soh & Naoyuki Tamura & Philipp Wanko, 2019. "$${\varvec{teaspoon}}$$ teaspoon : solving the curriculum-based course timetabling problems with answer set programming," Annals of Operations Research, Springer, vol. 275(1), pages 3-37, April.
    8. Lü, Zhipeng & Hao, Jin-Kao, 2012. "Adaptive neighborhood search for nurse rostering," European Journal of Operational Research, Elsevier, vol. 218(3), pages 865-876.
    9. Goh, Say Leng & Kendall, Graham & Sabar, Nasser R., 2017. "Improved local search approaches to solve the post enrolment course timetabling problem," European Journal of Operational Research, Elsevier, vol. 261(1), pages 17-29.
    10. Brinja Meiseberg & Thomas Ehrmann, 2013. "Diversity in teams and the success of cultural products," Journal of Cultural Economics, Springer;The Association for Cultural Economics International, vol. 37(1), pages 61-86, February.
    11. Alexander Kiefer & Richard F. Hartl & Alexander Schnell, 2017. "Adaptive large neighborhood search for the curriculum-based course timetabling problem," Annals of Operations Research, Springer, vol. 252(2), pages 255-282, May.
    12. Andrea Bettinelli & Valentina Cacchiani & Roberto Roberti & Paolo Toth, 2015. "An overview of curriculum-based course timetabling," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 313-349, July.
    13. Andrea Baldin & Trine Bille & Andrea Ellero & Daniela Favaretto, 2016. "Multiobjective optimization model for pricing and seat allocation problem in non profit performing arts organization," Working Papers 20, Venice School of Management - Department of Management, Università Ca' Foscari Venezia.
    14. Andrea Baldin & Trine Bille & Andrea Ellero & Daniela Favaretto, 2018. "Revenue and attendance simultaneous optimization in performing arts organizations," Journal of Cultural Economics, Springer;The Association for Cultural Economics International, vol. 42(4), pages 677-700, November.
    15. Ceschia, Sara & Di Gaspero, Luca & Schaerf, Andrea, 2023. "Educational timetabling: Problems, benchmarks, and state-of-the-art results," European Journal of Operational Research, Elsevier, vol. 308(1), pages 1-18.
    16. Soria-Alcaraz, Jorge A. & Ochoa, Gabriela & Swan, Jerry & Carpio, Martin & Puga, Hector & Burke, Edmund K., 2014. "Effective learning hyper-heuristics for the course timetabling problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 77-86.
    17. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    18. Wang, Dian & D’Ariano, Andrea & Zhao, Jun & Zhong, Qingwei & Peng, Qiyuan, 2022. "Integrated rolling stock deadhead routing and timetabling in urban rail transit lines," European Journal of Operational Research, Elsevier, vol. 298(2), pages 526-559.
    19. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    20. Wijiharjono, Nuryadi, 2017. "Kajian perkembangan penelitian pemasaran film [Contemporary study of film marketing research]," MPRA Paper 83349, University Library of Munich, Germany, revised Aug 2017.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:240:y:2015:i:3:p:637-648. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.