Heuristics in scheduling classes

Recently, the topic of class schedules slipped here, and I wanted to talk about my experience in constructing a scheduling algorithm for a university, or rather, more about the heuristics that I applied.

In the recent year 2002, ending with a university ( Yaroslavl branch of MESI), specialty "Applied Informatics in Economics", the task was to choose a thesis. The proposed list of topics was depressing, mostly boring database development. In principle, one of my existing developments could be taken as a basis, as suggested by the head. chair, but the blood was seething, I wanted to do something interesting and new for myself. I suggested the topic of scheduling to the head, especially since I worked in the IT service of the university, and I was in charge of the KIS UZ (Integrated Management Information System for the School) system, a product of the Yaroslavl company. KIS UZ was good, but she could not make a schedule. Also, with this I was aiming to do something useful, but it turned out that there were no attempts to implement it, maybe even publishing on a hub will give someone some benefit.

So, it was necessary to teach the computer to make a weekly lesson schedule, and as best as possible. Realizing the scale of the search space, he did not set the goal of finding the best option. First you need to determine what the classes are, and what is good and what is bad. The following model was selected, which has such input data:
- number of days in a week
- number of classes per day
- list of teachers
- list of groups, subgroups and flows
- number of classrooms for a certain type
- set of groups of tasks (classes):
  • occupation
  • teacher
  • stream or group
  • type of audience
  • number of classes in this group of classes
  • time if the director wants to “rigidly” establish this activity at a certain time

The process should arrange the lessons on a temporary grid - schedule. Four parameters take part in the schedule assessment - the number of “windows” in the schedule for the group and teachers, the even distribution of classes by day for the group and teachers. The significance of these parameters is set by the director. At first I wanted to apply the method of hierarchy analysis in the objective function, but I would have to introduce a pairwise comparison of these parameters, so I managed a linear function.



As for the audiences, I went for simplification, removed it from the schedule, making it a limitation, when searching, the number of free audiences for a specific time was taken into account. After generating the schedule in time, the audiences were placed. In general, I have outlined such a simple model. I experimented a little with the genetic algorithm, on the basis of the library I sketched a program during the day, but I didn’t like the result, and without thinking twice, I switched to other algorithms. I think a bad result was due to my baseless approach, most likely, the model was encoded in terms of GA unsuccessfully. I began to think about the method of branches and borders. The search space is a tree, where the level means occupation, and the branch is an element of the time grid. The schedule is considered the way from the root of the tree to one of the hanging peaks. On my way, in the process of branching, the possibility and expediency of going around by various signs are checked: the employment of the teacher, group, assessment. Bypassing the tree, naturally, inland. At each level there are free grid cells for the current task. If the director “rigidly” fixed this task for a certain time, then one branch corresponding to a certain time is built. Further, passing along the branch, the upper bound is estimated (plus, this is monitored for the presence of free audiences of this type), and if the upper bound is higher than the estimate of the currently found best schedule (and if there is a free audience of this type), then branches, otherwise go to the next branch. In the branch and bound method, the key and important point is the algorithm for finding the upper bound estimate. Without further ado, evaluated the current incomplete schedule, and compared with the current best found schedule. Since, diving further, the estimate of the incomplete schedule will become worse, then if it is already worse than the estimate of the best schedule, the branch will be rejected. And so, having programmed this whole thing, having prepared the data (taken from the system based on real data), he started it in the evening and went home. In the morning, having come to work, uploaded to KIS UZ the best of the billion schedules found, but without tears it was impossible to look at it. I was disappointed, dejected and did not know what to do next. In the evening, we went with friends to drink beer, and now I’m standing at a stop under a hop and waiting for the last tram, and in my head there are only trees, branches, borders, grades ... and then it dawns on me that I need to somehow at each level, when determining the branches, sort them, do so first, those options that would be more likely than others to be part of a better schedule. But how to do it? The thought came when he was already smoking a second cigarette. It is necessary, first, to build their ideal schedules for each subject of the schedule, and for each branch, calculate the degree of getting into these schedules, and sort by it. In the morning I went to work faster than usual, drawing technical details in my head on the way, by noon the heuristic was built in, the result looked pretty good in KIS UZ, and the remaining half-day I smiled. and sort by it. In the morning I went to work faster than usual, drawing technical details in my head on the way, by noon the heuristic was built in, the result looked pretty good in KIS UZ, and the remaining half-day I smiled. and sort by it. In the morning I went to work faster than usual, drawing technical details in my head on the way, by noon the heuristic was built in, the result looked pretty good in KIS UZ, and the remaining half-day I smiled.

PS. Later, when I heard about PageRank, I thought that there was something similar to this heuristic in it.

Also popular now: