SQL recursive common table expression in Project Scheduling practice

Introduction

The following article describes an implementation of a Project Scheduling Engine in Microsoft SQL Server by using recursive common table expression designed for high performance.

The solution provides project forecasting functionality based on predecessor and successor dependencies.

Background

Sometimes the complexity of project scheduling goes beyond the capabilities of commercial software systems like Primavera P6. Because these solutions were designed to fit most of the companies' requirement, they have limitations.  The cost of bypassing these limitations exceeds the cost of building new software which fulfils all the functionality requirement with fairly high performance.

In my case the size and the complexity of the projects ended up with over 3 million milestones in different programmes, different projects and over 7000 different sites. The milestones had cross dependencies between Programmes, Projects, Sites and used different Work Breakdown Structures (WBS).

The solution below shows how to build a single stored procedure to forecast millions of milestones effectively within seconds.

 

Using the code

My sample project is to build a house. To simplify the process I'll have a project start date, then 5 milestones and a housewarming party as the last milestone.

The goal of this exercise is to forecast the date of the housewarming party, by knowing only the project start date and the duration of each activity. 

The engine that we design will update the successor milestones' forecast date if any of the predecessors' forecast date or completed date has changed.

To hold all the milestones which are related to my project, I am creating a table called tblMilestone. 
The table stores the name of the milestones, forecast date, completed date and the duration of that activity.

CREATE TABLE tblMilestone (
    MilestoneId INT IDENTITY(1, 1) ,
    Milestone NVARCHAR(128) NOT NULL ,
    ForecastDate DATETIME NULL ,
    CompletedDate DATETIME NULL ,
    DurationInDays INT NOT NULL
                       DEFAULT ( 0 ) ,
    PRIMARY KEY ( MilestoneId ) )
GO

In this exercise I won't go into details how to fine tune with indexes and unique keys, I try to describe the solution as simple as possible.

At the beginning, the only thing I know is that I will commence the work on a certain date, and the time I allocate to each activity to be finished.
Our plan is to build a process, which updates the forecast date by calculations.

INSERT  INTO dbo.tblMilestone
        ( Milestone, ForecastDate, DurationInDays )<
VALUES  ( N'Project Start', '2016 Feb 1', 0 ),
        ( N'Buy Land', NULL, 30 ),
        ( N'Build Walls', NULL, 20 ),
        ( N'Build Roof', NULL, 15 ),
        ( N'Build Garden', NULL, 30 ),
        ( N'Key Handover', NULL, 2 )    ,
        ( N'Housewarming party', NULL, 5 )

If the project milestones were sequential, we would add sum of duration days to the start date to get the date of the housewarming party. But some of the activity can be started at the same time as others.

 

Only thing I have to do in order to start building the garden is to buy the land, in theory, I can start build the garden at the same time when I build the walls. Even though this is not the most practical approach, but assume for example sake. 

In case of normal parent and child relationship we could store the dependencies in tblMilestone. However, it would limit the number of parent milestone to one.

Let assume, at the time when we have bought the land we will start building the walls and the garden too. After we finished the walls, we can start building the roof.

So the time necessary to build the walls and roof is 35 days and the garden would take 30 days. Therefore the earliest date for the housewarming party when both the activities have finished which is 35 days plus 2 days for the key hand. 

Therefore, in order to kick off the housewarming party we need to finish all the activities.

In project management terms, the key handover milestone has two predecessors
1., Complete building the roof (please note: building the roof milestone has predecessor of building the walls)
2., Complete building the garden

To map this predecessor-successor relationship we need another table.

 

CREATE TABLE tblMilestoneDependency (
    MilestoneDependencyId INT IDENTITY(1, 1) ,
    PredecessorMilestoneId INT NULL --reference of the milestone to be finished before our activity can be started
    ,
    MilestoneId INT NOT NULL --current milestone in question
    ,
    PRIMARY KEY ( MilestoneDependencyId ) )
GO

ALTER TABLE dbo.tblMilestoneDependency
ADD CONSTRAINT FK_tblMilestoneDependency_PredecessorMilestoneId FOREIGN KEY (PredecessorMilestoneId) REFERENCES tblMilestone (MilestoneId)
GO

ALTER TABLE dbo.tblMilestoneDependency
ADD CONSTRAINT FK_tblMilestoneDependency_MilestoneId FOREIGN KEY (MilestoneId) REFERENCES tblMilestone (MilestoneId)

The start milestone has no predecessor, by inserting NULL the process will interpret as start activity

