Optimizing regular scheduling objectives: Schedule generation schemes

Figure 1 displays a project network with 11 activities and finish-start precedence relations Each number above the node denotes the estimated duration of the activity while the number below the node is used to refer to the resource demand. The maximum availability of the resource is equal to 6 units (e.g. people) (see “Linking resources to activities: Resource availability and resource demand”).

 

 

A schedule generation scheme determines the way in which a feasible schedule is constructed by assigning start times to the project activities. Both schemes remove activities from the priority list and add them to a partial schedule (i.e. a schedule that starts from an empty schedule and that is gradually built up) until all project activities have a starting time assigned. A serial schedule generation scheme makes use of an activity-incrementation principle while a parallel schedule generation scheme follows a time-incrementation scheme. 

 

Serial schedule generation scheme

 

The activity incrementation approach of a serial schedule generation scheme schedules each activity one at a time and as soon as possible within the precedence and resource constraints. To that purpose,the scheme scans the priority list and selects at each stage the next activity from the priority list in order to schedule it at its first possible starting time without violating both the precedence and resource constraints.

 

This principle can be easily illustrated on the project network of figure 1, using the GCRWC priority rule that results in the activity list [1,2,4,5,3,6,9,7,8,10,11] (see table 1 or “Optimizing regular scheduling objectives: Priority rule calculations”). Figure 2 displays the resulting resource feasible schedule when each activity is added one by one to the partial schedule using the SSGS until all activities are removed from the list. This dynamic process can also be viewed in the animated SSGS approach that can be found at “Animation: Serial schedule generation scheme”.

 

 

Parallel schedule generation scheme

 

A parallel schedule generation scheme iterates over the time horizon of the project (i.e. a time incrementation) instead of iterating over the priority list (i.e. an activity incrementation) and adds activities that are eligible to be scheduled. More precisely, the scheme starts at time point t = 0 and schedules activities before the time pointer is increased. It selects at each decision point t the eligible activities E and assigns a scheduling sequence of these eligible activities according to the priority list. At each decision point, the eligible activities are scheduled with a starting time equal to the decision point (on the condition that there is no resource conflict). Activities that cannot be scheduled due to a resource conflict are skipped and become eligible to schedule at the next decision point t’ > t, which equals the earliest completion time of all activities active at the current decision point t. 

 

This principle can also be easily illustrated on the project network of figure 1 using the same activity list [1,2,4,5,3,6,9,7,8,10,11]. The parallel schedule generation scheme starts with an empty schedule and proceeds as follows: 

 

 

 

Figure 3 displays the resulting resource feasible schedule. This dynamic process can also be viewed in the animated PSGS approach that can be found at “Animation: Parallel schedule generation scheme”.

 

 

Summary

 

Table 1 gives the total project durations that have been found by using both the serial (SSGS) and parallel (PSGS) schedule generation schemes using the various priority rules as discussed in “Optimizing regular scheduling objectives: Priority rule calculations”. For the sake of clarity, the activity lists that result from using these priority rules on the project data of figure 1 are also displayed.

 

Table 1: The priority rules and activity lists used to generate resource feasible schedules by two generation schemes 

(serial and parallel generation scheme) for the example project of figure 1

Priority rule	Activity list	SSGS	PSGS
SPT	[1,2,3,6,4,7,5,8,10,9,11]	24	24
LPT	[1,2,5,4,7,8,3,6,9,10,11]	29	29
MIS	[1,2,4,3,5,6,7,8,9,10,11]	24	24
MTS	[1,2,4,3,5,6,8,7,9,10,11]	24	24
LNRJ	[1,2,4,3,5,8,10,6,9,7,11]	24	24
GRPW	[1,2,4,5,7,3,6,9,8,10,11]	27	27
EST	[1,2,3,4,5,6,7,9,8,10,11]	24	24
EFT	[1,2,3,4,6,5,7,8,9,10,11]	24	24
LST	[1,2,3,5,6,4,9,7,8,10,11]	24	24
LFT	[1,2,3,6,4,5,8,7,9,10,11]	24	24
MSLK	[1,2,3,5,6,9,4,8,10,7,11]	26	26
GRWC	[1,2,4,5,7,8,3,6,9,10,11]	29	29
GCRWC	[1,2,4,5,3,6,9,7,8,10,11]	26	27