Heuristics in scheduling classes
Recently, the topic of class schedules slipped here, and I wanted to talk about my experience in building a scheduling algorithm for the university, or rather, more about the heuristics I used.
In the near 2002, ending with the university ( Yaroslavl branch of MESI ), specialty "Applied Informatics in Economics", the task was to select a thesis. The proposed list of topics disappointed, mostly boring database development. In principle, any of my existing developments could be taken as a basis, as suggested by the head. Department, but the blood raged, I wanted to do something interesting and new for myself. I suggested to the head the topic of scheduling, especially as he worked in the IT service of the university, and I was in charge of the KIS UZ system (Integrated Information Management System for Educational Institution), a product of the Yaroslavl company. KIS UZ was good, but she could not make the schedule herself. Also, by this I was aiming to do something useful, but it turned out that there were no attempts to put into practice, maybe even a publication on Habré would give someone a benefit.
So, it was necessary to teach the computer to make a weekly schedule of classes, and as best as possible. Aware of the scale of the search space, 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 chosen, which has such input data:
- number of days in a week
- number of lessons per day
- list of teachers
- list of groups, subgroups and streams
- the number of audiences for a particular type
- a set of groups of tasks (classes):
The process should arrange classes on a temporary grid - the schedule. In the evaluation of the schedule, 4 parameters are involved - 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 sets the director. At first I wanted to apply the method of analyzing hierarchies in the objective function, but I would have to introduce a pair-wise comparison of these parameters, so I managed with a linear function.
')
As for the audience, I went to the simplification, removed it from the schedule, making it a limitation, when looking for the number of free audiences for a specific time was taken into account. After generating the schedule in time - were placed the audience. In general, I have outlined such a simple model. I experimented a bit with the genetic algorithm, based on the library I sketched a program during the day, but did not like the result, and without thinking about it, I switched to other algorithms. I think the bad result was due to my unjust approach, most likely, unsuccessfully coded the model in terms of GA. He began to think about the method of branches and borders. The search space is a tree, where a level means occupation, and a branch is an element of the time grid. Schedule is considered the path from the root of the tree to one of the hanging peaks. On the way, in the process of branching, the possibility and expediency of a detour by various criteria is checked: teacher's employment, groups, assessment. Bypassing the tree, naturally, deep down. At each level there are free grid cells for the current task. If the director “rigidly” secured this task for a specific time, then one branch is constructed corresponding to a specific time. Then, passing along the branch, there is an upper bound estimate (plus control for the presence of free audiences of this type), and if the upper bound is higher than the estimate of the best-found current schedule (and if there is a free audience of this type), then branches, otherwise move 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, I evaluated the current incomplete schedule, and compared it with the current best found schedule. Since, plunging further, the evaluation of an incomplete timetable will become worse, then if it is already worse than the evaluation of a better timetable, then the branch is rejected. And so, having programmed the whole thing, having prepared the data (I took it from the system on the basis of real data) I started it in the evening and went home. In the morning, having come to work, I loaded into the KIS UZ the obtained best of the billion found schedules, but it was impossible to look at it without tears. I was disappointed, dejected and did not know what to do next. In the evening, I went with friends to drink a beer, and here I stand at the bus stop and wait for the last tram, and in my head there are only trees, branches, borders, assessments ... sort them, make sure that first the options that are more likely than others would be included in the best timetable. But how to do it? The thought came when I was already smoking a second cigarette. It is necessary, in advance, to build your ideal schedules for each subject of the schedule, and for each branch to calculate the degree of contact with these schedules, and sort them. In the morning I went to work faster than usual, drawing technical details in my head, for lunch the heuristics was built in, the result looked pretty good at the KIS UZ, and the rest of the working day I was smiling.
Ps. Later, when I heard of PageRank, I thought that there was something in it similar to this heuristic.
In the near 2002, ending with the university ( Yaroslavl branch of MESI ), specialty "Applied Informatics in Economics", the task was to select a thesis. The proposed list of topics disappointed, mostly boring database development. In principle, any of my existing developments could be taken as a basis, as suggested by the head. Department, but the blood raged, I wanted to do something interesting and new for myself. I suggested to the head the topic of scheduling, especially as he worked in the IT service of the university, and I was in charge of the KIS UZ system (Integrated Information Management System for Educational Institution), a product of the Yaroslavl company. KIS UZ was good, but she could not make the schedule herself. Also, by this I was aiming to do something useful, but it turned out that there were no attempts to put into practice, maybe even a publication on Habré would give someone a benefit.
So, it was necessary to teach the computer to make a weekly schedule of classes, and as best as possible. Aware of the scale of the search space, 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 chosen, which has such input data:
- number of days in a week
- number of lessons per day
- list of teachers
- list of groups, subgroups and streams
- the number of audiences for a particular type
- a set of groups of tasks (classes):
- occupation
- teacher
- stream or group
- type of audience
- number of classes in this class
- time, if the director wants to “hard” to set the lesson at a certain time
The process should arrange classes on a temporary grid - the schedule. In the evaluation of the schedule, 4 parameters are involved - 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 sets the director. At first I wanted to apply the method of analyzing hierarchies in the objective function, but I would have to introduce a pair-wise comparison of these parameters, so I managed with a linear function.
')
As for the audience, I went to the simplification, removed it from the schedule, making it a limitation, when looking for the number of free audiences for a specific time was taken into account. After generating the schedule in time - were placed the audience. In general, I have outlined such a simple model. I experimented a bit with the genetic algorithm, based on the library I sketched a program during the day, but did not like the result, and without thinking about it, I switched to other algorithms. I think the bad result was due to my unjust approach, most likely, unsuccessfully coded the model in terms of GA. He began to think about the method of branches and borders. The search space is a tree, where a level means occupation, and a branch is an element of the time grid. Schedule is considered the path from the root of the tree to one of the hanging peaks. On the way, in the process of branching, the possibility and expediency of a detour by various criteria is checked: teacher's employment, groups, assessment. Bypassing the tree, naturally, deep down. At each level there are free grid cells for the current task. If the director “rigidly” secured this task for a specific time, then one branch is constructed corresponding to a specific time. Then, passing along the branch, there is an upper bound estimate (plus control for the presence of free audiences of this type), and if the upper bound is higher than the estimate of the best-found current schedule (and if there is a free audience of this type), then branches, otherwise move 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, I evaluated the current incomplete schedule, and compared it with the current best found schedule. Since, plunging further, the evaluation of an incomplete timetable will become worse, then if it is already worse than the evaluation of a better timetable, then the branch is rejected. And so, having programmed the whole thing, having prepared the data (I took it from the system on the basis of real data) I started it in the evening and went home. In the morning, having come to work, I loaded into the KIS UZ the obtained best of the billion found schedules, but it was impossible to look at it without tears. I was disappointed, dejected and did not know what to do next. In the evening, I went with friends to drink a beer, and here I stand at the bus stop and wait for the last tram, and in my head there are only trees, branches, borders, assessments ... sort them, make sure that first the options that are more likely than others would be included in the best timetable. But how to do it? The thought came when I was already smoking a second cigarette. It is necessary, in advance, to build your ideal schedules for each subject of the schedule, and for each branch to calculate the degree of contact with these schedules, and sort them. In the morning I went to work faster than usual, drawing technical details in my head, for lunch the heuristics was built in, the result looked pretty good at the KIS UZ, and the rest of the working day I was smiling.
Ps. Later, when I heard of PageRank, I thought that there was something in it similar to this heuristic.
Source: https://habr.com/ru/post/148717/
All Articles