This is part 3 of a series of posts on software project management. The series starts with Managing Software Projects Part 1: Tools. Start there to get the whole story.
When you are heading out to run errands, it’s not too hard to figure out in what order you will go to the cleaners and the gas station and the grocery store but such intuitive scheduling doesn’t scale well. With dozens of tasks being done by a handful of people, you really want a computer to do the heavy lifting.
As I started working on automatic scheduling of Trac tickets, I did a bit of research and found that this is what academics call the Resource Constrained Project Scheduling Problem. A resource can be anything from a developer’s time to the capacity of a roadway. Your project schedule can’t exceed the constraints imposed by the availability of the resource. Your developer can’t work 25 hours a day and a one-lane dirt road can only accommodate so many cement trucks at a time.
Digging deeper, I found that academics have reference projects and their research is into how to efficiently find the best (usually shortest) schedule for a fixed set of activities and resources. In the end, they are talking about squeezing a few percent out of the time it takes to complete a project. Software project scheduling — at least as I practice it — is very different. The set of tasks is dynamic and the margin of error in the estimates is often 100%. Clearly rigorous academic thinking was not what I was looking for.
My research did turn up a useful technique, however. Several areas of research revolved around a Serial Schedule Generation Scheme. At it’s simplest, SSGS is straightforward and easy to implement; I’ve done it twice in Python and once in Perl. The basic idea is:
- Find eligible tasks
- No incomplete predecessors
- Resource is available
- Sort eligible tasks
- Bugs before enhancements
- High risk before low
- Fragile code base before stable
- Schedule one task
- Find more eligible
- Repeat at Sort
Like many templates, this one gets its power and flexibility from being able to customize steps.
The scheduler in TracPM gets resource availability from an implementation of IResourceCalendar.
class IResourceCalendar(Interface):
# Return the number of hours available for the resource
# on the specified date.
def hoursAvailable(self, date, resource = None):
"""Called to see how many hours are available on date"""The IResourceCalendar implementation in Team Calendar returns 0 or 8 based on whether the developer is in or out that day but more flexible calendars could return, for example, 4 hours per day for a developer who is only available half time.
The scheduler sorts tasks with an implementation of ITaskSorter:
class ITaskSorter(Interface):
# Process task list to precompute keys or otherwise make
# compareTasks() more efficient.
def prepareTasks(self, ticketsByID):
"""Called to prepare tasks for sorting."""
# Provide a compare function for sorting tasks.
# May be used as cmp argument for sorted(), and list.sort().
# Returns -1 if t1 < t2.
def compareTasks(self, t1, t2):
"""Called to compare two tasks"""TracPM includes a simple sorter but I use a small, in-house plugin that expresses our business rules.
Critical Path
The really interesting work in a project occurs on the critical path. The critical path is interesting because any delay in completing a task on the CP delays the completion of the project. That explanation doesn’t lead to a natural or obvious means of finding those tasks but I did turn up a brute force algorithm that works quite well for dozens or hundreds of tasks:
- Starting now, compute the ASAP schedule
- Starting at the end of the ASAP schedule, compute ALAP schedule
- Find tasks that have the same start and finish time in both schedules
Next Time
In my next post, I’ll explore using the critical path tasks and task estimates to estimate project completion.