School timetable - how to automate its creation?

[amorosik]

I would like to create a procedure to automate the compilation of the classic school timetable
And so starting from:
- list of teachers
- list of subjects provided by each teacher (each could teach more than one subject) and weekly quantity (e.g. teacher code 1 teaches mathematics and history and is present for 4 hours/week)
- list of classes present (3A, 3B, 4A, 5A, 5B, ...)
- weekly list of subjects for each class (class 3A=4 hours English, 3 hours history, 6 hours mathematics...)

How to automate the problem of obtaining weekly/monthly school hours using the information provided above?
What logic would you use to compile the timetable?

 

[Pat Hartman]

This isn't a technical question. You are asking us to create a schema and then write the code to populate it and haven't even added any of the rules that will probably appy.
1. teacher1 works only mornings
2. chemistry can be taught only in these two classrooms.
3. adjacent time slots shouldn't have a teacher walking across campus.
4. If a teacher teaches more than one subject, how much time is spent with each?
5. etc.

 

[gemma-the-husky]

All I will say is it's bound to be tricky, especially if the teachers aren't available for every period during the month. I presume you also need to ensure that certain subjects don't clash, so students aren't prevented from taking certain mixes.

Do you have to plan multiple years of lessons as well? I mean different ages of children.

How do you do it manually?
Write it down, and get your process to do a similar thing.

 

[isladogs]

I managed the timetable in my large secondary school with 100+ teachers (full and part time) for many years. I used complex specialist software to do so and having specified all the necessary rules, it was possible to automate parts of the timetabling process. That was the easy part.

The software then indicated all the clashes and it was up to me as the timetabler to manage all the rest of the task. This included manually rearranging slots and lots of discussions with individual staff over a period of several weeks to fix issues.

You will not be able to create an Access database to do this unless your school is small and the rules are very simple.
Use software designed for the job.

 

[arnelgp]

see post #3.
your automated system is only a reflection of your manual system.
know the manual system and it will be easy to translate it into code.

the part of knowing the system is called system analysis.

 

[amorosik]

How do you do it manually?
Write it down, and get your process to do a similar thing.

Yes, that's the point of the question
If I had already faced this problem manually, then I would know the logic to follow to solve it also via code
But I have never had to deal with this type of problem
And therefore I was asking for your help to understand how it can be solved in automatic mode

 

[amorosik]

see post #3.
your automated system is only a reflection of your manual system.
know the manual system and it will be easy to translate it into code.

the part of knowing the system is called system analysis.

I'm perfectly agree
But at this moment I don't know how to proceed (manual or automatic doesn't matter)
Seeing that there are already many systems that allow you to propose a school timetable, perhaps which can then be modified manually, I would like to create a procedure that comes as close as possible to these systems

 

[CJ_London]

You need to define all the rules, then design your schema accordingly. Pat made some suggestions in post #2 but only you know the requirements, restrictions etc or are in a position to find out by asking your client the questions

 

[amorosik]

I managed the timetable in my large secondary school with 100+ teachers (full and part time) for many years. I used complex specialist software to do so and having specified all the necessary rules, it was possible to automate parts of the timetabling process. That was the easy part.

The software then indicated all the clashes and it was up to me as the timetabler to manage all the rest of the task. This included manually rearranging slots and lots of discussions with individual staff over a period of several weeks to fix issues.

You will not be able to create an Access database to do this unless your school is small and the rules are very simple.
Use software designed for the job.

If there are complex software that achieve what I have described, I don't understand why you say that it is not possible to obtain the same effect with an Access procedure
Ah... maybe you meant I won't be able to do it
Oh yes, maybe

 

[amorosik]

This isn't a technical question. You are asking us to create a schema and then write the code to populate it and haven't even added any of the rules that will probably appy.
1. teacher1 works only mornings
2. chemistry can be taught only in these two classrooms.
3. adjacent time slots shouldn't have a teacher walking across campus.
4. If a teacher teaches more than one subject, how much time is spent with each?
5. etc.

