Compromise ratio with weighting functions in a Tabu Search multi-criteria approach to examination timetabling

摘要

University examination scheduling is a difficult and heavily administrative task, particularly when the number of students and courses is high. Changes in educational paradigms, an increase in the number of students, the aggregation of schools, more flexible curricula, among others, are responsible for an increase in the difficulty of the problem. As a consequence, there is a continuous demand for new and more efficient approaches. Optimisation and Constraint Programming communities have devoted considerable attention to this difficult problem. Just the definition of a satisfactory, not to mention optimal, timetabling may be complex. In fact, to characterise a timetabling solution, a single criteria may not be enough, since what may be considered good for one group of students may be regarded inappropriate for other students, or teachers. In this paper, four criteria were used to characterise the spreading of the exams over the examination period. A set of constraints regarding the non-overlapping of exams with students in common was considered. A multi-objective optimisation program was used to handle the four criteria and a Tabu Search was implemented to find a good feasible solution for this problem. Two new features to increase the automation of the algorithm were proposed. First, it uses a Fuzzy Inference Ruled Based System to choose the tabu tenure of the elements in the tabu list. Secondly, a modified version of the Compromise Ratio (CR) is proposed, where the usual fixed weights are replaced by weighting functions to rank the neighbourhood solutions in each iteration. Sufficient conditions which guarantee the monotonicity of the weighting functions are presented. (C) 2016 Elsevier Ltd. All rights reserved.