Skip navigation links

Package org.cpsolver.ifs.example.tt

Simple Timetabling Problem.

See: Description

Package org.cpsolver.ifs.example.tt Description

Simple Timetabling Problem.

Simplified model for timetabling problems consisting of a set of resources, a set of activities, and a set of dependencies between the activities. Time is divided into time slots with the same duration. Every slot may have assigned a constraint, either hard or soft: a hard constraint indicates that the slot is forbidden for any activity, a soft constraint indicates that the slot is not preferred. We call these constraints �time preferences�. Every activity and every resource may have assigned a set of time preferences, which indicate forbidden and not preferred time slots.

Activity (which can be, for instance, directly mapped to a lecture) is identified by its name. Every activity is described by its duration (expressed as a number of time slots), by time preferences, and by a set of resources. This set of resources determines which resources are required by the activity. To model alternative as well as required resources, we divide the set of resources into several subsets � resource groups. Each group is either conjunctive or disjunctive: the conjunctive group of resources means that the activity needs all the resources from the group, the disjunctive group means that the activity needs exactly one of the resources (we can choose from several alternatives). An example can be a lecture, which will take place in one of the possible classrooms and it will be taught for all of the selected classes. Note that we do not need to model conjunctive groups explicitly because we can use a set of disjunctive groups containing exactly one resource instead (the set of required resources can be described in a conjunctive normal form). However, usage of both conjunctive and disjunctive groups simplifies modelling for the users.

Resource is also identified by its name and it is fully described by time preferences. There is a hard condition that only one activity can use the resource at the same time. For instance, such resource can represent a teacher, a class, a classroom, or another special resource at the lecture timetabling problem.

Finally, we need a mechanism for defining and handling direct dependencies between the activities. It seems sufficient to use binary dependencies only that define relationship between two activities. We defined three temporal constraints: the activity finishes before another activity, the activity finishes exactly at the time when the second activity starts, and two activities run concurrently (they have the same start time).

The solution of the problem defined by the above model is a timetable where every scheduled activity has assigned its start time and a set of reserved resources that are needed for its execution (the activity is allocated to respective slots of the reserved resources). This timetable must satisfy all the hard constraints, namely: Furthermore, we want to minimize the number of violated soft constraints in the time preferences of resources and activities. We do not formally express this objective function; these preferences will be used as a guide during the search for the solution.
Skip navigation links