calculate gantt chart total duration

Question

I'm creating a gantt-like chart (configuration really) and need to calculate total duration and validate configurable durations. The goal is that users can build the gantt chart without knowing dates, but by knowing tasks and how they (loosely) relate. In a previous step, users add tasks and select start & end steps for those tasks. Steps have a fixed order. Actual dates are not known (or relevant) but will be mapped to steps later.

Most gantt tools I've seen rely on knowing the start/end dates and don't do calculations.

How should I calculate the total duration and also validate when a duration is invalid? Obviously in some cases a total can't be calculated: if there is an unused step between activities. A simple invalid duration would occur when 2 tasks share the same start and end date but have different values. A more complicated one would occur when 2 or more activities have different start/end steps and overlap.

I'm not looking for a complete solution (it would probably be of little use with my current code anyway), but more a general algorithm or approach. I would think a recursive solution would make sense, but because I'm doing this with JS/jQuery/DOM, I'm concerned about performance of a recursive solution that has to repeatedly look up elements. Should I start calculating from the end or the beginning? should I follow each step's start/end until I go no further or re-evaluate which step to add to total duration mid-way through?

Here is a picture of the current markup:

Answer 1

I'll try to explain what I wound up doing.

I think to follow you have to know a bit about the requirements. This interactive/configurable gantt/schedule is being used as a template to estimate production timelines.

There are 3 pieces:

• Steps
• Activities
• Durations of activities, which are different depending on the type of item the schedule is applied to.

Since this is a template used for estimation, initially there are no dates - just arbitrary durations tied to activities mapped to steps. However eventually steps get mapped to dates from an imported report (or manually entered).

There are 3 pages where the user incrementally builds up the schedule:

• Add/Edit Steps: Steps are rows which are created with a sort order value (inferred)
• Add/Edit Activities: A matrix with Steps as columns, Activities as rows. Every intersection is a checkbox. A Start and End Step must be selected for each Activity.
• Add/Edit Durations: An item type is selected and durations are added for each activity.

Classes

• Step [ Name, StepOrder, ..]
• Activity [ Name, StartStepID, StartStepOrder, EndStepID, EndStepOrder, ..]
• ActivityDuration : Activity [ Duration, ItemType, ..]

In MVC Controller/Repository:

        // start by ordering the durations by the order of the steps
        var sortedActivities = durations
            .OrderBy(x => x.StartStepOrder)
            .ThenBy(x => x.EndStepOrder);

        // create func to get the path name from the old + new activity
        var getActivityPath = new Func<string, string, string>(
            (prevPath, activityID) =>
            {
                return string.IsNullOrEmpty(prevPath)
                    ? string.Format("{0}", activityID)
                    : string.Format("{0}.{1}", prevPath, activityID);
            });

        // create the recursive func we'll call to do all the work
        Action<List<ActivityDuration>, string, long?, IEnumerable<ActivityDuration>> buildPaths = null;
        buildPaths = (activities, path, startStepID, starts) =>
        {
            // activities will be null until we are joining gapped paths, 
            // so grab the activities with the provided startStepID
            if (starts == null)
                starts = activities.Where(x => x.StartStepID == startStepID);

            // each activity represents a new branch in the path
            foreach (var activity in starts)
            {
                var newPath = getActivityPath(path, activity.Id.ToString());

                // add the new path and it's ordered collection 
                // of activities to the collection
                if (string.IsNullOrEmpty(path))
                {
                    paths.Add(newPath, new ActivityDuration[] { activity });
                }
                else
                {
                    paths.Add(newPath, paths[path].Concat(new ActivityDuration[] { activity }));
                }

                // do this recursively providing the EndStepID as the new Start
                buildPaths(activities, newPath, activity.EndStepID, null);
            }

            // if there were any new branches, remove the previous 
            // path from the collection
            if (starts.Any() && !string.IsNullOrEmpty(path))
            {
                paths.Remove(path);
            }
        };


        // since the activities are in step order, the first activity's 
        // StartStepID will be where all paths start.
        var firstStepID = sortedActivities.FirstOrDefault().StartStepID;

        // call the recursive function starting with the first step
        buildPaths(sortedActivities.ToList(), null, firstStepID, null);

        // handle gaps in the paths after all the first connected ones have been pathed.
        //   :: ie - step 1,2 & 4,5 are mapped, but not step 3
        // these would be appended to the longest path with a step order < start step of the gapped activity's start step (!!!) 
        //   :: ie - the path should be 1-2,2-4,4-5)

        // because the list of paths can grow, we need to keep track of the count
        // and loop until there are no more paths added
        var beforeCount = paths.Count;
        var afterCount = beforeCount + 1;
        while (beforeCount < afterCount)
        {
            foreach (var path in paths.ToArray())
            {
                var lastActivity = path.Value.Last();
                // check for activities that start after the last one in each path .. 
                // .. that don't start on another activity's end step (because that would be a part of a path already)
                var gapped = sortedActivities
                    .Where(x => x.StartStepOrder > lastActivity.EndStepOrder)
                    .Where(thisAct =>
                        !sortedActivities
                            .Select(otherAct => otherAct.EndStepID)
                            .Contains(thisAct.StartStepID)
                    );

                beforeCount = paths.Count;
                // for each new gapped path, build paths as if it was specified by the previous activity
                buildPaths(sortedActivities.ToList(), path.Key, null, gapped);
                afterCount = paths.Count;
            }
        }

        // build up an object that can be returned to 
        // JS with summations and ordering already done.
        rValue = new ActivityPaths()
        {
            Paths = paths
                .Select(x => new ActivityPath()
                {
                    Path = x.Key,
                    ActivityDurations = x.Value,
                    TotalDuration = x.Value.Sum(y => y.Duration)
                })
                .OrderByDescending(x => x.TotalDuration)
        };

There are admittedly some shortcomings of this design, but the use cases allow for it. Specifically: - An activity can't directly have more than one dependent step - or in other words - 2 steps can't have the same step order. - If 2 paths have the same total duration, only one will show as the critical path.

Since the dates which are mapped to steps are ultimately used to calculate back/forward to the end of a path from a given point of time, this is OK. Once all dates are provided, a more accurate critical path can be calculated if needed.

The entire set of paths is returned so that some validation can be implemented in the javascript. The first path will be the critical 'one', and this path gets highlighted in the UI, with the total duration of the critical path shown as well: