Heads up about the business side of this: selling to primary & secondary schools, esp outside of the US, is 8⁄10 difficult.
Specifically, even if the teachers are fully championing your solution, they do not wield any sort of purchasing authority (and sure as hell won’t pay from their own wallet). Purchasing authority’s incentive-structure does not align with “teacher happiness”, “optimal schedule”, or most things one would imagine being the mission of the school. It is, however, critical for them to control all sw used inside the school, and might actively discourage using non-approved vendors.
Whose job is it typically to create the schedule? Do those people have political power in schools?
If your marketing point is “better schedules”, then yes, it is about the benefit for teachers and students, and no one important cares about that. However, if your marketing point is “easier to make schedules”, suddenly the school administration has an incentive to care.
Pure economically driven decisions should win eventually.
For example we have once reduced the number of school buses from 4 to 3. 20% or 160 students come with a bus. That’s 3 full buses or 4 not so full buses. It’s important however, that every arriving student has a class right away. Otherwise he may want to come with a later bus, overcrowding it.
Just on time arriving of those students with just 3 buses was a logistical nightmare. But just a constrain for the digital evolution of the school schedule.
Another big saving is to eliminate the afternoon school shift. We have 2 such cases already evolved.
Evolution. Schedules are competing for being there. Every second 10000 or so are born and are mostly killed by the control program which let live only the top schedules according to the 30+ criteria set in the script.
Random (but perhaps clever) mutation and non-random selection, that’s under the hood.
At first, the top schedule is a random one and not feasible at all. After a million (or a billion, that depends) generations the first feasible one appears and from there on, evolution produces more and more perfect schedules.
For every processor core, at least one evolution is going on. Each at least slightly different one. The program can spread across many computers and there may be as many as 100 or more parallel evolutions going on. They talk occasionally (via internet) and exchange their champions.
It has been 10 years long real life experiment, which went very well. A lot of schools involved, teachers and students and some academic papers published. Now it’s time to spread it.
so, parallel genetic algorithm based scheduling app with (ranked?) constraints?
In what way is it more automatic than existing similar apps?
presumably you still need to give it a list of constraints (say a few thousand constraints), possibly in a spreadsheet, some soft, some hard and it spits out a few of the top solutions or presumably an error if the hard constraints cannot be met?
I wouldn’t say it’s “genetic algorithm”, I prefer the term “evolution algorithm”.
In what way is it more automatic than existing similar apps?
We did some testings. For example, we took some existing schedules and optimized them with our tool. The difference was substantial.
We also did some packings of circles inside a square and some spheres inside a cube, denser than it has been previously achieved.
We have built some 3D croswords 8 by 8 by 8 letters with no black field at all—field with English words.
I don’t know if optalaner can do the same. I think not.
spreadsheet, some soft, some hard and it spits out a few of the top solutions
Every constrain has its own user specified weight. From 0 to 10^12 and every integer inside this interval. This is the measure of how soft or hard a constrain is.
Did you also test what other software (optaplanner as mentioned by HungryHobo, any SAT solver or similar tool) can do to improve those same schedules?
Did you run your software on some standard benchmark? There exists a thing called the international timetabling competition, with publicly available datasets.
Sorry to be skeptical, but scheduling is an NP-hard problem with many practical applications and tons of research has already been done in this area. I will grant that many small organizations don’t have the know-how to set up an automated tool, so there may still be a niche for you, specially if you target a specific market segment and focus on making it as painless as possible.
We did some benchmarks. Sometimes we did it well, sometimes not that well.
For example in the case of Job Shop Scheduling benchmark we were unable to break a single record. There are records waiting to be break in JSS area, but we haven’t broken a single one.
But we are still holding some (years old) packing records right now.
One may say, that JSS is the base of every scheduling and that packing is not. In fact, the real life scheduling is more complicated than either one of those benchmarks. We have many more constrains in real life. And it turns out, that many constrains somehow help the evolution to find trade-offs.
The best way to win principals is to show them that a ridiculously complex constrain may be applied and calculated automatically.
4.5 school hours of S per week (4 hours on odd weeks and 5 hours on even weeks)
when there is the fifth hour in the week, then this hour may be the second hour of the subject S on that day
if it is on the same day, it should be immediately after the previous hour of the subject S
in the above case, it must be the last hour for the teacher
three classes of students are divided into 5 groups for the subject S
there are 4 teachers for those 5 groups, one teacher teaches groups number 2 and 4
there is a given list of students for groups 1, 3 and 5 and a combined list for students for groups 2 and 4
computer should divide the combined list into two separated lists (2 and 4) but they must not differ for more than 4 students in size
as one of those groups (2 or 4) are always idle, the subject M which is equally divided, must be taught then—or the S should be the first hour of the day
for there are only 4 hours of subject M per week
there are only 3 teachers of M
there are also 3 hours of subject A per week for those same students in 5 differently set groups
there are 5 teachers of A, but one of them also teaches the group number 1 of S
it would be nice but not mandatory if the number of waiting hours for students were 0
This is a real life example, I have discussed 1 hour ago with one of the teachers (math teacher) in one of our schools. It is not the most complex demand we had, by far.
S = Slovenian language
M = Math
A = Anglescina (guess what that is)
fair enough, I was underwhelmed by your initial post describing it but I agree that showing that your system can handle weird constraints in real examples is an excellent demonstration.
The record thing to me just happens to be a good demonstration that you’re not just another little startup with some crappy schedualling software, you’re actually at the top of the field in some areas.
I know that. But my focus in this thread are North America’s schools as a big market.
But yes—how good this algorithm really is? Where is its optimal domain?
I guess, evolving algorithms is the best usage. Either from a previous known algorithm, either from scratch, either from data. Like evolving Kepler’s law from planetary data. I wrote a post about that here, a few years ago.
The thing is, it’s a very fragmented market. The US schools are local, basically run at the town level, so for you it is essentially a retail market with a large number of customers each of which buys little. I’m guessing that you’ll need a large sales organization to break in.
Or possibly to find an existing company selling office/organization/planning software that’s already got a big share of the market and selling them license to the tech.
Does the solution space support this? I can imagine a schedule that only violates 1 criterium, but the nearest correct solution is far away from it. (Seems to me the schedules are similar to 3-SAT in this aspect.)
Does the solution space support this? I can imagine a schedule that only violates 1 criterium, but the nearest correct solution is far away from it.
This is indeed a big and fundamental problem. If 1 criterium only is violated and this persists for many millions of generations, the control program sees this semi-solution as worse and worse. Much worse than a 2 or 4 criteriums miss. So it’s then killed.
It’s even more complicated than that. Several such tricks are employed and this problem almost vanishes.
I used to make schedules with aSc TimeTables years ago. There is a free demo available. Could you compare your approach with this app?
The application is fully automatic, in the sense that you first enter all the data and constraints, and then you run the computation. (There is an option to put some items on specific place and “lock” them there, but this is strongly discouraged unless you really know what you are doing. Essentially, you can do it to speed up the computation if you have a logical proof that certain things must be done some way, but the application can’t notice that and keeps wasting CPU time with alternative approaches.) As far as I know, the numbers of teachers / students / rooms / subjects are not limited, but of course their number has an impact on the complexity of the computation.
The complexity of constrains for each student or teacher is much greater with our software than with aSc. The scripting language is much more complex and enables you to describe pretty much every whim one might have. Like a different speed, teachers have between two different locations or after how many classes a break is mandatory for a specified teacher … and many more.
It’s student oriented primary and every student can have a very different curriculum then everybody else.
Still, all this will be automatically calculated and then optimized.
Now, we want to see how it will behave in practice for North America and Australia.
Not an average, no. But at every other school, there is at least one teacher who is able to do it (for the entire school, of course) . Some like to work in pairs when scripting it.
I thought, I might find some among readers and contributors here as well. Looking for people with this (hard) problem.
Say, that you have a school with about 100 teachers, 1000 students, 25 rooms … Each having his/hers demands and constraints.
Now, you want an optimal schedule—who doesn’t. For that I have a software to do it automatically. Not semi-automatically like everyone else.
I want to test it for the North America and Australia’s primary and secondary schools on several real life examples. For free, of course.
I am looking for a principal or his assistant to try this together over Skype.
Heads up about the business side of this: selling to primary & secondary schools, esp outside of the US, is 8⁄10 difficult.
Specifically, even if the teachers are fully championing your solution, they do not wield any sort of purchasing authority (and sure as hell won’t pay from their own wallet). Purchasing authority’s incentive-structure does not align with “teacher happiness”, “optimal schedule”, or most things one would imagine being the mission of the school. It is, however, critical for them to control all sw used inside the school, and might actively discourage using non-approved vendors.
Whose job is it typically to create the schedule? Do those people have political power in schools?
If your marketing point is “better schedules”, then yes, it is about the benefit for teachers and students, and no one important cares about that. However, if your marketing point is “easier to make schedules”, suddenly the school administration has an incentive to care.
Pure economically driven decisions should win eventually.
For example we have once reduced the number of school buses from 4 to 3. 20% or 160 students come with a bus. That’s 3 full buses or 4 not so full buses. It’s important however, that every arriving student has a class right away. Otherwise he may want to come with a later bus, overcrowding it.
Just on time arriving of those students with just 3 buses was a logistical nightmare. But just a constrain for the digital evolution of the school schedule.
Another big saving is to eliminate the afternoon school shift. We have 2 such cases already evolved.
Only in the realm of spherical cows in vacuum.
Also known as “The markets can stay irrational longer than you can stay solvent”.
What optimization method are you using under the hood, if you don’t mind me asking?
Evolution. Schedules are competing for being there. Every second 10000 or so are born and are mostly killed by the control program which let live only the top schedules according to the 30+ criteria set in the script.
Random (but perhaps clever) mutation and non-random selection, that’s under the hood.
At first, the top schedule is a random one and not feasible at all. After a million (or a billion, that depends) generations the first feasible one appears and from there on, evolution produces more and more perfect schedules.
For every processor core, at least one evolution is going on. Each at least slightly different one. The program can spread across many computers and there may be as many as 100 or more parallel evolutions going on. They talk occasionally (via internet) and exchange their champions.
It has been 10 years long real life experiment, which went very well. A lot of schools involved, teachers and students and some academic papers published. Now it’s time to spread it.
so, parallel genetic algorithm based scheduling app with (ranked?) constraints?
In what way is it more automatic than existing similar apps?
presumably you still need to give it a list of constraints (say a few thousand constraints), possibly in a spreadsheet, some soft, some hard and it spits out a few of the top solutions or presumably an error if the hard constraints cannot be met?
What can it do that, say, optaplanner can’t do?
I wouldn’t say it’s “genetic algorithm”, I prefer the term “evolution algorithm”.
We did some testings. For example, we took some existing schedules and optimized them with our tool. The difference was substantial.
We also did some packings of circles inside a square and some spheres inside a cube, denser than it has been previously achieved.
We have built some 3D croswords 8 by 8 by 8 letters with no black field at all—field with English words.
I don’t know if optalaner can do the same. I think not.
Every constrain has its own user specified weight. From 0 to 10^12 and every integer inside this interval. This is the measure of how soft or hard a constrain is.
Did you also test what other software (optaplanner as mentioned by HungryHobo, any SAT solver or similar tool) can do to improve those same schedules?
Did you run your software on some standard benchmark? There exists a thing called the international timetabling competition, with publicly available datasets.
Sorry to be skeptical, but scheduling is an NP-hard problem with many practical applications and tons of research has already been done in this area. I will grant that many small organizations don’t have the know-how to set up an automated tool, so there may still be a niche for you, specially if you target a specific market segment and focus on making it as painless as possible.
We did some benchmarks. Sometimes we did it well, sometimes not that well.
For example in the case of Job Shop Scheduling benchmark we were unable to break a single record. There are records waiting to be break in JSS area, but we haven’t broken a single one.
But we are still holding some (years old) packing records right now.
One may say, that JSS is the base of every scheduling and that packing is not. In fact, the real life scheduling is more complicated than either one of those benchmarks. We have many more constrains in real life. And it turns out, that many constrains somehow help the evolution to find trade-offs.
if you’re the holders of some records for certain problem types then that grabs my interest.
I’d suggest leading with that since it’s a strong one.
Not necessarily for their target market.
I belief that being flexible about target markets is one of the major ways businesses grow.
The best way to win principals is to show them that a ridiculously complex constrain may be applied and calculated automatically.
4.5 school hours of S per week (4 hours on odd weeks and 5 hours on even weeks)
when there is the fifth hour in the week, then this hour may be the second hour of the subject S on that day
if it is on the same day, it should be immediately after the previous hour of the subject S
in the above case, it must be the last hour for the teacher
three classes of students are divided into 5 groups for the subject S
there are 4 teachers for those 5 groups, one teacher teaches groups number 2 and 4
there is a given list of students for groups 1, 3 and 5 and a combined list for students for groups 2 and 4
computer should divide the combined list into two separated lists (2 and 4) but they must not differ for more than 4 students in size
as one of those groups (2 or 4) are always idle, the subject M which is equally divided, must be taught then—or the S should be the first hour of the day
for there are only 4 hours of subject M per week
there are only 3 teachers of M
there are also 3 hours of subject A per week for those same students in 5 differently set groups
there are 5 teachers of A, but one of them also teaches the group number 1 of S
it would be nice but not mandatory if the number of waiting hours for students were 0
This is a real life example, I have discussed 1 hour ago with one of the teachers (math teacher) in one of our schools. It is not the most complex demand we had, by far.
S = Slovenian language M = Math A = Anglescina (guess what that is)
fair enough, I was underwhelmed by your initial post describing it but I agree that showing that your system can handle weird constraints in real examples is an excellent demonstration.
The record thing to me just happens to be a good demonstration that you’re not just another little startup with some crappy schedualling software, you’re actually at the top of the field in some areas.
If your algorithm is actually the best-of-class for this problem, there are serious applications for it outside of schools.
I know that. But my focus in this thread are North America’s schools as a big market.
But yes—how good this algorithm really is? Where is its optimal domain?
I guess, evolving algorithms is the best usage. Either from a previous known algorithm, either from scratch, either from data. Like evolving Kepler’s law from planetary data. I wrote a post about that here, a few years ago.
http://lesswrong.com/lw/9pl/automatic_programming_an_example/
The thing is, it’s a very fragmented market. The US schools are local, basically run at the town level, so for you it is essentially a retail market with a large number of customers each of which buys little. I’m guessing that you’ll need a large sales organization to break in.
Or possibly to find an existing company selling office/organization/planning software that’s already got a big share of the market and selling them license to the tech.
Does the solution space support this? I can imagine a schedule that only violates 1 criterium, but the nearest correct solution is far away from it. (Seems to me the schedules are similar to 3-SAT in this aspect.)
This is indeed a big and fundamental problem. If 1 criterium only is violated and this persists for many millions of generations, the control program sees this semi-solution as worse and worse. Much worse than a 2 or 4 criteriums miss. So it’s then killed.
It’s even more complicated than that. Several such tricks are employed and this problem almost vanishes.
I used to make schedules with aSc TimeTables years ago. There is a free demo available. Could you compare your approach with this app?
The application is fully automatic, in the sense that you first enter all the data and constraints, and then you run the computation. (There is an option to put some items on specific place and “lock” them there, but this is strongly discouraged unless you really know what you are doing. Essentially, you can do it to speed up the computation if you have a logical proof that certain things must be done some way, but the application can’t notice that and keeps wasting CPU time with alternative approaches.) As far as I know, the numbers of teachers / students / rooms / subjects are not limited, but of course their number has an impact on the complexity of the computation.
The complexity of constrains for each student or teacher is much greater with our software than with aSc. The scripting language is much more complex and enables you to describe pretty much every whim one might have. Like a different speed, teachers have between two different locations or after how many classes a break is mandatory for a specified teacher … and many more.
It’s student oriented primary and every student can have a very different curriculum then everybody else.
Still, all this will be automatically calculated and then optimized.
Now, we want to see how it will behave in practice for North America and Australia.
Sounds great! I hope you don’t expect average teachers to write the scripts though.
Not an average, no. But at every other school, there is at least one teacher who is able to do it (for the entire school, of course) . Some like to work in pairs when scripting it.
I thought, I might find some among readers and contributors here as well. Looking for people with this (hard) problem.