The Resource Constrained Project Scheduling Problem

No doubt, project management is a hot topic. Just googling for it will turn up thousands of methods, companies, software packages and consultants that deal with it. The reason for this is simple: work does not really scale well. A hundred people can not do a hundred times the work that a single person can do, but much, much less. This is due to the overhead of organizing the work, people stepping on each other's toes and the fact that some things just can not be sped up. Some tasks are much more friendly to paralellizing than others, and unfortunately the ones that are not are getting more and more important.

Project management has a lot of aspects, one of them is creating an optimal schedule or work plan: finding out when to do what. Failing to create such a schedule in any non-trivial project will most certainly lead to delays, contract violations and a lot of wasted money. Unfortunately creating such a schedule is a very difficult problem, NP-hard to be exact. This means that there is no way to find a perfect solution in polynomial time complexity, or even simpler: you will not find the perfect solution for any reasonably complex case.

This may sound frustrating, but it actually isn't that bad: you don't need to find the perfect solution, it usually is sufficient to find a good solution. Over time, a number of heuristics have been developed that find good solutions for the project scheduling problem, e.g. the critical path method. Unfortunately it can be proven that any simple or ``local'' heuristic creates suboptimal solutions in many cases and will even create really terrible solutions in some cases. The bottom line: if you are using local heuristics for project scheduling, you are doing something wrong.