INSERT  INTO dbo.tblMilestoneDependency
        ( PredecessorMilestoneId, MilestoneId )
VALUES  ( NULL, 1 ),
        ( 1, 2 ), -- buy the land when the project started    
        ( 2, 3 ), -- start building the wall when the land has bought
        ( 2, 5 ), -- start building the garden when the land has bought
        ( 3, 4 ), -- start building the roof when the walls are standing
        ( 4, 6 ), -- start organising the key handover when the garden and the roof finished
        ( 5, 6 ),
        ( 6, 7 ) -- start organising the housewawrming party

 

In summary, our project has a "fork" dependency. It includes an example when one milestone has multiple successors, in other words, when one activity finished two other activity can be started.
And also includes example when multiple activities needs to be finished before another can be started. So we can say that our example covers most of the situation in project management. 

 

---

So lets write a query to get the forecast date of the predecessors, add the duration time of the activity and show the new forecast date of the successor.

An easy way would be to loop through the successor milestones and update them with the new forecast date. However the performance of that query would be very low. 

But what would happen when the company runs 50 programme, each has 5-15 projects and each project has about 120 milestones and these milestones needs to be achieved in 7000 different sites?  The milestones sometimes have cross dependency between programmes. For example: In order to start a milestone in Project B another milestone needs to be finished in Project A.

By the fact that the number of milestones can easily go over millions an inefficient scheduler can cause delay in triggering the next activities. 

The query below shows how the second milestone's ForecastDate could be updated from the first milestone. However this script does not go over on the chain, but updates always the next cascading milestone.

SELECT  predm.Milestone PredecessorMilestone ,
        m.Milestone ,
        predm.ForecastDate PredecessorForecastDate ,
        DATEADD(DAY, m.DurationInDays,
                CASE WHEN md.PredecessorMilestoneId IS NULL
                     THEN m.ForecastDate
                     ELSE predm.ForecastDate
                END) ,
        m.DurationInDays
FROM    dbo.tblMilestoneDependency md
INNER JOIN dbo.tblMilestone m
        ON m.MilestoneId = md.MilestoneId -- show all the dependencies of the milestones
LEFT JOIN dbo.tblMilestone predm
        ON predm.MilestoneId = md.PredecessorMilestoneId -- show the name of predecessors if there is any
ORDER BY md.MilestoneId

 

In the result set below, we can see the new forcast date for 'Buy Land' milestone, which is 30 days after 'Project Start' Forecast Date.

 

 

Introducing Recursice Common Table Expression

Fortunately recursive common table expression was introduced in SQL, therefore we are able to populate the chain of milestones with one single query.

Let's modify the previous query and use as the source table in our recursive common table expression.

 

;WITH    cteCurrentSchedule
          AS ( SELECT   predm.Milestone PredecessorMilestone ,
                        m.Milestone ,
                        predm.MilestoneId PredecessorMilestoneId ,
                        m.MilestoneId ,
                        predm.ForecastDate PredecessorForecastDate ,
                        m.ForecastDate ,
                        m.CompletedDate,
                        m.DurationInDays
               FROM     dbo.tblMilestoneDependency md
               INNER JOIN dbo.tblMilestone m
                        ON m.MilestoneId = md.MilestoneId -- show all the dependencies of the milestones
               LEFT JOIN dbo.tblMilestone predm
                        ON predm.MilestoneId = md.PredecessorMilestoneId -- show the name of predecessors if there is any
             ),
        cteNewSchedule
          AS (
--select the start milestones
               SELECT   sch.Milestone ,
                        sch.MilestoneId ,
                        COALESCE(sch.CompletedDate, sch.ForecastDate) ForecastDate ,
                        sch.DurationInDays
               FROM     cteCurrentSchedule sch
               WHERE    sch.PredecessorMilestoneId IS NULL
               UNION ALL
               SELECT   cs.Milestone ,
                        cs.MilestoneId ,
                        COALESCE(cs.CompletedDate,
                                 DATEADD(DAY, cs.DurationInDays,
                                         ns.ForecastDate)) ,
                        cs.DurationInDays
               FROM     cteNewSchedule ns
               INNER JOIN cteCurrentSchedule cs
                        ON ns.MilestoneId = cs.PredecessorMilestoneId
             )
    SELECT  u.Milestone ,
            u.MilestoneId ,
            m.ForecastDate ,
            MAX(u.ForecastDate) NewForecastDate ,
            m.CompletedDate ,
            u.DurationInDays  --take the longest parth if  multiple available
    FROM    cteNewSchedule AS u
    INNER JOIN dbo.tblMilestone m
            ON m.MilestoneId = u.MilestoneId
    GROUP BY u.Milestone ,
            u.MilestoneId ,
            m.ForecastDate ,
            m.CompletedDate ,
            u.DurationInDays
    ORDER BY MAX(u.ForecastDate)

