$2$ Problem definition

The basic features of CB$-$CTT are presented in the ITC$2007$ web site and in the corresponding technical report $($Di Gaspero et al$.2007).$ However, the model has to be extended in order to include the features related to the addition components. In order to make this paper self$-$contained, we present here the full model. The problem consists of the following basic entities:

Days, Timeslots, and Periods. We are given a number of teaching days in the week $($typically $5$ or $6).$ Each day is split into a fixed number of timeslots, which is equal for all days. A period is a pair composed of a day and a timeslot. The total number of scheduling periods is the product of the days times the day timeslots.

Courses and Teachers. Each course consists of a fixed number of lectures to be scheduled in distinct periods, it is attended by a given number of students, and is taught by a teacher. For each course there is a minimum number of days that the lectures of the course should be spread in$,$ moreover there are some periods in which the course cannot be scheduled.

Rooms. Each room has a capacity, expressed in terms of number of available seats, and a location expressed as an integer value representing a separate building. Some rooms may not be suitable for some courses $($because they miss some equipment$).$

Curricula, A curriculum is a group of courses such that any pair of courses in the group have students in common. Based on curricula, we have the conflicts between courses and other soft constraints.

Curricula are published by the university in the Student Guide. However, the information published in the guide is usually expressed in terms of mandatory and optional courses. In order to obtain the curricula in the form proposed here, some preprocessing is necessary. In particular, the person responsible for the timetabling, mainly based on experience of previous years, has to divide optional courses in groups that are normally taken together by the students. Each group of optional course, together with the mandatory ones, forms a curriculum in our meaning.

The solution of the problem is an assignment of a period $($day and timeslot$)$ and a room to all lectures of each course.

We split the cost components into two sets: the basic ones, which belong to all formula$-$