Resource leveling, searching the space of orderings
This is the second entry in a series on resource leveling.
At Planlab we often create bespoke algorithms to maximise performance. This one makes the search for good solutions to resource-constrained projects much more tractable.
In Daniel's last blog post, we talked about project scheduling with resource constraints. We introduced Activity Iteration Resource Leveling (AIRL).
Most projects feature prerequisites, that by definition tell you when one task must wait for another. But if there's a limited (renewable) resource, we also know a certain set of tasks can't happen simultaneously. Then we need an external notion of which one must wait for the other, in case there's a conflict. A tiebreaker.
Resource constraints naturally lead to the idea of priority: an ordered list of the tasks, which is mathematically a permutation. In turn, this means that permutations are a natural and efficient representation of a given solution to the resource constrained scheduling problem.
If two activities compete for the same limiting resource, the priority order tells you which takes precedence. The algorithm that does this is called AIRL. How resource constraints can prevent things happening at the same time, if it's not obvious, is explained in the previous post. Going forward, just assume AIRL is a box that takes a priority order, and a set of tasks in a project, and tells you a schedule: when everything should actually run: a Gantt chart.
If we want to search around for a good solution to the project, and we have a map (AIRL) from priority orders to schedules, we would do well to start from the representation of priorities.
What makes a 'good solution' is up to you. Typically, we would look at the total duration of the solution, and try to minimize it. But you may also say that you care about solutions that don't use water in the summer, or hit certain intermediate deadlines, or have manageable working hours. You can price that in however you like.
The priority order should be a topological ordering of the project.
Topological orderings
What is the topological order? A project is a directed graph. If you could only do one activity at a time, a topological order would be an order allowed by the graph. I.e. when every activity's time comes, its predecessors are already done. It's guaranteed if, for every edge in the graph (every prerequisite), the pre-activity is earlier in the order than the post activity. In other words, all the prereqs arrows are pointing forwards.
Imagine building a skyscraper, and each story is a task. Then there's only one topological order. But if you're building a bungalow park of N bungalows, and each house is a task, you have N! topological orders. (Every order is fine, because there's no prerequisites).
For anything in between, you can construct the topological order by starting with any activity that has no prerequisites. That's the first element. Each next one is picked freely from the tasks that have no unscheduled prereqs. Because it's a Directed Acyclic Graph (DAG), we'll place them all. It should be clear that, while most orderings are not topological in general, there are still a great many that are, for projects that aren't overly constrained.
The priority order doesn't have to be topologically sorted for it to work in AIRL, but having an activity with a higher priority than its predecessors has no effect on the solution. You could SAY: "If we ever have a conflict between digging the foundation, and building the roof, build the roof first", but it will never be relevant. You should only make priority orders that give relative priority to things that could actually compete for their placement. All the non-topo-ordered ones map to the same solution as at least one topo-ordered one.
So using AIRL, we can restrict ourselves to topological orderings, and they will map to all the solutions we used to be able to.
Searching a sensible space
In optimization, a general rule is that most of the battle is won if you can search a SENSIBLE space. By this we mean: no redundant moves in the space are even possible. Each state you visit, by construction, has a good chance of being a good solution. Even better if they're all unique.
It can take a long time to look for your keys. If you include in your search the surface of the moon, the center of the earth, and sometimes look at the same place 500 times at varying angles, it's positively hopeless. You want to look for your keys only in places where you've recently visited, and each place you check should be a couple inches from the past attempt.
Over and over we discover at Planlab, that a dumb algorithm searching a smartly represented space, outperforms a smart algorithm searching a dumbly represented space. It's frustratingly effective to spend some good physical insight reducing the problem to a very efficient representation, and then dusting off the well-tested simulated annealing. No need for very smart general purpose solvers. Dumb general purpose solvers are the way to go.
State spaces are BIG. The space of topological orderings of N activities is typically superexponential in N, and it in fact already represents a dramatic reduction compared to the 'out of the box' way of getting priorities. That would be choosing a point in RN, each dimension corresponding to an activity, and inferring an order by sorting them. That's the native way of doing simulated annealing: finding a spot in N-dimensional space that somehow reduces an objective function. It's worse on two counts:
- Many points in RN map to the same permutation
- Most permutations aren't topologically ordered
Simulated annealing
Now, there's great literature on simulated annealing. We won't repeat it, and for the present purpose, we only need to know a few things.
It's a method to take a state, check its score, make a small modification to the state, check again, etc etc, until you find the best score. It only needs:
- a score box that takes a state and outputs a score
- a move box that takes a state, and outputs another state
It will generally only 'accept' moves that form an improvement, but early on it will concede some ground to get over barriers into the real optima.
It's what we use, because it's better than a hill climber for avoiding local optima, and it doesn't actually need a smooth space with differentiable coordinates. Our only job is to build the state space, the move box, and the score box.
We've already decided the state space: it's the space of topological orderings of the project. We've also discussed how to get the score box: put the permutation and the project into AIRL, get a solution schedule (what happens when, resource usage respects limits). Then you decide how good you like that schedule, and output a number. E.g. the number of days you're early on delivery.
The move box
The big question, is then: the move box. What we want, is when you start with a topological ordering, that you can make a move, and you get another permutation that is still a topological ordering of the project. How to do that?
Well, let's go back to the description "all the arrows are pointing forward". It's quite obvious: take an ordering, any old ordering, and pick a random activity. You can move it forward until one of the arrows going out of it would point backwards. Or backwards, until any arrow going into it would point backwards. You only need to look at the arrows on THAT activity, so it's very easy.
In the example above, we could move E right: swapping with F. But not another spot (it would be after G). We could move it left one spot, swapping with D. But not another (it would be before C).
Now, in practice, our move box might do this process any number of times, more in the beginning to cover more ground, fewer later to be more sensitive. And you might use information on what activities are likely causing blockages and try moving more often. These are details we use to refine the core idea.
Stay tuned for part three where we explain how we applied this machinery to some real-world projects.