The result set shows the Forecast Date for all the dependant milestones.

With that result, you can update your original table (tblMilestone) with the latest Forecast dates to represent the data on a user control (not covered in this article).

In summary, we can place the logic into the store procedure. When the stored procedure executed it updates the forecast dates if any of the milestone predecessors changed.

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
-- =============================================
-- Author:        <Author, Csaba Hegyi>
-- Create date: <Create Date, 2015 Sep 21>
-- Description:    <Description, This stored procedure updates milestones forecast dates if any of the predecessors' forecast date od completition date changed>
-- =============================================
ALTER PROCEDURE sp_Milestone_Reschedule
AS
BEGIN
    SET NOCOUNT ON;

;WITH    cteCurrentSchedule
      AS ( SELECT   predm.Milestone PredecessorMilestone ,
                    m.Milestone ,
                    predm.MilestoneId PredecessorMilestoneId ,
                    m.MilestoneId ,
                    predm.ForecastDate PredecessorForecastDate ,
                    m.ForecastDate ,
                    m.CompletedDate ,
                    m.DurationInDays
           FROM     dbo.tblMilestoneDependency md
           INNER JOIN dbo.tblMilestone m
                    ON m.MilestoneId = md.MilestoneId -- show all the dependencies of the milestones
           LEFT JOIN dbo.tblMilestone predm
                    ON predm.MilestoneId = md.PredecessorMilestoneId -- show the name of predecessors if there is any
         ),
    cteNewSchedule
      AS (
--select the start milestones
           SELECT   sch.Milestone ,
                    sch.MilestoneId ,
                    COALESCE(sch.CompletedDate, sch.ForecastDate) ForecastDate ,
                    sch.DurationInDays
           FROM     cteCurrentSchedule sch
           WHERE    sch.PredecessorMilestoneId IS NULL
           UNION ALL
           SELECT   cs.Milestone ,
                    cs.MilestoneId ,
                    COALESCE(cs.CompletedDate,
                             DATEADD(DAY, cs.DurationInDays,
                                     ns.ForecastDate)) ,
                    cs.DurationInDays
           FROM     cteNewSchedule ns
           INNER JOIN cteCurrentSchedule cs
                    ON ns.MilestoneId = cs.PredecessorMilestoneId
         ),
         cteLongestPathPerMilestone
         as
         (
         SELECT ns.MilestoneId, MAX(ns.ForecastDate)  ForecastDate FROM cteNewSchedule ns 
         GROUP BY ns.MilestoneId
         )

UPDATE m
SET  ForecastDate = u.ForecastDate
FROM    cteLongestPathPerMilestone AS u
INNER JOIN dbo.tblMilestone m
        ON m.MilestoneId = u.MilestoneId
WHERE m.CompletedDate IS NULL OR m.ForecastDate IS NULL

END
GO

The stored procedure reschedules only milestones where completed date is not entered yet. As an example, I'll update the comleted date for two of the milestones to see how the proc calculates the forecast dates for the successor milestones.

It will use the predecessor milestone's completed date as the source of truth rather than its forecast date.

UPDATE  dbo.tblMilestone
SET     CompletedDate = DATEADD(DAY, 3, ForecastDate)
WHERE   MilestoneId = 1
GO

UPDATE  dbo.tblMilestone
SET     CompletedDate = DATEADD(DAY, 15, ( SELECT    ForecastDate
                                              FROM      dbo.tblMilestone
                                              WHERE     MilestoneId = 1
                                            ))
WHERE   MilestoneId = 2

To see the result:

EXEC sp_Milestone_Reschedule

SELECT * FROM dbo.tblMilestone m

and the result set is:

I hope you enjoyed the article, and if you have any question, please don't hesitate contacting me.

 

Points of Interest

One of the most challenging part was in designing the solution, when a milestone has multiple predecessors, which means one of the predecessor already completed, but the milestone's activity still has to wait untill the longest path completed.

I came across with the solution to calculate the forecast dates for all the possible path, and take the maximum date (longest path) to update the milestone. This is represented in the final select statement as NewForecastDate.

The real application is more complex than this sample project. That sample covers only one milestone dependency type which is "Finish to Start". During the implementation I came up with solution for "Start to Start", "Start to Finish" and "Finish to Finish" scenarios. 

History

No changes yet.