School timetable - how to automate its creation?

[ebs17]

Why in Access?
Ms Access is a small desktop database. The SQL dialect is very limited, there are no loops or recursions. VBA is not a language that can offer a good result for the masses of arithmetic operations that would be necessary in reasonable runtimes.

Ms Excel at least offers something like goal seek and solver.

For your task you don't need codes first, you don't need algorithms first. First you need a functional mathematical model, so you should consult with experts in this field. They probably also have experience with which program languages and environments would be helpful.

I also like Access. But you should know your program, as well as the advantages and the disadvantages and the limits and act accordingly (if it goes beyond your instinct to play).

 

[gemma-the-husky]

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

Yes, but the question of automatically managing a casual absence of a teacher is next to impossible. In the first place that would assume you always have a suitable "spare" teacher able to fit in at a moments notice. In practice I am sure that would be outside the scope of any system. The system would probably tell you which teachers were available in those time slots to help the administrator make an informed decision. Depending on the school you could even just give the class a "free" period. Clearly you couldn't do that with infants.

I think you could do it in Access, but I wouldn't want to try for my own amusement.

 

[isladogs]

Assigning cover for absent staff is done using a different but related application which has the full timetable info available to it.
There are other nationally agreed rules that need to be followed, at least in the UK, to determine whether the cover staff are current teachers with a non-contact period at that time...or whether external 'supply' teachers need to be used.

 

[The_Doc_Man]

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?

I looked at this a couple of different ways. Optimization problems and gaming problems are similar, analogous to each other in that there are multiple choices and your choice at each step of the way produces a more advantageous or less advantageous result. In this case it is like a decision tree. You make a move and decide what to do on the (now changed) pile of remaining things to do. The difficulty is that game trees can grow factorially based on the number of "things to do next." If you have hundreds of things to schedule and have constraints, picking what to do via random means will probably produce a result which you can "score" to decide how close you came to a viable schedule. (Granted, scoring a solution can itself be difficult since you can have multiple simultaneous criteria for success.) But the point is that there is no direct queuing theory solution for this problem. There is no direct game-theory solution. It is always iterative and the number of projected iterations is a function of the number of things to schedule. And N! (n-factorial) gets huge pretty quickly. It is for that reason that many people are consciously or unconsciously shying away from this beast of a scheduling problem.

I'll offer the thought that if you feel you MUST do this, the way to pare down the work is to schedule the most constrained choices first. I.e. if you have classes that can ONLY be taught by one teacher in one room, do that first and then lock it down. Take those resources AND requirements out of the problem. Now do the next most constrained selection. Wash, rinse, repeat. When you reach the point where you DO have multiple choices, that should be easier to find accommodations. This then becomes more like a hotel scheduling problem, which has been addressed in various posts in this forum. Try looking at "scheduling" in the forum for approaches that have been considered. The topic is not an exact match but there might be some parallels that are helpful.

 

[tvanstiphout]

Before you think you can do this brute force, think again. This came up in a recent discussion among the Access MVPs and I dug up the below diagram where I calculate how many combinations exist for two variables: the number of examiners needed per exam, and the number of examiners available for that exam. The number of combinations grows very quickly, and with that your computing time. And this is only two variables! I agree with Isladogs: this is the subject of very specialized software.

 

[gemma-the-husky]

Even Colin doesn't do it. He uses software designed to solve the specific problem and then fixes the clashes.

VBA may not be the best tool, but you could use it assuming your set of classes/teachers/rules isn't too large.

Use Doc's divide and conquer suggestion to get you started. Or, just go out to find a canned solution.

Yes, I really meant Colin might design and sell a complete solution but the fact that he hasn't indicates it's quite tricky.

For different reasons I wouldn't want to develop a payroll (well in the UK anyway - I'm not sure about other places). That wouldn't be ever so hard, but you would need a good insurance policy just in case.

 

[The_Doc_Man]

