Constraints

The quality of an automatically constructed timetable is measured by how convenient it is for the involved individuals and by how well it utilizes the available resources. The parameters which define these criteria are called Constraints.

There are many kinds of constraints which the program supports and we have, in fact, already seen some of them in the previous chapters. That's because some constraints are fundamental and are taken under account even during the interactive timetabling process whereas others are optimizational constraints and are considered by the software only during the automatic construction.

But before we get to the new type of constraints, let's go over the ones we have learned about in the previous chapters so that we have a clear list of all the constraints which are considered during automation in one place.

Fundamental Constraints

All the constraints in this chapter are considered during automation, but the ones that are listed in this section were entered in the "Timetable" tab (as explained in previous chapters) and not in the "Constraints" tab. Let's get a reminder of what they were.

Note: All the constraints described in this section are considered as mandatory constraints by the software in the Automatic mode. The program will never suggest a timetable in which any of these requirements is not met.

Length Of Activity

As you remember, each activity can be assigned a Length attribute in the activities' list:

Constraint activity length turbo8.png

The length is the number of periods the activity should occupy consecutively each time it is scheduled. In the Interactive mode, when you drag-and-drop an activity with a length of "2", for example, into the timetable, you will be dragging a two-cell activity. In the Automatic mode, the program does exactly the same thing - it always schedules such an activity on 2 consecutive periods.

Constraint length turbo8.png

Multiple Resources Per Activity

