Introduction

Most dictionaries do not include the word timetabling as a single word. It is often listed as either two words (time table) or hyphenated (as time-table). The Oxford English Dictionary defines a timetable as:

A tabular list or schedule of times at which successive things are to be done or happen, or of the times occupied in the parts of some process. spec. a. A printed table or book of tables showing the times of arrival and departure of railway trains at and from the stations; also a similar table of times of arrival and departure of passenger boats or other public conveyances. b. A chart used in railway traffic offices, showing by means of cross lines, in one direction representing hours and minutes and in the other miles, the position of the various trains at any given moment. c. A time-sheet on which a record is kept of the time worked by each employee. d. A table showing how the schedule of a school or other educational institution, for any day, or for a week, is allotted to the various classes and subjects. e. Mus. A table of notes showing their relative time value.

The Oxford dictionary also defines the verb time-table as “To schedule, to plan or arrange according to a timetable, to include in a timetable. Hence time-tabled and timetabling.”

Professor Anthony Wren, at the first Practice and Theory of Automated Timetabling (PATAT) conference in Edinburgh, 1995, defined timetabling as “the allocation, subject to constraints, of resources to objects being placed in space-time, in such a way as to satisfy as nearly as possible a set of desirable objectives. Examples are class and examination time-tabling and some forms of personnel allocation, for example manning of toll booths subject to a given number of personnel.” In the latter case, the process is defined in terms of developing timetables for each individual employee.

In other words: timetabling involves deciding when events/activities will take place in time; but it does not involve assigning resources to those activities. For example, a bus timetable for a particular metropolitan bus route may require “one bus to leave the main terminal every 30 minutes between 6:00 am and 11:00 p.m.; and every 10 minutes during rush hours 7:00 am to 9:00 am and 4:00 p.m. to 6:00 p.m.”. The time table does not specify which buses or drivers should be allocated to each trip. In course timetabling, the objective is to decide what day and time each section of each course should be held. It does not specify which students will be assigned to each section.

Normally, when one sees the word timetabling in an operations research context, people are referring to problems relating to timetabling of courses or examinations in a school. Furthermore, it refers to the concept of developing algorithms, usually computer programs, for the automatic construction of time-tables. There are a number of other related problems in timetabling which will be described; but they are often referred to under different titles. As described by McCollum and Burke (2010) in the Preface to the Proceedings for PATAT 2010, “computer-aided timetable generation … includes personnel rostering, school timetabling, sports scheduling, transportation timetabling and university timetabling.”

Timetabling can also be described as a subset of the larger discipline called scheduling. One can define scheduling as the more general problem of determining the times for activities and assigning the necessary resources. In some cases, for example in Sports Time tabling, once it is decided when a match will occur between a pair of teams, (and who the home team is), all major resources have already implicitly been assigned (the two teams and the stadium). Hence Sports Time tabling is commonly referred to as Sports Scheduling. In this case, the terms are justifiably interchangeable.

It will be frequently distinguished between feasibility and optimality. A feasible solution is any solution that satisfies all of the constraints. An optimal solution is the (possibly unique) solution among all feasible answers which maximizes (minimizes) some objective function. In some timetabling problems, it is sufficient to find a feasible solution.

Examination Timetabling

Examination Timetabling is the simplest timetabling problem to describe, although it is not always easy to solve. The basic problem is to assign examinations to a limited number of available periods in such a way that there are no conflicts or clashes. That is, no student is required to write two examinations at the same time. The problem is closely related to the graph coloring problem. Each examination is represented by a node. Two nodes are connected by an edge if there is at least one student who is required to write the two corresponding exams. The graph coloring problem asks the question: Can the nodes of this graph be colored using p colors such that no two nodes with the same color are connected by an edge? If each color represents an examination period, and if p is the number of periods available, then coloring the graph is equivalent to finding a conflict free assignment of exams to the available periods.

In practice, the basic feasibility issue may be the critical problem. In particular, for any given problem instance, there is a minimum number of periods required to allow a feasible solution. In graph theory terminology, this is called the chromatic number of a graph. If the number of periods provided is close to the theoretical minimum, then you need an algorithm that concentrates on finding a feasible solution. There has been considerable research on good coloring algorithms. Given plenty of periods, it is easy to find a conflict free timetable. The coloring problem is trivial, and efforts can be focused on searching for a good answer using some secondary objectives. Without enough periods, it is not possible to find a feasible solution, and the objective must be changed to something like minimize the number of student conflicts.

The most common secondary objective is to try to spread each student’s exams as evenly as possible. Each institution will impose a variety of additional constraints on the basic model such as:

  • Some exams may have precedence constraints (e.g., “exam A must precede exam B”);

  • Some exams must be consecutive (e.g., “exam C must immediately precede exam D”);

  • Some exams are excluded from certain periods;

  • Limited available rooms and/or seats; and

  • There may be special resource requirements.

For a more comprehensive description of the exam timetabling problem and a survey of practical approaches, refer to Carter (1986), and Qu et al. (2009).

School Timetabling

Class-Teacher timetabling is normally associated with high schools or elementary level schools where the students are grouped into a set of classes and each class has a set of courses that it must take. Professor Dominique de Werra (1985) defines the basic class-teacher model in the following terms. Let C = {c1, c2, …, c m } be a set of classes and T = {t1, t2,…, t n } be a set of teachers. An n × m requirements matrix, R = {r ij } is given where r ij is the required number of times class c i must meet with teacher t j . In the basic model, it is assumed that all lectures are the same length (say one period). Given a set of p periods, the problem is to assign each meeting to some period such that no teacher (and no class) is involved in more than one meeting at a time. The basic problem has no objective function, so the issue is simply to find a feasible solution.

