GNOME Bugzilla – Bug 340340
feature request: resource leveling
Last modified: 2009-05-21 23:50:09 UTC
It would be very helpful for planner to do "resource leveling". That is, if I schedule independent tasks for the same "resource"/person, planner should give me a mechanism to avoid overscheduling the person. Currently, I have to create artificial dependencies between tasks, or artificially adjust a task start date. Planner should let me automatically adjust start times (perhaps based on task priorities) and/or reduce the percentage time spent on several tasks.
Planner uses an activity on node model. However, the algorithms for managing projects were developed back in the 60s for use by activity on arc networks e.g. CPM/PERT. This makes a lot of things tricky - we need to remember that the representation used by planner is the DUAL of the project network. Resource levelling is NP-HARD that is it is even worse than NP-Complete. Even for small numbers of resources levelling is VERY time consuming. It is also a whole network operation. To be useful, planner MUST include resource levelling - some commentators are correct when they say `that is what a planner is'. Also, it should support uncertain durations if it is going to be useful. Question: Can the present design be used to support these functions ? Ans: I really don't know, but somehow we need to prove
Planner uses an activity on node model. However, the algorithms for managing projects were developed back in the 60s for use by activity on arc networks e.g. CPM/PERT. This makes a lot of things tricky - we need to remember that the representation used by planner is the DUAL of the project network. Resource levelling is NP-HARD that is it is even worse than NP-Complete. Even for small numbers of resources levelling is VERY time consuming. It is also a whole network operation. To be useful, planner MUST include resource levelling - some commentators are correct when they say `that is what a planner is'. Also, it should support uncertain durations if it is going to be useful. Question: Can the present design be used to support these functions ? Ans: I really don't know :( Possibility 1. No. I think this is a real possibility in which case we would need to be realistic about the need for a planner that is consistent with the operations research methodology. Possibility 2. There are newer algorithms for task on node networks (there should be a collection of theory papers associated with Planner!). Possibility 3. Yes, probably though we need some view of the plan network i.e. a view of the inverse dual network of the Planner representation. a) There should be a unique start node b) There should be a unique end node c) Sometimes dummy activities are needed to ensure that no two tasks (represented as nodes in planner) connect the same two nodes (represented as ??? in planner - the node relations I suppose). Given that this were true then resource levelling can be solved in exponential time using a linear program solver like GLPK or lpsolve. Usually heuristics are used for this. Then there would be a button or menu option called `Level Resources' to press. I'm happy to review the operations research stuff and post back but I have a bad feeling that resource levelling could have been a better starting point for a planner than a ghantt chart (which is for displaying properties of the net you have) and that the architecture is weak. On the +ve side - nice ui and the API should hold up ok.
I would like to second that this is an important feature in a project planner and look forward the release when it is implemented.
*** This bug has been marked as a duplicate of 132917 ***