No
The basic information to start processing is obviously already present
What I asked is:
"..What logic would you use to compile the timetable?.."
Basically, what algorithm to follow to compile the school timetable
And being one of the classic problems that can be found in computer science, I thought there were already codified and tested methods to achieve the set objective (for example the traveling salesman's algorithm), but perhaps each one proceeds independently
Like when at school you study the ordering of a list of elements, there are methods already studied and tested, it is useless to invent hot water

 

[amorosik]

You need to define all the rules, then design your schema accordingly. Pat made some suggestions in post #2 but only you know the requirements, restrictions etc or are in a position to find out by asking your client the questions

Yes, of course, there must obviously be a table dedicated to the constraints to be respected
Both ordinary constraints (such as the number of hours per week for a certain teaching subject) and extraordinary constraints (such as teacher XYZ requesting to leave a couple of hours early because he has to catch the train)
And I think respecting these constraints is the most complex thing
In fact in many cases it will not be possible to respect them all and therefore adding a priority for each constraint will be essential, so as to first respect those with high priority and then gradually those with lower priority

 

[ebs17]

I would like to create a procedure...

That sounds a bit cocky if you ask in the next breath how you should implement it. A serious developer would have thought through his task several times and could and would present his own ideas.

What logic would you use to compile the timetable?

In a blank plan I would write something that is not wrong. If there are no rules for this, a random selection is carried out.
This process is repeated in a loop, taking into account that the initial quantity is reduced and that the entry options in the plan become fewer and more specific.

 

[gemma-the-husky]

@amorosik

Nothing in a database is "of course,". It's up to the database designer to understand and build the system. I think we assumed you were familiar with manually developing a time table, and wanted to automate the process. Most of us aren't familiar with such software, and would have to give this careful thought. @isladogs is familiar, and he told you this is very complex, and you are most unlikely to be able to do this, given the questions you are asking. Maybe Colin could do it, but I imagine if he thought it was straightforward he would have already developed such a system.

Your constraint about a teacher taking time off is a case in point. You must plan the timetable in advance knowing whether the teacher is available or not. If, having planned the timetable, a teacher becomes non available, then you will need a substitute teacher, or some other mechanism to manage that lesson. Maybe schools have spare capacity to do that outside scheduled plans. I don't know, as I'm not familiar with the workings of a school. I doubt very much a "system" can automate processes of that nature.

 

[gemma-the-husky]

Another thought.

Maybe this is so complex, that the only way to deal with it is to treat it as a sort of linear programming exercise, of managing resources adequately, where you produce a scheme that satisfies constraints. It's not necessarily the best timetable, but it can successively be refined to create better and therefore acceptable timetables from the effectively infinite number of possible timetables.

Maybe you have teachers who can teach alternate subjects, and the scheme you produce works, but doesn't use all the teachers in the way they might prefer to be used, for instance.

You might build a system that needs 25 teachers, but you might have been able to build it in another way with only 24. Both systems work, but one is slightly more efficient but provides less slack, if you will.

 

[Minty]

I created a system for a group of consultants to manage their weekly commitments, and plan new projects.
It has a target number of allocated hours, and allows for holidays, and repeating retained work.
It also has to ensure all members of the project's team have available hours in any given week, and they also need to occasionally force a dead line date for a specific step of a project.

To say this was a complicated system to set up and program would be an understatement, and it has taken many iterations and tweaks to get it right. It is only looking at whole weeks and a small number of consultants, with small teams.

I can't imagine trying to do the same for a school timetable with all the variables, with classroom availability, clashes of type of class, availability of teachers, different class lengths, double periods etc. etc.

 

[isladogs]

In an ideal world, your school timetable will be based on the following conditions

• all teachers are full time
• each teacher always teaches in their own classroom
• there are sufficient specialist classrooms for each subject
• no classroom is ever required for other non-teaching purposes
• each teacher only teaches one subject
• all lessons are on a single site
• there are no restrictions on when certain lessons are taught
• you have a one-week timetable (not fortnightly)
• all lessons are single periods (no doubles)
• randomising lesson placement in the day / week isn't important
• etc, etc

However, that is never going to be the situation in any typical school.
First obtain a list of conditions / restrictions that apply in your school and prioritise them
Start with the most restrictive items and work from there
If you are very lucky, you may get 80% of the timetable done using automation - often less than that
Completing the rest will require lots of discussions & compromises resulting in much of the automated portion being undone

Each year, the conditions will differ and the process will need different rules

The process will require a complex GUI to make it understandable both to the timetabler and to others involved in the process.
There will also be a need for many & complex reports for different purposes

From experience, I would say this isn't a task that should be done in Access nor is it worth spending hundreds / thousands of hours devising a database from scratch. Specialist software is available for this purpose

 

[amorosik]

That sounds a bit cocky if you ask in the next breath how you should implement it. A serious developer would have thought through his task several times and could and would present his own ideas.


In a blank plan I would write something that is not wrong. If there are no rules for this, a random selection is carried out.
This process is repeated in a loop, taking into account that the initial quantity is reduced and that the entry options in the plan become fewer and more specific.

I'm sorry I gave this impression, but that's not the case
Currently I have only created the data tables (teachers, courses, teachings per course, teachings per teacher, constraints, ...)
I do not yet have the code for compiling the solo timetable I'm asking for help because
I thought there were more or less standard methods to solve this problem, and therefore to avoid solving a problem already solved by others I thought I'd write the initial post
If this were not the case, and therefore there is no standard or preferential method for solving the problem, then I hypothesize that starting by creating a basic timetable without taking into account the constraints, and then retouching it to ensure that the constraints are respected could be a logic to be followed.

 

[CJ_London]

Perhaps start with something simple like solving a suduko puzzle

 

[amorosik]

@amorosik

Nothing in a database is "of course,". It's up to the database designer to understand and build the system. I think we assumed you were familiar with manually developing a time table, and wanted to automate the process. Most of us aren't familiar with such software, and would have to give this careful thought. @isladogs is familiar, and he told you this is very complex, and you are most unlikely to be able to do this, given the questions you are asking. Maybe Colin could do it, but I imagine if he thought it was straightforward he would have already developed such a system.

Your constraint about a teacher taking time off is a case in point. You must plan the timetable in advance knowing whether the teacher is available or not. If, having planned the timetable, a teacher becomes non available, then you will need a substitute teacher, or some other mechanism to manage that lesson. Maybe schools have spare capacity to do that outside scheduled plans. I don't know, as I'm not familiar with the workings of a school. I doubt very much a "system" can automate processes of that nature.

Yes, understanding the system is what I'm trying to do
With your help
"..I think we assumed you were familiar.." no, in my first project
"..Your constraint about a teacher taking time off.." yes, this must be codified on 'contrain' table
"..I doubt very much a "system" can automate processes of that nature.." you're too pessimistic, I'll take the plunge and then we'll see

 

[amorosik]

Another thought.

Maybe this is so complex, that the only way to deal with it is to treat it as a sort of linear programming exercise, of managing resources adequately, where you produce a scheme that satisfies constraints. It's not necessarily the best timetable, but it can successively be refined to create better and therefore acceptable timetables from the effectively infinite number of possible timetables.

Maybe you have teachers who can teach alternate subjects, and the scheme you produce works, but doesn't use all the teachers in the way they might prefer to be used, for instance.

You might build a system that needs 25 teachers, but you might have been able to build it in another way with only 24. Both systems work, but one is slightly more efficient but provides less slack, if you will.

Yes, the idea is to be able to propose a school timetable that satisfies the constraints
Then the changes to optimize it can be made manually