IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i10p1833-d431066.html
   My bibliography  Save this article

Modeling and Solving a Latin American University Course Timetabling Problem Instance

Author

Listed:
  • Oscar Chávez-Bosquez

    (División Académica de Ciencias y Tecnologías de la Información, Universidad Juárez Autónoma de Tabasco, Cunduacán, Tabasco 86690, Mexico)

  • José Hernández-Torruco

    (División Académica de Ciencias y Tecnologías de la Información, Universidad Juárez Autónoma de Tabasco, Cunduacán, Tabasco 86690, Mexico)

  • Betania Hernández-Ocaña

    (División Académica de Ciencias y Tecnologías de la Información, Universidad Juárez Autónoma de Tabasco, Cunduacán, Tabasco 86690, Mexico)

  • Juana Canul-Reich

    (División Académica de Ciencias y Tecnologías de la Información, Universidad Juárez Autónoma de Tabasco, Cunduacán, Tabasco 86690, Mexico)

Abstract

Timetabling problem is a complex task that is performed by a number of institutions worldwide, which has been usually addressed as an optimization problem where every approach considers the particular constraints of each institution under consideration. In this paper, we describe, model, and propose a solution to the timetabling problem at the División Académica de Ciencias y Tecnologías de la Información of the Universidad Juárez Autónoma de Tabasco (UJAT), México. We modeled the specific constraints of this problem instance using the Object Constraint Language (OCL) of the Unified Modeling Language (UML), and we validated the model while using the state-of-the-art tool USE: UML-based Specification Environment. The solution strategy tackles the problem in two stages: (1) ACA: academic assignments, i.e., assign lectures to professors and (2) TTP: the timetabling process. We developed a Tabu Search customization named Tabu Search with Probabilistic Aspiration Criterion (TS-PAC) in order to solve the timetabling problem, and we developed a software prototype to test our proposal. Two feasible timetables for two different semesters were obtained according to the modeled constraints.