Another important reminder: each activity can involve multiple resources of the same type (by placing a check mark near all these resources when you are filling in the activity's properties):

Constraint activity 2 teachers turbo8.png

For example, one activity can involve two teachers; or three groups; or two teachers and three groups. Such an activity will appear in all the involved resources' timetables and will only be scheduled at a time slot when they are all free.

Constraint multiple resources turbo8.png

Simultaneous Activities

Sets make it possible to bundle together several separate activities which need to be scheduled at the same time. Sets are created in the activities' list and stand out from the rest of the activities by having a color and a folder-like shape:

Constraint set simultaneously turbo8.png

Each activity in a Set can involve different resources such as groups and teachers, yet when they are united into a Set, they become one inseparable unit and are always scheduled simultaneously by the automatic engine.

Constraint simultaneously turbo8.png

Multiple Possible Rooms Per Activity

Naturally, when an activity can be scheduled in several possible rooms, it gives the program more flexibility during the automatic timetabling. As described before, the potential rooms in which an activity can be scheduled can be listed in the activity's Room property, while changing the inscription at the bottom of the list from "All the selected resources" to "Any of the selected resources":

Constraint activity room selection turbo8.png

When an activity has several possible rooms as above, the program will automatically choose one of them during the timetable construction. Note that different cells of the same activity may be scheduled in different rooms.

Constraint room selection turbo8.png

Quantity Of Equipment In Stock

As you remember, the total number of items of a certain kind of equipment in stock is defined in the equipment's properties:

Constraint resource equipment quantity turbo8.png

This quantity creates a limit on the number of activities which use that equipment that can be scheduled at the same time slot. For example, suppose an activity requires a single projector:

Constraint activity equipment turbo8.png

In such case when there are only 2 projectors available in stock, the program will never be able to schedule 3 activities which require a single projector at the same time slot.

Constraint equipment quantity turbo8.png

Double Booking

Needless to say, that teachers, students and groups cannot be double booked (that is unless they are intentionally part of a Set). This may sound obvious, but we are reminding this because it is actually one of the most constraining aspects of timetabling.

Constraint double booking turbo8.png

Times of Unavailability

As explained in the Interactive Timetabling chapter, the days and periods at which a resource (or an activity) are not available for scheduling can be blocked out by selecting the relevant cells and choosing "Edit", "Block" in the main menu. A resource's blocked cell prevents the program from scheduling any activities which involve that resource at that cell.

Constraint unavailability turbo8.png

Fixated Cells

An activity that is scheduled in the interactive mode and fixated (by selecting "Edit", "Fixate" in the main menu), will not be "touched" during the automation. This is very useful when you know in advance that a certain activity must take place at a certain day and period or when you think that would be the best way to schedule it.

Constraint fixated cells turbo8.png

Optimizational Constraints

Now that we got a reminder of the software's fundamental constraints, we can explore the constraints which are used to optimize the timetable. Each kind of constraint is responsible for a different aspect of the timetable. Let's go over their types and understand what each one means.

Cells Per Day

The constraint Cells per day sums up the number of scheduled cells on one day in some resource's timetable:

Constraint cells per day turbo8.png

There are two common use cases for this constraint. One, it allows you to spread the activities evenly across the week. For example, suppose a teacher has 10 activities to be scheduled; by setting the maximal cells per day to "2", you can force the program to schedule the teacher's activities on all 5 days because no day would be permitted to have more than 2 scheduled activities.

The second use case is related to subjects. It allows you to make sure a subject is not scheduled too many times on the same day in any group's timetable. For example, given that "Physical Education" needs to be scheduled 3 times a week, we don't want it to be scheduled more than once a day. This is accomplished by setting the maximal cells per day for the subject "Physical Education" to "1".

Gaps

A Gap is a free cell in the middle of the day, before which there is some activity scheduled and after which there is also some activity scheduled:

Constraint gaps turbo8.png

The number of gaps on any single day is summed up by the "Gaps per Day" constraint and the total number of gaps during the entire week is summed by the "Gaps per Week" constraint. There is one additional constraint related to gaps which is called "Gap Size" which sums up the number of consecutive free cells and allows to limit that number.

The most common use case for constraining the number of gaps is to prevent idle time in between activities for teachers, groups and students. For example, if a teacher is scheduled on the 1st period and then only on the 7th period, he/she has 5 gaps (5 idle periods). On many occasions this may be uncomfortable for the teacher. In such cases, by setting the maximal number of gaps per day to 2, for example, the program will be encouraged to schedule all the teacher's activities no more than 2 idle periods apart.

Late Starts

A Late Start is a free cell or a series of several free cells at the beginning of the day. There are no scheduled activities before a late start but there are activities scheduled after it. For example, if a teacher does not teach anything on the 1st period, but has an activity scheduled on the 2nd period, he/she has a "Late Start".

Constraint late starts turbo8.png

We have two types of constraints here: "Late Starts per Week" which sums up the number of free cells a resource has at the beginning of a day throughout the entire week, and "Late Start Size" which sums up the number of consecutive free cells at the beginning of any day. The first constraint makes it possible to limit the number of times a resource starts his/her day later than the 1st period (e.g. no more than 3 late starts per week) and the second one to limit the length of the allowed late start (e.g. no more than 2 periods).

Period Range

This constraint allows you to specify the range of periods on which a resource or an activity should be scheduled. For example, to tell the program that a resource's activities should be scheduled only on periods 1-4, you can enter "1" as the minimal value for that constraint and "4" as the maximal value.

Constraint period range turbo8.png

Note: If the periods in your school start from "0" or are named differently than "1", "2", etc., you still need to enter positive numbers as the constraint minimum/maximum values. That's because after you enter a number, the program maps that number to the relative period's number. For example, "1" is mapped to the first period in the list, "2" to the second period and so on.

Consecutive Cells

This constraint sums up the number of consecutive periods at which any activity is scheduled:

Constraint consecutive cells turbo8.png

The most common use case for this constraint is to limit the maximal length of a series of activities in some resource's timetable. For example, by setting the maximal value of some teacher to "3" you can ask the program that the teacher is not scheduled for more than 3 consecutive periods in a row. In such case the program would be forced to leave a free period after the 3rd cell.

Entry of Constraints

The optimizational constraints are entered in a dedicated tab named "Constraints" which is located at the bottom left corner of the workspace:

Constraints tab8.png

How to select the type of the constraint?

The Constraints tab has a navigation pane at the top. The first selector in the navigation pane is where you choose the type of the constraint while the rest of the buttons allow you to select the type of resources for which you are entering the constraint values:

Constraints navigation pane8.png

After you select a constraint type, you will see a list of all the resources with three columns: "Min.", "Max." and "Desr." ("Desirable"):

Constraints min max desr8.png

What are the Min, Max and Desirable columns?

As we have seen above, a constraint is basically a mathematical formula which counts something. That's why if we look at any resource's timetable from the point of view of a specific kind of constraint, that formula always produces a single number. For example, if we are counting the number of weekly gaps in some resource's timetable we will come up with a number. Of course, each resource's timetable will produce a different number. That's why when we are defining the constraints, we will be defining different limits for each resource.

Since every constraint's formula produces a number, what is left for us to do is to put a limit on that number. Once we do, the program will aspire to generate a timetable in which all these limits are satisfied. We can define 3 types of limitations: minimum, maximum and a desirable value (or several desirable values). The minimum and maximum values are hard limitations (have higher priority) whereas the desirable value is a soft limitation (has lesser priority). It is not required to enter all the 3 values if not necessary.

To enter a value, just type it in one of these fields. All fields are optional so you can type only a minimum, or only a maximum or minimum and desirable etc.:

Constraints enter value turbo8.png

How to enter several Desirable values?

The Desirable ("Desr.") column allows you to enter one or more desirable values. A desirable value has a lesser priority than the values defined by the Min/Max range. This means that if the program considers a way to improve the timetable in order to reach a desirable value on the account of breaking another constraint's Min or Max value, this option will not be applied. However, the desirable values do allow you to tweak the timetable's quality to a greater extent by providing you with a way to enter "nice to have" requirements.

The program supports not only a single desirable value, but also a range of values. This is accomplished by using a comma or a dash to specify multiple values. For example, suppose a certain subject should only be scheduled on periods 2-8, but the preferred periods are 3, 4, 5 and 7. To define this you can set the "Period Range" constraint for that subject to have a Min value of "2" and a Max value of "8", and in the Desirable field type: "3-5,7":

Constraints multiple desirable values turbo8.png

How to prioritize critical constraints?

There are 3 constraint priorities: "critical", "required" and "desirable". By default, the critical constraint is only the "scheduling" constraint, meaning that it is considered critical for the program to schedule 100% of the activities. The required constraints are the Min/Max values that you enter in the constraints list and the desirable are the values that you enter in the Desirable column in that list.

There is, however, a way to turn any "required" constraint into a "critical" constraint. This makes it clear to the program that it is absolutely vital to take care of that constraint – even in a higher priority than scheduling any other remaining activities. In a way, this affects the decision making process of the program during the automatic phase because the program does not even consider solutions in which that critical constraint is violated. In order to turn a "required" constraint into a "critical" constraint, you need to append the "!" symbol to the value in the Min or Max columns:

Constraints critical priority turbo8.png

What does the Violation column mean?

If you click the Constraints tab while being in the Automatic mode, you will see an additional column next to the Min/Max/Desirable columns, named Violation ("Viol."). A value will appear in this column only for constraints which are unfulfilled (violated) in the current timetable. In such cases the value in this column will show either a negative or a positive number which indicates the difference between the value of the constraint in the current timetable and the nearest required (or desirable) value.

For example, if we set the maximal number of gaps per week to "3" for some teacher, yet the current timetable has 5 gaps, the Violation column for that teacher will have the value "+2", meaning that there are 2 gaps more than what was required. Another example – if the minimal number of cells per day for a group was set to "5" but the current timetable of that group has only 1 cell on each day of the 5-day week, the violation column will contain the accumulated value of "-20" because on each of the 5 days 4 cells are currently missing.

In case the violation is of the min/max range, it will be shown in a red color. If it's a violation of the desirable value, it will be displayed in an orange color:

Constraints violation column turbo8.png

Is it possible to modify constraints later?

It's important to emphasize that even if the timetable is already partially or almost fully constructed, you always have the option to modify the existing constraints (or add new ones) and then run the automation from that point. The program knows how to take the existing timetable as a starting point and automatically make the necessary adjustments to have it fulfill the constraints that you have modified.

In fact, this ability can be used as a useful technique to construct the timetable gradually because you can run the automatic engine multiple times. The reason this can be useful is because it is often very difficult to enter all the constraints correctly from the beginning. You may well find yourself looking at the resulting timetable after the first phase and saying something like "Oh, this also needs to be like this and that". In such cases you can always go back to the constraints entry and enter the additional constraints; or, you can make a manual change in the interactive mode, fixate it, and then run the automatic solver again. Doing these steps several times until completion is actually the recommended method of achieving the highest quality timetable.

How to prevent over constraining?

One last thing which is important to understand about constraints is how to avoid misusing them. You see, constraints are really a very delicate matter. Imagine that you have entered plenty of constraints into the program, and some are indeed important to you yet some are negligible or worse yet – totally unrealistic. If it were you constructing the timetable manually and gradually, you would have undoubtedly made the right decisions as you went along in order to satisfy the critical constraints as first priority. The automatic solver, on the other hand, does not possess your judgment logic. Its process of decision making is 100% based on the constraints that you have entered. If the solver faces a logical "junction" in which it needs to decide whether to make a change in the timetable in order to satisfy one constraint, but that change breaks another constraint (and they are both defined as Min/Max constraints, i.e. both have the same priority), the program will refrain from making that change (because it would seem disadvantageous to the program). If both constraints are indeed required, that is certainly the desired behavior. If, however, one of them isn't really necessary, we have a case of over constraining here which damages the program's ability to make the right decisions for you. So when you are entering constraints, please make sure to enter only the required and realistic constraints in the Min/Max values while using the Desirable value for the lesser priority "nice to have" constraints.

Next chapter: Automatic Timetabling.

 HAVE A QUESTION? EMAIL US: CONTACT@LANTIV.COM