Catálogo de publicaciones - libros

In this paper we introduce a new fuzzy evaluation function for examination timetabling. We describe how we employed fuzzy reasoning to evaluate the quality of a constructed timetable by considering two criteria: the average penalty per student and the highest penalty imposed on any of the students. A fuzzy system was created based on a series of easy to understand rules to combine the two criteria. A significant problem encountered was how to determine the lower and upper bounds of the decision criteria for any given problem instance, in order to allow the fuzzy system to be fixed and, hence, applicable to new problems without alteration. In this work, two different methods for determining boundary settings are proposed. Experimental results are presented and the implications analysed. These results demonstrate that fuzzy reasoning can be successfully applied to evaluate the quality of timetable solutions in which multiple decision criteria are involved.

Linear Linkage Encoding (LLE) is a recently proposed representation scheme for evolutionary algorithms. This representation has been used only in data clustering. However, it is also suitable for grouping problems. In this paper, we investigate LLE on two grouping problems; graph coloring and exam timetabling. Two crossover operators suitable for LLE are proposed and compared to the existing ones. Initial results show that LLE is a viable candidate for grouping problems whenever appropriate genetic operators are used.

Scheduling exams at universities can be formulated as a combinatorial optimization problem. Basically one has to schedule a certain number of exams in a given number of time periods so that a predetermined objective function is minimized. In particular, the objective function penalizes schedules where students have to write exams in consecutive periods or even in the same period. Ant colony approaches have been demonstrated to be a powerful solution approach for various combinatorial optimization problems. This paper presents two ant colony approaches for the exam timetabling problem, a Max–Min and an ANTCOL approach. Using the Toronto benchmark test cases from the literature, both algorithms arc compared to other timetabling heuristics. Finally, the Max–Min and ANTCOL algorithms are compared using the same set of test cases. In spite of some shortcomings, the ANTCOL approach turned out to be a worthwhile algorithm, among the best currently in use for examination timetabling.

Several modelling languages have been proposed to standardize the specification, solution and data format for timetabling problems. As of now these languages have not been adopted as standards and are seen as not simplifying the modelling process, lacking features and offering little advantage over traditional programming languages. In contrast to this approach we propose a new language-independent modelling framework for general timetabling problems based on past experience of modelling the examination timetabling problem. This framework is a work in progress but demonstrates the possibilities and convenience such a model would afford.

Hyper-heuristics are proposed as a higher level of abstraction as compared to the metaheuristics. Hyper-heuristic methods deploy a set of simple heuristics and use only non-problem-specific data, such as fitness change or heuristic execution time. A typical iteration of a hyper-heuristic algorithm consists of two phases: the heuristic selection method and move acceptance. In this paper, heuristic selection mechanisms and move acceptance criteria in hyper-heuristics are analyzed in depth. Seven heuristic selection methods and five acceptance criteria are implemented. The performance of each selection and acceptance mechanism pair is evaluated on 14 well-known benchmark functions and 21 exam timetabling problem instances.