At the beginning of each school year, universities everywhere must undertake boring and time-consuming process of slotting students, teachers and lessons into available classrooms. It is a natural scheduling problem and schedulemakers are looking for simple flexible and effective automatic systems.

Scheduling problems are often NP-complete. There are many approaches to deal with them such as algorithmic approach, operation research approach, etc. Algorithmic (or integer programming) approach is hard for scheduling problems, since the domain of the search space is very large. Finding the solution in this search space by traditional search methods is very inefficient. A lot of attention in operation research has been paid to scheduling problems that are based on relatively simple mathematical models. Operation research often aims to achieve a high level of efficiency. This approach has some classical models to use when modeling a practical scheduling problem. The main disadvantages of these models are in that they discard many degrees of freedom and side constraints that exist in the practical scheduling situation. Discarding degrees of freedom and side constraints causes optimal solutions to be eliminated, regardless of the solution method used. Discarding the side constraints may result in a simplified version of the problem and solving this simplified problem might be easier but the solution found can be impractical for the original problem.

yakhno.pdf223.81 KB