School timetable algorithm

Question

I was wondering if there are any known solutions for the school curriculum creation algorithm. This mainly concerns the optimization of “hourly dispersion” (both in the case of teachers and in classes) for these class-subject-teacher associations. We can assume that we have sets of classes, lesson subjects and teachers connected to each other at the entrance, and this schedule should correspond between 8AM and 4PM.

I guess there is probably no exact algorithm for this, but maybe someone knows a good approximation or tips for developing it.

Answer 1

This problem is NP-Complete !
In a nutshell, you need to study all possible combinations to find a list of acceptable solutions. Due to differences in circumstances in which the problem occurs in different schools (for example: are there restrictions on classrooms?). Are some of the classes in some subgroups separated for a while? Is this a weekly schedule? etc.) there is no known class of problems that corresponds to all planning tasks. Perhaps the Knapsack issue has many similarities to these issues in general.

Confirmation that this is both a difficult problem and one for which people are constantly looking for a solution is to check out this (long) list of (mostly commercial) software planning tools

Due to the large number of variables involved, the largest source of which, as a rule, is desired by the teacher, -) ..., it is usually impractical to consider listing all possible combinations . Instead, we need to choose an approach that visits a subset of the problem / solution space.
- Genetic algorithms cited in another answer (or, it seems, IMHO), well prepared to perform this kind of semi-oriented search (the problem is to find a good rating function for candidates to be saved for the next generation)
- Graph rewriting is also used with such combinatorial optimization problems.

Instead of focusing on specific implementations of the automatic schedule generator program, I would like to suggest several strategies that can be applied at the problem definition level .
The general rationale is that in most real-world planning tasks some compromises will be required, and not all limitations, expressed and implied: will be fully implemented. Therefore, we help ourselves:

• Defining and ranking all known constraints
• Manually reduce problem space by providing a set of additional restrictions. This may seem contradictory, but, for example, by providing an initial, partially filled schedule (say, about 30% of the time intervals), in a way that fully satisfies all the restrictions, and considering this inevitable partial schedule, we significantly reduce time / space, necessary to obtain candidate decisions.
  Another way that additional restrictions helps is, for example, "artificial" adding a restriction that prevents certain subjects from learning on certain days of the week (if this is a weekly schedule ...); this type of constraint reduces the space of problems / solutions, without, as a rule, eliminating a significant number of good candidates.
• Providing quick calculation of some problem constraints. This is often related to the choice of data model used to represent the problem; the idea is to be able to quickly select (or cut) some of the options.
• Override the problem and break some of the restrictions several times (usually to the end nodes of the graph). The idea here is either to remove some of the restrictions for filling the last few slots in the schedule, or to make the automatic schedule generator program invisible to complete the entire schedule, instead providing us with a list of a dozen or so plausible candidates. A person is often in a better position to complete the puzzle, as indicated, possibly violating some of the contraindications, using information that is not usually shared with automated logic (for example, the rule “No math in the afternoon” may be violated for the class “advanced” Mathematics and Physics "or" It is better to violate one of the requirements of Mr. Jones than one of Ms Smith ... ;-))

In the proof of this answer, I understand that he is rather shy to give a definite answer, but nevertheless he has practical suggestions. I hope this help, with which, in the end, is a "difficult problem".

Answer 2

This is a mess. royal mess. To add to the answers, already very complete, I want to point out my family experience. My mother was a teacher and used participation in this process.

It turns out that having a computer for this is not only difficult in itself, but also difficult, because there are conditions that are difficult to determine for a pre-baked computer program. Examples:

• The teacher teaches both at your school and at another institution. It is clear that if he finishes the lesson there at 10.30, he cannot start at your premises at 10.30, because he needs some time to get between the institutes.
• two teachers are married. In general, he believes that it is not good practice to have two married teachers in the same class. Therefore, these two teachers must have two different classes.
• two teachers get married and their child attends the same school. Again, you must stop the two teachers from teaching in the particular classroom where their child is.
• The school has separate facilities, for example, one day the class is in one institution, and the next day the class is in another.
• There are laboratories in the school, but these laboratories are only available on certain working days (for safety reasons, for example, when additional staff is required).
• Some teachers have preferences during the free day: some prefer on Monday, some on Friday, some on Wednesday. Some prefer to arrive early in the morning, some prefer to arrive later.
• you should not have situations where you have a lesson, say, history in the first hour, then three hours of math, then another hour of history. This makes no sense to students as well as to the teacher.
• you should evenly distribute the arguments. It does not make sense to have the first days only in mathematics, and then the rest of the week.
• you must give teachers two consecutive hours to conduct assessment tests.