It can be shown that this problem is easy to solve (in the computational complexity sense) in that there exists a polynomial algorithm to find a solution (using a matching algorithm) under the simple and obvious conditions that no teacher (or class) is required to attend more than p periods. The problem remains easy if the basic model is extended to include assigning meetings over a week, where limits are imposed on the number of times each class-teacher pair can meet on any one day.

Unfortunately, most practical problems will have a few extra conditions, and the problem quickly becomes computationally intractable (NP-Complete). For example, if it is assumed that some of the teachers (and/or classes) are not available in every period, then the problem is no longer easy. This is also true if the teachers and classes are available every period, but some of the meetings have been preassigned to specific periods. Another common complication is that some meetings are for more than one period. For example, some meetings may require two or three consecutive periods.

The problem is also often complicated by adding room availability constraints. For example, there may be certain meetings (science, physical education, music, etc.) which require specific rooms. This problem can be expressed using a three dimensional requirements matrix that specifies the number of meetings between class i and teacher j in a room of type k, where there are a limited number of each type of room. This problem is also NP-Complete. Refer to Kingston (2008) for more details.

Course Timetabling

Course timetabling is normally associated with universities, and involves the assignment of sections of courses (lectures, laboratories, tutorials, seminars, etc.) to specific days of the week and times of day. In the course-timetabling problem, unlike the class concept, each student selects a set of courses personally tailored to their own needs. (In practice, many students will have very similar selection patterns.) The primary objective is often to find a timetable that minimizes the expected number of student conflicts.

Strictly speaking, based on the definition given here, course timetabling does not include the assignment of resources (teachers, rooms, special equipment, or even students). In many practical instances, most teachers will be assigned to teach specific course sections before timetabling, while rooms, special equipment and students are assigned after time-tabling. In large schools, many of the courses will be offered in more than one section. Students must be divided up into (roughly equal) groups and assigned to separate sections. This problem is referred to as sectioning or student scheduling. Some packages have been designed to attack all of these problems simultaneously. However, due to the large number of variables involved, most practical methods approach the problems sequentially. The basic course-timetabling problem will be described here. The interested reader can refer to Lewis (2008) for a more detailed discussion of each of the subproblems, and references to practical applications.

The basic course-timetabling problem usually includes a number of side constraints. Courses and course sections should be spread in a particular way throughout the week. For example, an institution may require that all sections of the same course be timetabled at the same times. A course may be divided into multiple meetings (two or three times per week), and there may be restrictions on the meeting patterns that can be used (e.g., Mon., Wed., Fri. at 9:00 a.m.). Some schedules include an allowance for lunch periods, travel time between classes, and the number of hours per day for students and teachers.

In practice, there are two main variations of the course-timetabling problem: the master timetable approach, and the demand driven system. Practitioners typically feel very strongly about their preference for one or the other. Under a master-time-tabling system, the institution will first create a course timetable, and then students register for courses (after consulting a list that describes when each class is offered). The term master timetable refers to the common practice of starting this year’s timetable based on the previous year, and making any required changes based on revisions to course offerings. With a demand driven timetable, the institution posts a list of (proposed) course offerings without any times, and students pre-register for courses before timetabling is performed.

The main advantage of a demand driven system is that the timetable can be constructed using actual student course requests. With a master-timetable system, the timetable must be developed without knowing what the students really want or need. Individual department timetable representatives try to build a timetable that will work for students in their own program in each year. This is very difficult unless the programs are highly structured. In more flexible environments, students often have difficulty selecting the credits that they need without conflicts. A major problem in the U.S. today is that students in many institutions find it impossible to complete their program in the nominal program length due to timetable issues.

There are several disadvantages of a demand-driven system. It requires additional data collection effort, since students must pre-register for courses (typically 4–5 months before term starts) and then, when they get the results of their requests, they start making changes in a second round. In a master-timetabling system, students should be able to construct a conflict free timetable on the first attempt. A demand-driven system also puts fairly tight time constraints on the timetabling process. In a master timetable system, the institution can construct the timetable a year in advance, and some schools publish the times in the course calendar. In a demand-driven system, the students submit course requests a few months before the term starts, and all of the timetabling activity is compressed.

One of the curious issues in the timetabling problem creates a bit of a paradox in the demand-driven system when courses are taught in multiple sections. You cannot assign students to sections (conflict-free) until you have timetabled the sections; but, you cannot timetable the sections until you know which students are in each section. One solution is to assign students to a specific section in advance of timetabling, for the purpose of finding good times. These assignments can be re-evaluated in the student scheduling phase at the end.

Anyone interested in timetabling should refer to the Web site maintained by the University of Nottingham, on automated scheduling, optimisation and planning.

There are a number of other (less common) problems that share the basic timetabling structure. Sports timetabling is the problem of trying to find a rotation for a set of teams such that each team can play every other team twice (once at home and once away). If there are no side constraints, there are some elegant solutions related to tournaments, including a mathematical construction based on permutations (see survey by Kendall et al. 2010). There has also been some research on Employee Timetabling/Rostering, where you want to determine shift work patterns for employees in order to meet a given demand pattern. A particular well-studied variation on this problem is the nurse-rostering problem (see review by Burke et al. 2004).

See

Computational Complexity

Graph Theory

Higher Education

Scheduling and Sequencing

Sports