A Novel Fuzzy Approach to Evaluate the Quality of Examination Timetabling
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 hig
- PDF / 528,133 Bytes
- 20 Pages / 430 x 660 pts Page_size
- 48 Downloads / 159 Views
School of Computer Science and Information Technology, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB, UK {hba,ekb,jmg}@cs.nott.ac.uk 2 School of Computer Science, Queen’s University Belfast, Belfast BT7 1NN, UK [email protected]
Abstract. 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.
1
Introduction
Timetabling refers to the process of allocating limited resources to a number of events subject to many constraints. Constraints are divided into two types: hard and soft. Hard constraints cannot be violated under any circumstances. Any timetable solution that satisfies all the specified hard constraints is considered to be a feasible solution, provided that all the events are assigned to a time slot. Soft constraints are highly desirable to satisfy, but it is acceptable to breach these types of constraint. However, it is very important to minimise the violation of the soft constraints, because, in many cases, the quality of the constructed timetable is evaluated by measuring the fulfillment of these constraints. In practice, the variety of constraints which are imposed by academic institutions are very different [6]. Such variations make the timetabling problem more challenging. Algorithms or approaches that have been successfully applied to one problem may not perform well when applied to different timetabling instances. E.K. Burke and H. Rudov´ a (Eds.): PATAT 2006, LNCS 3867, pp. 327–346, 2007. c Springer-Verlag Berlin Heidelberg 2007
328
H. Asmuni et al.
Researchers have employed many different approaches over the years in an attempt to generate ‘optimal’ timetabling solutions subject to a list of constraints. Approaches such as Evolutionary Algorithms, e.g. [8, 16, 28], Tabu Search, e.g. [7, 17, 19, 29], Simulated Annealing, e.g. [27], Constraint Programming, e.g. [1, 4, 18], Case-Based Reasoning, e.g. [11, 30], and Fuzzy Methodologies, e.g. [2, 3, 23, 30] have been successfully applied to timetabling problems. Overviews of timetabling approaches are presented in [10, 12, 22, 24, 26]. In 1996, Carter et al. [13] introduced a set of examination timetabling benchmark data. The
Data Loading...