As you can see, the problem is not NP-complete, it is NP-crazy.

So what they do is that they have a large table with small plastic inserts, and they move the inserts until a satisfactory result is obtained. They never start from scratch: they usually start from the schedule of the previous year and are adjusted.

Answer 3

The 2007 International Scheduled Competition has set up a scheduling schedule for tracking and tracking exams. Many researchers participated in this competition. Many heuristics and meta-heuristics have been tested, but in the end, local search meta-heuristics (such as Tabu Search and Simulated Annealing) clearly outperformed other algorithms (such as genetic algorithms).

Take a look at the 2 open source frameworks used by some finalists:

• JBoss OptaPlanner (Java, open source)
• Unitime (Java, open source) - more for universities

Answer 4

One of my half-time appointments is generating a school genetic algorithm table.

The whole table is one "organism." Some changes and warnings have been made to the general approach to genetic algorithms:

• The rules for "illegal tables" were adopted: two classes in one class, one teacher simultaneously taught two groups, etc. These mutations were considered fatal immediately, and a new "organism" was sprouted instead of the "dead" immediately. The original was created by a series of random attempts to get legal (if it is meaningless). The fatal mutation was not considered in relation to the number of mutations per iteration.

• Exchange mutations were much more common than Modify mutations. Changes were only between parts of the gene that made sense - without replacing the teacher with the classroom.

• Small bonuses were assigned to combine a certain 2 hours together, to assign the same generic class in sequence for the same group, to preserve the duration of the teacher's work and to continuously load the class. Moderate bonuses were assigned to provide the right classrooms for the subject, to keep hours of classes in bonds (in the morning or afternoon), etc. Big bonuses were designed to set the correct amount of a given subject, a given workload for a teacher, etc.

• Teachers can create workload schedules “I want to work then”, “I want to work normally”, “I don’t like to work”, “I can’t work”, with appropriate weights. The whole 24 hours were legal working hours, except at night, it was very undesirable.

• Weight function ... oh yes. The weight function was a huge, monstrous product (as in multiplication) of the scales assigned to the selected properties and properties. It was very cool, one property could easily change it by an order of magnitude up or down - and in one organism there were hundreds or thousands of properties. This led to absolutely HUGE numbers as weights, and as a direct result, you need to use the bignum library (gmp) to perform the calculations. For a small test test of 10 groups, 10 teachers and 10 classrooms, the initial set began at 10 ^ -200 and that from 10 ^ + 300. It was completely ineffective when it was flatter. In addition, values ​​grew at a wider distance with larger "schools."

• The average computational time there was little difference between a small population (100) for a long time and a large population (10k +) for fewer generations. Calculation for the same time produced approximately the same quality.

• The calculation (at some 1 GHz CPU) would take about 1 hour to stabilize around 10 ^ + 300, generating graphs that looked pretty good for the 10x10x10 test case mentioned.

• The problem is easily parallelizable by providing a network tool that will exchange the best samples between computers on which the calculation is performed.

As a result, the program never saw the light of day to get a good class for a semester. This showed some promises, but I never had enough motivation to add any kind of graphical interface and make it useful to the general public.

Answer 5

This problem is more complicated than it seems.

As others have said, this is an NP-complete problem, but let them analyze what it means.

Basically, this means that you should look at all the possible combinations.

But “watching” does not tell you what you need to do.

Making all possible combinations is easy. This can lead to a huge amount of data, but you should not have problems understanding the concepts of this part of the problem.

The second problem is to assess whether a given combination is good, bad, or better than the previous “good” solution.

To do this, you need more than just "this is a possible solution."

For example, the same teacher who works 5 days a week for X weeks in a row? Even if this is a working solution, it may not be a better solution than alternating between two people, so that each teacher does each week. Oh, have you thought about this? Remember that these are the people you are dealing with, and not just the problem of resource allocation.

Even if one teacher can work full time for 16 consecutive weeks, it may not be the optimal solution compared to the one in which you try to alternate teachers, and this kind of balancing is very difficult to integrate into the software.

To summarize, creating a good solution to this problem will cost a lot, for many people. Therefore, it is not an easy task to break and solve. Be prepared to make several goals that are not 100%, and calling them "good enough."

Answer 6

