Timetabling is one of the computationally difficult problems in scheduling. In timetabling, the aim is to find suitable time slots for a number of tasks that require limited resources. Depending on the nature of the problem, the constraints in the problem can vary and there may be many different objectives. For example, in some cases the objective may be to minimize the length of the total time period over which the tasks are to be scheduled, in other cases the objective may be to find a feasible solution subject to a fixed total time period and several other constraints. Yet in others the objective can be to find a solution in which least number of constraints are violated. Timetabling problems can arise in many different settings, but generally it refers to the timetabling at educational institutions. The significance of this problem is mainly due to the difficulty of constructing a feasible timetable that satisfies the preferences of the administration, the instructors, and the students. In certain cases, it may be extremely difficult even to find a single feasible solution. It is not possible to formulate a general model that is applicable for all cases, since every educational institution has its own special constraints and objectives. For example, for a secondary school, there should not be any gap between the class meetings, on the other hand this is allowed, and in some cases encouraged, in a university. Timetabling problems can be grouped into two types: Examination and course scheduling problems. Examination scheduling problems deal with assigning the examinations over an examination period subject to several constraints. The objective can be assignment of the examinations to a minimum number of periods without any conflict. In other problems, the number of periods are fixed and the objective is to optimize a preference function that is based on the preferences of the administration, the instructors, and the students. Some of these preferences may be:

Maximizing the time interval between the two consecutive examinations of a student.

Scheduling the examinations with large number of students in earlier time slots, to allow more time for grading.

In course scheduling, the time period is fixed and, in general, it is one week. The objective is to find a course schedule that is feasible with respect to a number of constraints. Course scheduling and examination scheduling problems have both similar and differing characteristics. For example, in both problems a student cannot take more than one examination or attend more than one class meeting at a time. On the other hand, in examination scheduling problems there may not have a fixed time period, however all course scheduling problems are for fixed time periods.

Regardless of the differences among problem types, similar solution approaches are used in all. In this study, the focus is on the course scheduling problem.

In course scheduling problems, some constraints are case specific, but there are some constraints which should be satisfied in every course scheduling problem. These are called hard constraints. For example,

The class meetings of two courses with the same student enrollment cannot be assigned to the same time slot.

An instructor cannot teach more than one class meeting at the same time slot.

The assigned number of class meetings that are scheduled for the same time slot cannot exceed the number of available classrooms.

All class meetings should be assigned to a time slot.

Hard constraints cannot be violated, since violation of any one of them results in an infeasible timetable. On the other hand, there are soft constraints. It is not desirable to violate a soft constraint, but if it is violated, the timetable is still feasible, but not as good as a timetable in which that constraint is not violated. Among such soft constraints are:

An instructor may not want to teach more than, say, four class meetings in a day.

It is undesirable to have a class meeting during the lunch hour.

Students may not want to have class meetings in early and late time slots.

There should be at least one day between the two class meetings of a course.

As mentioned earlier, timetabling problem is computationally very difficult. The basic timetabling problem is reducible to graph coloring problem. Since in 1972, Karp showed that the graph coloring problem is NP-Complete, it consequently follows that timetabling problem is NP-Complete. In addition to this, the varied nature of constraints for each institution makes timetabling problem even more complicated. The next subsection discusses these specific constraints in the case of Bilkent University.

The Course Scheduling Problem at Bilkent University Bilkent is a large university having two campuses, several schools and around ten thousand students. The course scheduling problem is becoming considerably more demanding each year and thus, there is a need to use advanced techniques for course timetabling. At Bilkent, the classes can meet during the weekdays from 08:40 to 17:30. Each day there are nine time slots in which a class meeting can be scheduled. Each meeting lasts 50 minutes with a ten minute break in between classes. So the class meetings start at {8:40, 9:40,$\ldots$,16:40} and end at {9:30, 10:30,$\ldots$,17:30}. A course that requires two time slots is called a 2-hour course. In the similar manner, there are 3-, 4-, and 5-hour courses which requires three, four and five time slots, respectively. Other than the 2-hour courses, all other courses are to be scheduled on two separate days, that is: 3-hour courses One class meeting requires one time slot and the other one requires two consecutive time slots. 4-hour courses Both class meetings require two consecutive time slots. 5-hour courses One class meeting requires two consecutive time slots and the other one requires three consecutive time slots. A course may have several sections depending upon the student enrollment in the course. If a course is to meet on two separate days, then the class meetings cannot be assigned to two consecutive days. For example, if the first class meeting is scheduled on Monday, the second class meeting can be scheduled at the earliest on Wednesday. Each section of a course may have different class sizes ranging from 10 to 65 students. The variety in section sizes requires scheduling of class meetings in an appropriate classroom which has sufficient capacity to accommodate all students. Currently, the classrooms can be grouped into four types based on their capacity: Type-1 classrooms Maximum capacity of 25 students. Type-2 classrooms Maximum capacity of 30 students. Type-3 classrooms Maximum capacity of 40 students. Type-4 classrooms Maximum capacity of 65 students. Thus, as an example, if a section has 35 students, then its class meetings can take place in a type-3 or a type-4 classroom. Although in some other institutions instructor and course section assignments may be done by timetabling programs [3], the number of sections for each course and the instructor of each course section are known in advance at Bilkent. Further more, each course section is reserved for a specific student group. That is, for each course section, the students who can enroll are known in advance. This makes it possible to compute the number of required sections for each course prior to the course scheduling process at each semester. Summing-up, following ten constraints are needed to comply with the conditions and requirements of Bilkent University. All these constraints are treated as if they are hard constraints at Bilkent.

All class meetings will be assigned to a day.

All class meetings will be assigned to a feasible time slot.

Two class meetings belonging to the same course section cannot be scheduled on two consecutive days.

