Optimizing regular scheduling objectives: Priority rule based scheduling

Submitted by Mario Vanhoucke on Tue, 01/10/2012 - 16:07

Project scheduling is the act of constructing a timetable for each project activity, respecting the precedence relations and the limited availability of the renewable resources, while optimizing a predefined scheduling objective (see “Resource constrained project scheduling: What is my scheduling objective?”). The presence of resources during project scheduling often leads to a complex scheduling process and hence, simple priority based scheduling rules are used to facilitate this scheduling process.

In this article, the priority rule based scheduling approach is discussed along the three following dimensions:

Priority rule based scheduling: An overview of the general principle of this technique
Priority rules: Assign priorities to project activities and create a ranking
Generation schemes: Assign start and finish times to project activities and construct a schedule

Priority rule based scheduling

Priority rule based scheduling is a simple and quick heuristic scheduling method used to construct feasible schedules for projects with a regular scheduling objective. Three definitions are explained along the following lines:

Heuristic scheduling: Since resource-constrained project scheduling is often a complex algorithmic task, heuristic scheduling is a quick and easy alternative to generate a project schedule without the guarantee that the best possible theoretical solution is found (see “Heuristic project scheduling: Validating the quality of a project schedule”).
Feasible schedule: A feasible schedule should respect the logic of the project network (i.e. the precedence relations) and the limited availability of resources (i.e. the resource conflicts), as explained in “The critical path or the critical chain?: The difference caused by resources”.
Regular scheduling objective: A regular scheduling objective is discussed in “Resource constrained project scheduling: Regular and non-regular scheduling objectives”, for which the minimization of the total duration of the project is probably the most well-known and widely used objective.

A priority rule based scheduling approach consists of two components, a priority rule to determine the list with the rankings of activities and a schedule generation scheme to construct a feasible project schedule based on the constructed activity list. In figure 1, the approach is illustrated graphically and shows that the project data is used to construct a list of activities using a priority rule which is then transformed by a schedule generation scheme into a feasible project baseline schedule.

Figure 1: The priority rule based scheduling approach to construct a feasible project schedule

Priority rules

A priority rule contains information to construct a list of activities that ranks all project activities in a certain order to determine the priorities in which the activities are assigned to the project schedule. Such a list is constructed based on the project data in order to assign priorities to activities, as follows:

Activity information: information about time or cost estimates of the activities determines the activity priorities.
Network information: information on the project network logic determines the activity priorities.
Scheduling information: information obtained from simple critical path scheduling tools determines the activity priorities.
Resource information: information about the project resources determines the activity priorities.

The constructed list is then used and activities are removed one by one from the list and are put in the schedule during the heuristic scheduling process. To that purpose, a schedule generation scheme is used to determine the exact start and finish time of the activity. Examples on priority rule calculations on a fictitious project network can be found in “Optimizing regular scheduling objectives: Priority rule calculations”.

Schedule generation schemes

A schedule generation scheme makes use of the priority list constructed in the previous step and aims at the generation of a feasible schedule by extending the partial schedule (i.e. a schedule where only a subset of the activities has been assigned a starting and finishing time) in a stage-wise fashion. At the start of the heuristic scheduling process, the partial schedule is empty and all activities are available to be scheduled. Afterwards, activities are selected according to their priorities and are put in the schedule following the rules of the generation scheme. Basically, two well-known generation schemes are available, as follows:

Serial schedule generation scheme: selects the activities one by one from the list and schedules it as-soon-as-possible in the schedule.
Parallel schedule generation scheme: selects at each predefined time period the activities available to be scheduled and schedules them in the list as long as enough resources are available.

Illustrations of the use of schedule generation schemes on a project network example are given in “Optimizing regular scheduling objectives: Schedule generation schemes”.

PM Knowledge Center

Optimizing regular scheduling objectives: Priority rule based scheduling