UPDATE: from the comments ... there should also be heuristics!

I would go with Prolog ... then use Ruby or Perl or something to clear your solution in a more beautiful form.

teaches(Jill,math). teaches(Joe,history). involves(MA101,math). involves(SS104,history). myHeuristic(D,A,B) :- [test_case]->D='<';D='>'. createSchedule :- findall(Class,involves(Class,Subject),Classes), predsort(myHeuristic,Classes,ClassesNew), createSchedule(ClassesNew,[]). createSchedule(Classes,Scheduled) :- [the actual recursive algorithm]. 

I'm (still) in the process of doing something similar to this problem, but using the same path that I just mentioned. Prolog (as a functional language) really makes it easier to solve NP-Hard problems.

Answer 7

Genetic algorithms are often used for such planning.

Found this example (creating class schedules using a genetic algorithm) that matches your requirement.

Answer 8

Here are some links I found:

School timetable - lists some of the problems associated with this

Hybrid Genetic Algorithm for School Schedules

Planning utilities and tools

Answer 9

My scheduling algorithm implemented in FET (Free Timetabling Software, http://lalescu.ro/liviu/fet/ , successful application):

The heuristic algorithm. I called it a "recursive replacement."

Input: set of actions A_1 ... A_n and restrictions.

Output: a set of times TA_1 ... TA_n (time interval of each type of activity. For convenience, numbers are excluded here). The algorithm should place each action in a time interval, observing the restrictions. Each TA_i is between 0 (T_1) and max_time_slots-1 (T_m).

Limitations:

C1) Basic: a list of pairs of actions that cannot be simultaneous (for example, A_1 and A_2, because they have the same teacher or the same students);

C2) Many other limitations (excluded here for simplicity).

Schedule Algorithm (which I called a "recursive replacement"):

• Sorting is the most difficult task. Not a critical step, but speeds up the algorithm, perhaps 10 times or more.

• Try to place each action (A_i) in the allowed time interval, following the order above, one at a time. Find an available slot (T_j) for A_i in which this activity can be set subject to restrictions. If more slots are available, select random. If none of them are available, perform a recursive replacement:

  a . For each time interval T_j, consider what happens if you put A_i in T_j. There will be a list of other actions that are not consistent with this movement (for example, activity A_k is in the same slot T_j and has the same teacher or the same students as A_i). Keep a list of conflicting activities for each time interval T_j.

  b . Choose the slot (T_j) with the least amount of conflicting actions. Let's say the list of actions in this slot contains 3 actions: A_p, A_q, A_r.

  with Put A_i in T_j and make A_p, A_q, A_r unallocated.

  d . Try recursively placing A_p, A_q, A_r (if the recursion level is not too large, say 14, and if the total number of recursive calls counted after step 2) on the initial A_i is not too large, say 2 * n), as in step 2 )

  e . If A_p, A_q, A_r have been set successfully, return with success, otherwise try other time intervals (go to step 2 b) and select the next best time interval).

  e . If all (or a reasonable number) of time intervals were unsuccessful, return without success.

  g . If we are at level 0, and we were unable to place A_i, place it as in steps 2 b) and 2 c), but without recursion. We now have 3 - 1 = 2 more events to host. Go to step 2) (some methods are used here to avoid cycling).

Answer 10

I have developed commercial algorithms for both the class schedule and the exam schedule. For the first, I used integer programming; for the second heuristic, based on maximizing the objective function, by choosing slots, very similar to the initial manual process that was developed. The main thing in making such decisions is the ability to represent all the limitations of the real world; and for human schedules will not be able to see ways to improve the solution. As a result, the algorithmic part was quite simple and easy to implement compared to the preparation of databases, the user interface, the ability to report statistics, such as the use of premises, user training, etc.

Answer 11

This article describes the problem of the school curriculum and their approach to the algorithm pretty well: " Development of the SYLLABUS-Interactive Scheduler based on restrictions for schools and colleges. " [PDF]

The author informs me that the SYLLABUS software is still used / developed here: http://www.scientia.com/uk/

Answer 12

I am working on a widely used planning mechanism that does just that. Yes, this is NP-Complete; best approaches are aimed at approximating the optimal solution. And, of course, there are many different ways to tell which one is the “best” solution - is it more important that your teachers are happy with their schedule or, for example, with students in all their classes?

