HYBRID VNS-TS HEURISTICS FOR UNIVERSITY COURSE TIMETABLING PROBLEM

• Published in: Brazilian journal of operations & production management 2020-06, Vol.17 (2), p.1-20
• Main Authors: Vianna, Dalessandro Soares, Martins, Carlos Bazilio, Lima, Thiago Jéffery, Vianna, Marcilene de Fátima Dianin, Meza, Edwin Benito Mitacc
• Format: Article
• Language: English
• Subjects: Hybrid heuristics; Tabu Search; UCTTP; VNS; VNS-TS
• ISSN: 2237-8960; 2237-8960
• DOI: 10.14488/BJOPM.2020.014

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.