Posted by Jason Kottler on September 12, 2022 | scheduler

Space is Big

Space is big. You just won’t believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think it’s a long way down the road to the chemist’s, but that’s just peanuts to space. – Douglas Adams

Let’s talk about space for a second. Space is made of emptiness and atoms. And estimates of the minimum number of atoms in the observable universe range from around 10^78 to 10^86. That’s a lot of variation, and produces fun things to say, like “ten quadrillion vigintillion” and “one hundred-thousand quadrillion vigintillion” - which sound enough like total nonsense to make the Adams’ quote really land - the numbers are mind-bogglingly big.

Now that we’ve set a baseline for mind-bogglingly immense numbers, let’s talk about problems we’re working to solve here at Administrate, and how the numbers we’re dealing with compare. Let’s discuss the planning problem.

A planning problem is about optimizing a goal, with limited resources, under constraints. The planning problems we’re tackling here at Administrate are about scheduling. A customer might want to plan 100 courses with 5 sessions each over the span of 6 months. Each course can have a different collection of eligible instructors, and each session within those courses can require its own selection of resources (venues, equipment, etc.,). So for scheduling, the goal is to get all the courses scheduled, with limited pools of resources and instructors, with other business constraints like the times and days when learners are available, and so on.

I can hear the question now: What’s this got to do with space?

Planning problems have their own space - a search space. Every possible solution to a problem - viable or not, nonsensical or not - contributes to the search space. Even a small data set will produce an absolutely vast search space. Let’s take a look at how that happens. Say for the sake of argument that each session of a course takes an instructor, a room, and a resource - like a simulator or a CPR dummy.

For the example schedule above, let’s say a company has 7 instructors, 6 rooms, and 4 commercial driving simulators available to deliver these trainings. That’s 500 sessions (100 courses of 5 sessions each) and the calculation is (sessions * rooms * instructors * resources)^time = search space. (500 * 6 * 7 * 4) = 84000 - that’s a big number, sure, but as we are reminded above, just peanuts to space. In the exponential notation used when talking about counting the atoms in the universe, that’s a paltry 8x10^4. But there’s something else in play here - time.

We currently are working with a scheduling resolution of 30 minutes - so a class can start at 10:00 or 10:30, but not at 10:17, for example. Over 6 months there are approximately 8640 half-hours. In the equation above, time is the exponent, so that 84000 is going to get multiplied by itself - over eight. thousand. times.

In case you’re tabbing over to Google Sheets to calculate this let me save you some time - Google Sheets cannot represent this number. It just gets sort of sad and says #NUM!

Turning instead to Wolfram Alpha we find that the answer is (approximately) 6x10^42545.

Now, all of a sudden, space is peanuts in comparison to search space. The number of possible solutions to this problem, the vast majority of which are utterly worthless, is 6x10^42459 times larger than the number of atoms in the universe.

I’m going to just let that sink in for a moment.

OK then.

Let’s continue.

The number of combinations a modern computer can evaluate per year is on the order of 10^20. So clearly, just looking at all the available solutions isn’t an option. We’d need countless computers all cranking for a year to get just one answer - by which time the need for it would have passed and the conditions for it would have changed anyhow.

Instead, we use an AI-powered constraint solving engine that applies multiple optimization strategies and heuristics to prune the search space and find good solutions in a situation where searching for the best solution can take longer than you’ve got - longer than the planet’s got.

Recently we scored a big win by re-implementing our time handling so that we don’t have to check every half-hour in the plan duration (6 months), but only the ones that can possibly begin a session. It turns out that if you take a normal work week – Monday through Friday 9:00 to 17:00 – you eliminate 75% of the half hours in a given span, turning the exponent of 8640 into an exponent of merely 2160.

Reducing that exponent has a massive impact on the size of the search space - reducing it to 2.7x10^10636 - a number 2.1x10^31909 times smaller than the other.

None of these numbers are small. They’re not even huge-yet-comprehensible, like government budget figures. We’re never going to get back into “a trip to the chemist’s” territory, no matter how clever we are. There are simply too many combinations and too great an exponent to produce search spaces smaller than the number of atoms in the observable universe for any but the tiniest of toy problems.

And that’s why, even though space is vastly, hugely, mind-bogglingly big, calling the size of a planning problem “astromonomical” does it a severe injustice.

But with the help of intelligent software and clever reductions of the search space, we will bring the problem back to a comprehensible scope for our users. As far as they’re concerned, they’ll be defining the problem and setting up some constraints. To them, it’ll be a trip to the chemist’s.