The absolute most important question that needs to be addressed early is what makes one way to plan this system better than another ? That is, if I have a schedule with Mrs. Jones teaching mathematics at 8 years old, and Mr. Smith teaching mathematics at 9 years old, is it better or worse than in one of them that have mathematics teaching at 10 years old? Is it better or worse than with Mrs. Jones teaching at age 8, and Mr. Jones studying at 2? Why?

The main advice that I will give here is to divide the problem as much as possible - perhaps a course, of course, a teacher, perhaps around the room - and first get down to solving the problem. There you should get a lot of solutions to choose from and choose one of them as the most optimal. Then, work on creating “earlier” subtasks takes into account the needs of later sub-problems in assessing their potential solutions. Then, perhaps, you will work on how to get out of the situation with the painted ones in the corner (provided that you cannot foresee these situations in earlier problems) when you find yourself in a state of “without valid solutions”.

The local search optimization pass is often used to “polish” the final answer for better results.

Please note that we usually deal with resource-limited systems in school planning. Schools do not go through a year with a lot of empty rooms or teachers sitting in the salon 75% of the day. The approaches that work best in decision-rich environments are not necessarily applicable to the school schedule.

Answer 13

Generally, constraint programming is a good approach to this planning problem. A search for “restriction programming” and planning or “restriction-based planning” for both stack overflow and Google will lead to good links. This is not impossible - which is difficult to think about when using traditional optimization methods, such as linear or whole optimization. One solution would be - is there a schedule that meets all the requirements? This in itself is obviously useful.

Good luck

Answer 14

You can use it with genetic algorithms, yes. But you should not :. It may be too slow, and setting parameters may be too economical, etc.

There are other approaches. All are implemented in open source projects:

• Constraint Based Approach
  • Implemented in UniTime (not for schools)
  • You can also go further and use Integer programming. Successfully done at the University of Udine , as well as at the University of Bayreuth (I was involved there) using commercial software (ILOG CPLEX)
  • Rule-based heuristic approach - see Drools Scheduler
• Various heuristics - FET and my own

See here for a list of schedule schedules.

Answer 15

I think you should use a genetic algorithm because:

• It is best suited for large instances of problems.
• This gives reduced time complexity at the price of an inaccurate answer (not the best)
• You can easily identify restrictions and preferences by adjusting fitness penalties for non-working people.
• You can specify time limits for program execution.

• The quality of the decision depends on how much time you intend to spend on the decision of the program.

  Definition of genetic algorithms

  Genetic Algorithm Tutorial

  Class Planning Project with GA

Also look at a similar question and another

Answer 16

I don’t know that someone will agree with this code, but I developed this code using my own algorithm and works for me in ruby.Hope it will help those who are looking for it in the following periodflag flag code, dayflag day flag and teacher flag are a hash with the corresponding id and flag value, which is a boolean. Any problem contact me ....... (-_-)

periodflag.each do | k2, v2 |

  if(TimetableDefinition.find(k2).period.to_i != 0) subjectflag.each do |k3,v3| if (v3 == 0) if(getflag_period(periodflag,k2)) @teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id) @teacherlists=Employee.find(@teachers) teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle] teacherflag.each do |k4,v4| if(v4 == 0) if(getflag_subject(subjectflag,k3)) subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3) if subjectperiod.blank? issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3) if issubjectpresent.blank? isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4) if isteacherpresent.blank? @finaltt=TimetableAssign.new @finaltt.timetable_struct_id=@timetable_struct.id @finaltt.employee_id=k4 @finaltt.section_id=section.id @finaltt.standard_id=standard.id @finaltt.division_id=division.id @finaltt.subject_id=k3 @finaltt.timetable_definition_id=k2 @finaltt.timetable_day_id=k1 set_school_id(@finaltt,current_user) if(@finaltt.save) setflag_sub(subjectflag,k3,1) setflag_period(periodflag,k2,1) setflag_teacher(teacherflag,k4,1) end end else @subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3) @finaltt=TimetableAssign.new @finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id @finaltt.employee_id=@subjectdetail.employee_id @finaltt.section_id=section.id @finaltt.standard_id=standard.id @finaltt.division_id=division.id @finaltt.subject_id=@subjectdetail.subject_id @finaltt.timetable_definition_id=k2 @finaltt.timetable_day_id=k1 set_school_id(@finaltt,current_user) if(@finaltt.save) setflag_sub(subjectflag,k3,1) setflag_period(periodflag,k2,1) setflag_teacher(teacherflag,k4,1) end end end end end end end end end end end