The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
In 1986, Carter published a survey of papers on practical examination timetabling, in the intervening years, there have been a number of new applications, and several innovative techniques have been attempted. In this paper, we will classify the algorithms, discuss their reported results and try to draw some conclusions on the state of the art. We have not attempted to perform any experimental comparisons...
During the last five years a peak of interest has been observed in the problems related to computer-aided timetabling. The most recent works in this area are based on the application of modern information technologies. Here the main directions of modern research and design are reviewed. A classification is proposed for academic timetabling problems, requirements for the timetables, mathematical models,...
Computer solution of timetabling, scheduling and rostering problems has been addressed in the literature since the 1950's. Early mathematical formulations proved impossible to solve given the limited computer power of the era. However, heuristics, often very specialised, were used for certain problems from a very early date, although the term heuristic was not generally recognised until later; a few...
This paper describes the results of a questionnaire on examination timetabling sent to the registrars of ninety five British Universities. The survey asked questions in three specific categories. Firstly, universities were asked about the nature of their examination timetabling problem: how many people, rooms, periods are involved and what difficulties are associated with the problem? Secondly, we...
Employee timetabling problems (ETP) usually involve an organization with a set of tasks that need to be fulfilled by a set of employees, each with his/her own qualifications, constraints and preferences. The organization usually enforces some overall constraints and attempts to achieve some global objectives such as a just or equitable division of work. Examples for such problems are: assignment of...
This paper describes the application of multiple context reasoning and truth maintenance to the automated generation of timetables. The reasoning system used is made up of a rule-based problem-solver which makes inferences and an assumption-based truth maintenance system that maintains a record of the justification of these inferences. While this method has been used for scheduling and planning applications...
The casting of university timetables is a problem which combines classical numerical scheduling techniques with important human considerations. It will be argued here that since the application involves the preferences of humans, the problem is qualitatively different than similar problems involving inanimate objects. The humane and profane facets are combined in this study by using the constraint...
In preparation for the changeover to a new modular degree structure, at the University of Leeds, a new modular timetable for the 1993–94 academic session had to be constructed from scratch. This paper describes our experience in constructing a large scale modular timetable using Constraint Logic Programming techniques.
In this paper, we concentrate on a typical scheduling problem: the computation of a timetable for a German college. Like many other scheduling problems, this problem contains a variety of complex constraints and necessitates special-purpose search strategies. Techniques from Operations Research and traditional constraint logic programming are not able to express these constraints and search strategies...
A software solution based on a genetic algorithm (GA) optimization has been designed for creating a university class timetable. The prototype program has demonstrated the capability to define an acceptable schedule within a maximum stress, minimum resource environment. The constraints imposed in such a complex environment are resolved by the GA assisted by a dynamic penalty function and greedy algorithms...
In this paper we describe a heavily constrained university timetabling problem, and our genetic algorithm based approach to solve it. A problem-specific chromosome representation and knowledge-augmented genetic operators have been developed; these operators ‘intelligently’ avoid building illegal timetables. The prototype timetabling system which is presented has been implemented in C and PROLOG, and...
In this paper, the development and implementation of a university examination scheduling system, based on a genetic algorithm, is described. The system has been used for scheduling examinations in two real instances so far at Middle East Technical University, involving 682 exams in one case and 1449 exams in the other. The methods employed are described including two adaptive mutation operators that...
Some evolutionary algorithm (EA)/timetabling researchers find benefit from combining an EA with graph-colouring based greedy algorithms, while others opt for a simpler but faster method. We consider a combination of the two approaches, largely retaining the speed of the simpler method while adopting the greedy method to bootstrap the process. In this combination, the initial population is produced...
The scheduling of exams in institutions of higher education is known to be a highly constrained problem. The advent of modularity in many institutions in the UK has resulted in a significant increase in its complexity, imposing even more difficulties on university administrators who must find a solution, often without any computer aid. Of the many methods that have been applied to solving the...
This paper describes work in progress to increase the performance of a memetic timetabling system. The features looked at are two directed mutation operators, targeted mutation and a structured population that facilitates parallel implementation. Experimental results are given that show good performance improvements with directed and targeted mutation, and acceptable first results with the structure...
This paper describes the experience of using an automatic timetable generation system, based on a memetic algorithm, to produce working timetables for a large department that offers a range of undergraduate and postgraduate courses attended by some 500 students. The automatic algorithm is supported by a records system which permits manual data collection and editing, viewing and printing of timetables...
This paper shows that timetable construction is NP-complete in a number of quite different ways that arise in practice, and discusses the prospects of overcoming these problems. A formal specification of the problem based on TTL, a timetable specification language, is given. Specificially, we show that NP-completeness arises whenever students have a wide subject choice, or meetings vary in...
Timetabling problems have often been formulated as coloring problems in graphs. We give formulations in terms of graph coloring (or hypergraph coloring) for a collection of simple class-teacher timetabling problems and review complexity issues for these formulations. This tutorial presentation concludes with some hints on some general procedures which handles many specific requirements.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.