Abstract

University timetabling (UTT) is a complex problem due to its combinatorial nature but also the type of constraints involved. The holy grail of (constraint) programming: "the user states the problem the program solves it" remains a challenge since solution quality is tightly coupled with deriving "eective models", best handled by technology experts. In this paper, focusing on the eld of university timetabling, we introduce a visual graphic communication tool that lets the user specify her problem in an abstract manner, using a visual entity-relationship model. The entities are nodes of mainly two types: resource nodes (lecturers, assistants, student groups) and events nodes (lectures, lab sessions, tutorials). The links between the nodes signify a desired relationship between them. The visual modeling abstraction focuses on the nature of the entities and their relationships and abstracts from an actual constraint model.

Introduction

University timetabling (UTT) is a complex problem due to its combinatorial nature but also the type of constraints involved. Several approaches have been proposed to solve timetabling problems for specic instances using several approaches, e.g. [5,3,1]. One of the shortcomings of the current constraint-based systems is the existence of modeling tools/languages to express constraint problems. Several approaches have been proposed to over- come these problems. A lot of work has been invested to propose languages that allow the spec- ication of a combinatorial problem at a high level of abstraction, e.g. [2]. Alternatively, visual modeling languages have been proposed to generate constraint programs from visual drawings, e.g. [4]. In general, the visual drawings correspond to constraint graphs where the nodes describe the variables of the problem with their associated domains and the edges correspond to the constraints between each pair of variables. The constraint graphs provide a visual counterpart to constraint satisfaction problems. However, in practice they are intractable for real world problems even if abstraction is introduced into the constraint graph.

In this work, we propose an orthogonal approach where the user models the constraint problem visually by drawing a graph that denes the available resources and the tasks to be scheduled. The graph does not describe the constraints explicitly. It consists of nodes and links, where the nodes are mainly of two types: resource nodes (lecturers, assistants, student groups) and events nodes (lectures, lab sessions, tutorials). The links describe relationships between the nodes. Depending on the type of node, the semantics of the links is determined. This approach enjoys three main properties: 1) the problem is stated at a high level in a constraint and variable free manner, 2) online preliminary consistency checks of proposed links are possible thanks the rich semantic carried by the nodes, 3) a compilation into an eective constraint pro- gramming model including global constraints is performed using the properties of the nodes and specied links.

Our system was built in Java and compiled into SICStus Prolog. Tests were run to build a complete timetable for the German University in Cairo (GUC) including over 200 events to be scheduled and over 400 resources in 3 minutes.

This paper is organized as follows. In Section 2, we present the GUC timetabling problem. In Section 3, we describe how the problem can be modeled as a constraint satisfaction problem. arXiv:1109.6112v1 [cs.AI] 28 Sep 2011Section 4 presents the visual graphic communication tool for generic timetabling problems.

In Section 5, we address additional problem components that are particular for the GUC. In Section 6, we discuss the scalability and the modularity of the approach. Finally, we conclude with a summary and directions for future work.

2 GUC Timetabling

The GUC consists of four faculties. Each faculty oers a set of majors. Currently at the GUC, there are 140 courses oered and 6500 students registered for which course timetables should be generated every semester. There are 200 sta members available for teaching. Each faculty oers a set of majors. For every major, there is a set of associated courses. Faculties do not have separate buildings, therefore all courses from all faculties should be scheduled taking into consideration shared room resources.

Students registered to a major are distributed among groups for lectures (lecture groups) and groups for tutorials or labs (study groups). A study group consists of maximum 25 students. In each semester, study groups are assigned to courses according to their corresponding curricula and semester. Due to the large number of students in a faculty and lecture hall capacities, all study groups cannot attend the same lecture at the same time. Therefore, sets of study groups are usually assigned to more than one lecture group. For example, if there are 27 groups studying Mathematics, then 3 lecture groups will be formed.

The timetable at the GUC spans a week starting from Saturday to Thursday. A day is divided into ve time slots, where a time slot corresponds to 90 minutes. An event can take place in a time slot. This can be either a lecture, tutorial, or lab session and it is given by either a lecturer or a teaching assistant. Lectures are given by lecturers and tutorial and lab sessions are given by teaching assistants (TA). In normal cases, lectures take place in lecture halls, tutorials in exercise rooms and lab sessions take place in specialized laboratories depending on the requirements of a course. In summary, an event is given by a lecturer or a teaching assistant during a time slot in a day to a specic group using a specic room resource. This relationship is represented by a timetable for all events provided that hard constraints are not violated. These constraints cannot be violated and are considered to be of great necessity to the university operation. The timetable also tries to satisfy other constraints which are not very important or critical. Such constraints are known as soft constraints that should be satised but may be violated. For example, these constraints can come in form of wishes from various academic sta.

Some courses require specialized laboratories or rooms for their tutorials and lab sessions. For ex- ample, for some language courses a special laboratory with audio and video equipment is required. The availability of required room resources must be taken into consideration while scheduling. Some lecturers have specic requirements on session precedences. For example, in a computer science introductory course a lecturer might want to schedule tutorials before lab sessions. Furthermore, some constraints should be taken into consideration to improve the quality of edu- cation. One of the constraints requires that a certain day should have an activity slot for students, and a slot where all university academics can meet. For those slots no sessions should be scheduled. A study group should avoid spending a full day at the university. In other words, the maximum number of slots that a group can attend per day is 4. Therefore, if a group starts its day on the rst slot, then it should end its day at most on the fourth slot. Furthermore, though the university runs for 6 days a week each study group must have at least two days o which means that a study group can only have sessions for ve days a week.

A certain number of academics are assigned to a course at the beginning of a semester. Teaching assistants are assigned to one course at a time. For courses involving lab and tutorial sessions, a teaching assistant can be assigned to both or just one of them. This should be taken into consider- ation when scheduling to avoid a possible clash. Furthermore, the total numbers of TAs assigned to a session should not exceed the maximum number of assistants assigned to the corresponding course at any time. A lecturer can be assigned to more than one course. This should be considered when scheduling in order to avoid a possible overlap. Academics assigned to courses have a totalnumber of working and research hours per day and days o that need to be considered when scheduling. Courses should be scheduled in a manner such that the number of session hours given by an academic should not exceed his or her teaching load taking into consideration days o.