Scheduling Algorithms

[rmfa]

Hi
I would like to know if there is any algorithm, such that if we change a task scheduling or duration, and based on the task dependencies information (defined by SS,SF,FF and FS relations), it automatically relocates every dependent activity, or otherwise informs that changing is not possible without delaying the global project schedule.

Also, are there any efficient algorithms for automatically scheduling, given the task dependencies information (defined by SS,SF,FF and FS relations), the resource needs per task and the resource usage constraints?

Thank you in advance
Rui

[pmkb]

I would like to know if there is any algorithm, such that if we change a task scheduling or duration, and based on the task dependencies information (defined by SS,SF,FF and FS relations), it automatically relocates every dependent activity, or otherwise informs that changing is not possible without delaying the global project schedule.

CPM algorithms describe the method(s) for calculating the Early Start (ES), Early Finish (EF), Late Start (LS) and Late Finish (LF) for all tasks in a schedule network. If you make changes to an element of the schedule network (logic/dependency, duration, etc.), you need to re-calculate the schedule. This will relocate dependent activities and/or improve/delay the critical path.

All CPM scheduling software can do this. Whether the software does it automatically when a change is made or requires the user to initiate a recalculation manually depends upon the software.

Also, are there any efficient algorithms for automatically scheduling, given the task dependencies information (defined by SS,SF,FF and FS relations), the resource needs per task and the resource usage constraints?

Resource leveling is an NP-hard (nondeterministic polynomial-time hard) problem. This means that there is realistically no way to guarantee that the result provided is the optimal result. Resource leveling algorithms must compromise between efficiency (ie. algorithm processes/completes quickly) and sufficiency (finding a near optimal result).

[rickrow]

Resource leveling is indeed, as pmkb states, an NP-hard problem which means there is no guaranteeing that a project schedule is the absolute shortest for the resource constraints and technical dependencies imposed. But that doesn't mean some algorithms may not do reliably better at producing shorter overall project schedules than others on a consistent basis.

A small artificial-intelligence software company in California, [URL="http://www.stottlerhenke.com/"]Stottler-Henke[/URL], believe that their algorithms for automatic scheduling, incorporated in their [URL="http://www.stottlerhenke.com/products/aurora/index.htm"]Aurora software[/URL], can reliably shorten schedules for complex projects by 10 to 30 percent compared with schedules generated with commercial project management software.

Aurora has been used extensively by NASA and [URL="http://www.mdatechnology.net/update.aspx?id=a5378"]Boeing (to schedule assembly of their new 787 Dreamliner)[/URL].

Most input files prepared for Primavera can be run through Aurora, and if you would like Stottler Henke to show you at no cost how much Aurora can shorten your project schedule, please reply to me.

Rick

[davilara]

[url]http://www.stottlerhenke.com/products/aurora/Turnaround/2009-10-01_Aurora_WhitePaper_Turnaround.pdf[/url]

The Sample Schedule provided by Aurora to illustrate their claimed superiority over Primavera P6 might be good for comparison against P6 alone but in the same way Aurora compared their sample schedule I used theirs to compare it to Spider Project and MS Project and found:

•If you schedule the same sample job with MS Project, allowing for activity splitting you will get the minimum 7 days duration, same with Spider Project.

•If you use Spider Project with the option to use Advanced Scheduling Algorithm, no activity splitting and a few prioritization options, you will still get the minimum 7 days schedule instead of the eight days schedule you can get with Aurora. Other Spider Project Options will result in job duration of 8 days, the best Aurora could get.

Therefore, to me, Aurora seems like a waste of money.

In addition, P6 is incapable of correctly modeling shift work as you need to tell in advance how much work is going to be done at each shift, but this is a variable as the schedule moves. Not sure if Aurora solves this issue.

Best regards,
Rafael

[michaelmz]

"Once a set of precedence relations for a project is given, the essential scheduling problem becomes the creation of a Priority List. There are many possible strategies that lead to the creation of a Priority List."