the issue in most cases is keeping up with the taxman

Oh, you are SO right. Heck, look at how many companies have their own USA Income Tax preparer programs.

 

[MajP]

"..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

The Time Table Problem (TTP) is well studied in optimization, combinatorics, operations research, and comp sci. In an area of complex problems, this one is hard.
There a lots of techniques and algorithms used and it often depends on the specifics of your problem. Without looking at the details of the problem, there is no way to say what algorithm to apply.
From a quick search in Google the two biggest methods that seem to be pop up for solving the TTP are
Genetic Algorithms
Tabu Search Algorithm

Some background on TTP

, The CTTP classified as NP-complete problem as it incorporation multi-dimensional and multi-objectives. Generating a solution for timetabling by traditional methods is a very difficult effort and requires time to satisfy all problem constraints. The problem constraints can be classified as hard constraints which must not be violated because it effect on the solution feasibility, and soft constraints which can be violated if necessary, but will effect on the solution quality. The objective of timetabling problem is to maximize the number of stratified soft constraint for a feasible solution that is generated by the hard constraints. As the CTTP is a one of the reachable development area, there are many researchers studying this problem and various methodologies are used to solve this type of problem
. Metaheuristics is a fertile field for optimizing the CTTP. The metaheuristics can be divided into Singlebased (Search Trajectory) and Population-based algorithms [11]. There are many single-based algorithms implemented for solving the CTTP such as tabu search [12], simulated annealing [20] and great deluge [18]. Also, the population-based algorithms are used for solving the CTTP for example genetic algorithm [13][15][16] and particle swarm [10][6]. In addition, other techniques are presented such as heuristic [15], hybridized approaches [4][3] and integer programming as a one of methodologies that are used to solve CTTP [14

You can code many of these algorithms in VBA if you understand coding, heuristics, algorithms. I have coded several examples of heuristics for optimizations and assignments.
Shortest Path

Route Planning - shortest path

I'm trying to get my head around using the following data to create the shortest route between 2 places in a map using VBA in either excel or access. ID Name Connection 1 Connection 2 1 Location1 2 2 Location2 3 4 3 Location3 2 4 Location4 2 5 5 Location5 3 5 So...

www.access-programmers.co.uk

Schultze Forced Ranking

Forced ranking using Schultze method

Hi I am trying to build an Access database, where I can force rank a number of choices using the Schultze method. In the attached database I have created a table with respondents, who has ranked 5 choices. The ranking data can be found in the Data table. Schultze method...

www.access-programmers.co.uk

KnapSack Bin Packing

How to find all combinations within a constraint

I am after some code/advice for Access. I have a list of Order Numbers(Unique) and what cubic metres that each are, I also have a cost benefit per Order. I would like to run some code to be able to find every combination of Orders but within a given constraint of Cubic size (65Cube) to find...

www.access-programmers.co.uk

Travelings Salesman
Working implementation of the TSP heuristic using several types of Simulated Annealing improving algorithms.

You can take a look at the code behind these and see if you are up to the task. Understand these are likely much easier problems to formulate since they are not multi objective or multi dimensional.

Now doing this is more than finding an algorithm because they also require efficient data structures. So may need to understand how to make heaps, stacks, link lists, binary trees, graph or perform matrix math. Can you find something out of the box done in Excel or Access? Maybe. The issue I find with these algorithms is that if you problem is slightly different the complexity can be large.

I could probably code a working solution in Access VBA, but it would take a lot of time. And that would depend on how complex the constraints.
This example is done in Excel VBA

I am not familiar with either technique.

 

[gemma-the-husky]

The Time Table Problem (TTP) is well studied in optimization, combinatorics, operations research, and comp sci. In an area of complex problems, this one is hard.
There a lots of techniques and algorithms used and it often depends on the specifics of your problem. Without looking at the details of the problem, there is no way to say what algorithm to apply.
From a quick search in Google the two biggest methods that seem to be pop up for solving the TTP are
Genetic Algorithms
Tabu Search Algorithm

Some background on TTP


You can code many of these algorithms in VBA if you understand coding, heuristics, algorithms. I have coded several examples of heuristics for optimizations and assignments.
Shortest Path

Route Planning - shortest path

I'm trying to get my head around using the following data to create the shortest route between 2 places in a map using VBA in either excel or access. ID Name Connection 1 Connection 2 1 Location1 2 2 Location2 3 4 3 Location3 2 4 Location4 2 5 5 Location5 3 5 So...

www.access-programmers.co.uk

Schultze Forced Ranking

Forced ranking using Schultze method

Hi I am trying to build an Access database, where I can force rank a number of choices using the Schultze method. In the attached database I have created a table with respondents, who has ranked 5 choices. The ranking data can be found in the Data table. Schultze method...

www.access-programmers.co.uk

KnapSack Bin Packing

How to find all combinations within a constraint

I am after some code/advice for Access. I have a list of Order Numbers(Unique) and what cubic metres that each are, I also have a cost benefit per Order. I would like to run some code to be able to find every combination of Orders but within a given constraint of Cubic size (65Cube) to find...

www.access-programmers.co.uk

Travelings Salesman
Working implementation of the TSP heuristic using several types of Simulated Annealing improving algorithms.

You can take a look at the code behind these and see if you are up to the task. Understand these are likely much easier problems to formulate since they are not multi objective or multi dimensional.

Now doing this is more than finding an algorithm because they also require efficient data structures. So may need to understand how to make heaps, stacks, link lists, binary trees, graph or perform matrix math. Can you find something out of the box done in Excel or Access? Maybe. The issue I find with these algorithms is that if you problem is slightly different the complexity can be large.

I could probably code a working solution in Access VBA, but it would take a lot of time. And that would depend on how complex the constraints.
This example is done in Excel VBA

I am not familiar with either technique.

And every one tells me you can have pointers (which you need for most if not all the data structures you mention) in VBA, but I don't think it's easy, as VBA doesn't actually provide an easily accessible pointer data type. I will have a look at the excel example you mentioned.

 

[gemma-the-husky]

It's not payroll that is so hard, the issue in most cases is keeping up with the taxman but you're right. No one develops payroll in house any more.

That's why I said you would need a good insurance policy. If your software deals with salary deductions incorrectly, and there are lots in the UK in addition to tax and social security, I imagine you may well be responsible vicariously.

 

[MajP]

And every one tells me you can have pointers (which you need for most if not all the data structures you mention) in VBA, but I don't think it's easy, as VBA doesn't actually provide an easily accessible pointer data type.

You can build all of those data structures in VBA without a pointer reference. Might not be ideal, but you can.

I will have a look at the excel example you mentioned.

It only discusses the algorithm not the actual implementation in VBA.

 

[isladogs]

In response to some earlier comments, I could write school timetabling software in Access though that wouldn't be my first choice.
However, the reason I could do it is definitely not because I am more skilled than others who have responded in this thread.
I could do it due to having well over a decade of experience in doing school timetabling so I know the complexities involved.

It would still take me hundreds if not thousands of hours to complete
If I were to do this as a commercial application, I would want to ensure it was generic so it could be used by any school and in any country.
Only then would my time investment have any chance of being repaid in sales.

In fact, I wrote a fully featured timetabling application for a specific purpose back in 2005

Curriculum Enrichment Organiser

This is designed to manage all aspects of a school curriculum enrichment programme

www.isladogs.co.uk

It works perfectly (though its far from being my best ever application) and I did think at one time about broadening it to a full timetabling app.
I also wrote other related applications e.g. to manage GCSE options in Year 9.
Again that worked but was no better than commercial software already available

That was when I was young(er) and naive.
I eventually came to realise that it was a foolish endeavour for me to embark upon a full timetabling application