HYBRID VNS-TS HEURISTICS FOR UNIVERSITY COURSE TIMETABLING PROBLEM

  • Dalessandro Soares Vianna Universidade Federal Fluminense
  • Carlos Bazilio Martins
  • Thiago Jéffery Lima
  • Marcilene de Fátima Dianin Vianna
  • Edwin Benito Mitacc Meza
Keywords: Hybrid heuristics, UCTTP, VNS, Tabu Search, VNS-TS

Abstract

Goal: Propose hybrid heuristics combining VNS and Tabu Search (TS) for adding adaptability to University Course Timetabling Problem (UCTTP) resolution.

Design / Methodology / Approach: VNS and TS metaheuristics were used isolated and in combination in order to verify which shape acquired the best solutions. Those heuristics were verified using constraints found at two undergraduate courses of Federal Fluminense University. Effectiveness is verified by comparing them with solutions manually elaborated by undergraduate course coordinators.

Results: The computational results showed the efficiency of the hybrid VNS-TS heuristics, with emphasis on the heuristic VNS-TS1, which uses tabu search as local search method.

Practical implications: The hybrid heuristic VNS-TS1 has been in use since the first half of 2019 by some of UFF undergraduate courses coordinations. Even though each university has specific constraints on its timetable, the use of the proposed heuristics is possible because it has been developed using the framework FINESS that allows for the easy insertion and removal of constraints.

Originality / Value: We have the following innovative contributions: Development of heuristics with a high degree of adaptation to the needs of educational institutions; Two proposed VNS-TS heuristics; Proposed VND-TS improvement method.

Published
2020-05-13
How to Cite
Vianna, D., Martins, C., Lima, T., Vianna, M. de F., & Meza, E. (2020). HYBRID VNS-TS HEURISTICS FOR UNIVERSITY COURSE TIMETABLING PROBLEM. Brazilian Journal of Operations & Production Management, 17(2), 1-20. https://doi.org/https://doi.org/10.14488/BJOPM.2020.014
Section
Research paper