Track:
All Papers
Downloads:
Abstract:
In most schools and colleges, producing a timetable is a task that is dreaded by those charged with annually creating it. In schools in particular, it can be difficult to produce any solution at all because teaching resources are usually stretched to the limit. This situation is made more difficult by the fact that the person making up the timetable must not only produce a valid solution but one that is of good quality. A large number of judgmental factors are involved in producing a good-quality timetable. Some of these are educational (for example, it is undesirable for a group of pupils to have a Spanish lesson immediately following a German one), others pertain to the work conditions of the staff (for example, the teaching load should be distributed evenly through the day so that no teacher has a long, contiguous block of lessons), and others are political (for example, a senior teacher should not end up with fewer free periods than a more junior one). These qualitative factors make an already difficult problem time consuming indeed. For a medium-sized school (about 1,000 pupils), even a veteran at the task takes several weeks to produce a satisfactory timetable. Despite this great investment in time and concentration, the timetable will inevitably contain errors, such as requiring a teacher to be in two places at once. Tight resources, together with the need to juggle many qualitative factors, means that the person creating the timetable only has one shot at producing a solution: The timetable is effectively set in concrete and is only amenable to minor modification. Because of the time-consuming nature of manually producing a timetable, there is no opportunity to try alternative scenarios that might enable cost savings or late extensions to the curriculum. With the advent of greater access to digital computers, attempts began in the seventies to solve this problem by computer. Given the difficulty of manually producing a timetable, one would expect a computer-based timetable program to be a godsend. Early computer-based timetable programs ran on mainframe computers: The school would send its requirement to the administrative center, which would enter the data and run the timetable program overnight. The resulting timetable was usually unsatisfactory because it violated constraints that were important to the school. As a result, school timetable programs got a bad name for themselves. As far as schools were concerned, computers were incapable of producing a solution of the quality achieved by humans performing the same task. Previous timetable systems have been based on operations research techniques. Although able to generate solutions, the main failing of this approach is the lack of control available to the user. The only way to alter the solution is to change some of the numeric parameters that control the priority of the various factors. This approach is fairly hit or miss because it is never clear what effect altering some numeric value will have on the overall solution. Based as they are on mathematical programming methods, such timetable programs are difficult to control because their processing is completely opaque to the user. In contrast, ai approaches to problem solving are characterized by their reliance on symbolic, rather than numeric, methods. This technique makes it much easier for a program to communicate its problem-solving rationale to the user. The application of ai to scheduling has a relatively short history, only starting to gather momentum in the mid-eighties (for example, Fox and Smith [1984] and Keng, Yun, and Rossi [1988]). Constraint-satisfaction problem techniques (in particular) seem to offer a powerful way of solving scheduling problems (compare Dincbas, Simonis, and Van Hentenryck [1988] and Keng and Yun [1989]). syllabus uses a constraint-satisfaction problem approach to producing timetables, rarely fails to produce a timetable, and can usually detect such cases before it begins scheduling. However, it is common for operations research-based timetable programs to only manage to produce a timetable for some 90 percent of the curriculum, leaving the user to manually insert the remaining lessons. Unfortunately, these lessons are typically the hardest to fit; so, the machine is only solving the simple part of the problem.