Suggested Citation

  • Oscar Chávez-Bosquez & José Hernández-Torruco & Betania Hernández-Ocaña & Juana Canul-Reich, 2020. "Modeling and Solving a Latin American University Course Timetabling Problem Instance," Mathematics, MDPI, vol. 8(10), pages 1-29, October.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:10:p:1833-:d:431066
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/10/1833/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/10/1833/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. de Werra, D., 1985. "An introduction to timetabling," European Journal of Operational Research, Elsevier, vol. 19(2), pages 151-162, February.
    2. Hertz, A., 1991. "Tabu search for large scale timetabling problems," European Journal of Operational Research, Elsevier, vol. 54(1), pages 39-47, September.
    3. Fred Glover, 1990. "Tabu Search: A Tutorial," Interfaces, INFORMS, vol. 20(4), pages 74-94, August.
    4. Saviniec, Landir & Santos, Maristela O. & Costa, Alysson M., 2018. "Parallel local search algorithms for high school timetabling problems," European Journal of Operational Research, Elsevier, vol. 265(1), pages 81-98.
    5. Kergosien, Y. & Lenté, Ch. & Piton, D. & Billaut, J.-C., 2011. "A tabu search heuristic for the dynamic transportation of patients between care units," European Journal of Operational Research, Elsevier, vol. 214(2), pages 442-452, October.
    6. Valdecy Pereira & Helder Gomes Costa, 2016. "Linear Integer Model for the Course Timetabling Problem of a Faculty in Rio de Janeiro," Advances in Operations Research, Hindawi, vol. 2016, pages 1-9, January.
    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. Fabian Riquelme & Elizabeth Montero & Leslie Pérez-Cáceres & Nicolás Rojas-Morales, 2022. "A Track-Based Conference Scheduling Problem," Mathematics, MDPI, vol. 10(21), pages 1-25, October.

    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. De Causmaecker, Patrick & Demeester, Peter & Vanden Berghe, Greet, 2009. "A decomposed metaheuristic approach for a real-world university timetabling problem," European Journal of Operational Research, Elsevier, vol. 195(1), pages 307-318, May.
    2. Cangalovic, Mirjana & Kovacevic-Vujcic, Vera & Ivanovic, Lav & Drazic, Milan, 1998. "Modeling and solving a real-life assignment problem at universities," European Journal of Operational Research, Elsevier, vol. 110(2), pages 223-233, October.
    3. White, George M. & Xie, Bill S. & Zonjic, Stevan, 2004. "Using tabu search with longer-term memory and relaxation to create examination timetables," European Journal of Operational Research, Elsevier, vol. 153(1), pages 80-91, February.
    4. Juretzka, Jan & Böhler, Catharina & Drexl, Andreas, 2000. "Ein Decision Support System zur universitären Prüfungsplanung," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 530, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    5. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    6. de Werra, D., 1997. "The combinatorics of timetabling," European Journal of Operational Research, Elsevier, vol. 96(3), pages 504-513, February.
    7. Hertz, Alain & Robert, Vincent, 1998. "Constructing a course schedule by solving a series of assignment type problems," European Journal of Operational Research, Elsevier, vol. 108(3), pages 585-603, August.
    8. Saviniec, Landir & Santos, Maristela O. & Costa, Alysson M., 2018. "Parallel local search algorithms for high school timetabling problems," European Journal of Operational Research, Elsevier, vol. 265(1), pages 81-98.
    9. Drexl, Andreas & Juretzka, Jan & Salewski, Frank, 1993. "Academic course scheduling under workload and changeover constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 337, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    10. Jagota, Arun, 1996. "An adaptive, multiple restarts neural network algorithm for graph coloring," European Journal of Operational Research, Elsevier, vol. 93(2), pages 257-270, September.
    11. Michael R. Miller & Robert J. Alexander & Vincent A. Arbige & Robert F. Dell & Steven R. Kremer & Brian P. McClune & Jane E. Oppenlander & Joshua P. Tomlin, 2017. "Optimal Allocation of Students to Naval Nuclear-Power Training Units," Interfaces, INFORMS, vol. 47(4), pages 320-335, August.
    12. Valls, Vicente & Angeles Perez, M. & Sacramento Quintanilla, M., 1998. "Pre-processing techniques for resource allocation in the heterogeneous case," European Journal of Operational Research, Elsevier, vol. 107(2), pages 470-491, June.
    13. Gerhard Post & Samad Ahmadi & Sophia Daskalaki & Jeffrey Kingston & Jari Kyngas & Cimmo Nurmi & David Ranson, 2012. "An XML format for benchmarks in High School Timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 385-397, April.
    14. H. A. J. Crauwels & C. N. Potts & L. N. Van Wassenhove, 1998. "Local Search Heuristics for the Single Machine Total Weighted Tardiness Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 10(3), pages 341-350, August.
    15. Massimiliano Caramia & Stefano Giordani, 2020. "Curriculum-Based Course Timetabling with Student Flow, Soft Constraints, and Smoothing Objectives: an Application to a Real Case Study," SN Operations Research Forum, Springer, vol. 1(2), pages 1-21, June.
    16. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    17. Cazzaro, Davide & Fischetti, Martina & Fischetti, Matteo, 2020. "Heuristic algorithms for the Wind Farm Cable Routing problem," Applied Energy, Elsevier, vol. 278(C).
    18. Xi Chen & Enlu Zhou, 2015. "Population model-based optimization," Journal of Global Optimization, Springer, vol. 63(1), pages 125-148, September.
    19. David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    20. Vaithyanathan, Shivakumar & Burke, Laura I. & Magent, Michael A., 1996. "Massively parallel analog tabu search using neural networks applied to simple plant location problems," European Journal of Operational Research, Elsevier, vol. 93(2), pages 317-330, September.

    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:gam:jmathe:v:8:y:2020:i:10:p:1833-:d:431066. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.