There is a limited daily classroom capacity.

There are limited number of classrooms in each classroom type.

The course sections assigned for specific student groups cannot overlap.

Sections of the courses that are taught by the same instructor cannot overlap.

An instructor cannot teach more than a fixed number of class meeting hours per day.

A student can attend at most eight hours of class meetings per day.

All class meetings should be assigned to an appropriate size classroom.

Allocation of class meetings to days,

Construction of course schedule for each day,

Assigning classrooms to class meetings.

Allocation of Class Meetings to Days

All class meetings should be assigned to a day.

Number of class meeting hours that a student can attend in a day should be taken into account.

Number of class meeting hours that an instructor can teach in a day should be taken into account.

Two class meetings of the same course section should not be scheduled on consecutive days.

Every class meeting on that day should be scheduled to a time slot ensuring that it ends at 5:30 p.m at the latest.

At each time slot, the total capacity requirement of the class meetings for a specific classroom type cannot exceed the available capacity of that classroom type.

Two class meetings taught by the same instructor cannot be scheduled on overlapping time slots.

Two class meetings of a student group cannot be scheduled on overlapping time slots.

Soft and hard constraints are fundamental elements behind not only creating a great timetable, but also a working one. The make up of a timetable (any timetable) consists of a variety of constraints that are either hard or a soft, but what are they? and what is the difference? Let starts with hard constraints, these are the fundamental elements of a timetable that you and the software use to create the timetable and must be abided by. For example, the number of hours in the teaching day is likely to be a hard constraint. If you teach Monday – Friday 09-17:00, then the timetable must ensure that all timetable activities are placed within this time frame. A timetable booking placed on a Thursday at 18:00 or a Saturday at 12:00 will not be of any use, therefore the software and those who use it must abide by this constraint in order to create a working timetable i.e. a hard constraint. Each hard constraint, is an element of the timetable that is equally weighted and must be abided by. Simply put – if they are broken, the timetable will not work. I have provided below the key hard constraints that typically make up a teaching timetable, although there can be more depending on how your institution works!

Number of Teaching Spaces/Rooms – You can only book as many rooms as you have available, if the number of timetable activities outstrips your teaching room availability then you have a problem! The Teaching Week – As discussed, if you have a strict teaching week then there is no use timetabling outside of these times.

Number of Weeks in the Semester – As with the teaching week, there is no use timetabling activities outside of the institutions planned teaching weeks if all etaching actvities must take place within them.

Student Clash Checks – These can be a mixture of both hard and soft constraints, however if a student must attend two lectures then the timetable should recognise that they cannot happen at the same time – i.e. a hard constraint.

Staff Clash Checks – As with students, staff can’t be in two places at the same time therefore again the timetable must recognise this.

Teaching Room Capacity – If a room has a 100 capacity then only 100 students can fit into this room, therefore this is typically a hard constraint. However, there can be some flexibility with this if you can accurately predict a certain percentage will not attend and therefore are willing to allow for example a 5% margin, as this would allow an extra 5 students into this room. Each of these hard constraints is built around the same principles that govern most aspects of our life – space and time. These hard constraints will allow you to create a timetable that works, providing you have resources available to enable you to accommodate the timetable activities within the hard constraints! The soft constraints, are the other side of the coin and are made up of the elements which can turn your timetable from a working timetable into a great timetable. Of course, a “great” timetable is dependent on what you are looking to achieve and what resources you have available but the principle of a soft constraint is that you are putting a constraint into the timetable that will help to improve your timetable and isn’t a necessity. For example, student feedback may indicate that the students want to have an hour lunch break within their timetable during each day of the teaching week. This request isn’t a necessity, but it is a want and therefore you can test to see whether this is feasible by building it into your timetable as a soft constraint. The difference between this soft constraint and a hard constraint, is that the timetabling software (and you) must be able to recognise that if there is no other option (or there is a better option) this constraint can be ignored. 14426528187_e65627fdd6_zWhat do I mean by a better option? Well, one of the fundamental issues with soft constraints is that you are likely to have more than one. For example, students may want to have a lunch hour, but also not have a teaching day exceeding 6 hours, or have more than 4 hours of lectures in a row, plus your staff also don’t want to teach more than three hours worth of activities in a row plus want to have a research day each week. Each of these is a soft constraint, as if they are all ignored, then you still have a timetable that works – just not one that makes very many people happy! However, you may well not be able to accommodate all of these requests without running out of space and time. Therefore, these soft constraints are typically put into timetabling software and ranked according to their importance. By ranking the soft constraints you are telling the software how important each of these soft constraints are in comparison to each other. In doing so the timetabling software will try to abide by all the hard and soft constraints when creating a timetable, but if they cannot all be fulfilled the software will try to satisfy as many of the higher ranked soft constraints as possible whilst also abiding by the hard constraints – the hard constraint must also be abided by! Using the same example, you could rank the soft constraints as shown below:

Student Lunch Hour – 1 hour between 12-14:00 – Rank 7

Student Teaching Day – Max 6 Hours – Rank 8

Student Consecutive Teaching Hours – Max 4 Hours – Rank 4

Staff Consecutive Teaching Hours – Max 3 hours – Rank 5

Staff Teaching Week – Max 4 days – Rank 6

Teaching Space Capacity – Timetable activities into rooms that closely match their class size

A Preferred Teaching Week – Restrict the number of bookings at certain times or on certain days.

Maximum Gap Between Lectures – Limit the number of free hours students (and staff) have between lectures.

Teaching Room Zoning – Concentrate certain departments bookings within specific areas of an estate. For example Department A would prefer to have their teaching in the 3 buildings the department is based in.

Fixslots.com is designed to meet all these constraints Including (Hard+Soft) in blue and orange plans. Hope You'll enjoy !