RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Network Knowhow: Partial Orderings : Page 2

The dependencies among a project's tasks gives you a partial ordering of those tasks. In this article, learn how to extend that to a complete ordering so you can decide what to do first, what to do next, and how long the whole project will take.

When you select the Data menu's Complete Ordering command, the program lets you enter a number. It creates that number of items and adds a relationship between every pair of adjacent numbers (for example, 119 < 120) to force a unique solution. The program then randomizes the list of relationships so the deck doesn't look completely stacked. Figure 5 shows the program after finding the unique ordering for 10,000 tasks.

Figure 5. Single Solution: The Data > Complete Ordering command makes the program specify enough relationships to define a unique complete ordering.

Parallel Partial Orderings

Building a useful schedule often depends on the exact details of the particular situation. For example, in the house-building scenario you clearly can't add the roof until you've framed the walls but some other tasks might be able to proceed in parallel. For example, the window installers, electricians, and plumbers might all be able to work at once, possible in different parts of the house.

In fact, you might even be able to start parts of one task before all of an earlier task is finished. For example, you might split the framing task so you can start writing and plumbing the first floor before the second floor's framing is finished.

Figure 6 shows a rearranged network where the links still point downward but tasks that can be performed in parallel are drawn side-by-side.

Figure 6. Parallel Possibilities: This network places tasks that can proceed in parallel side-by-side.

In addition to allowing tasks to run in parallel, I decided to add durations to tasks. For example, in Figure 6 the Drywall task can start when the Roofing, Plumbing, and Wiring tasks are finished. If those tasks aren't finished until days 49, 46, and 57, then the Drywall task can't start until day 57.

Fortunately it's not too hard to modify the previous algorithm to handle these changes.

First, modify the POItem class to hold the task's Duration. To make recording each task's finish time easier, add a DoneAtTime property. You can also add a calculated StartAtTime property if you like.

The ParallelPartialOrdering example program uses the following version of the POItem class.

// Represent a single task.
private class POItem
    public string Name { get; set; }
    public int NumBeforeMe { get; set; }
    public List ItemsAfterMe { get; set; }
    public int Duration { get; set; }
    public int DoneAtTime { get; set; }
    public int StartAtTime { get { return DoneAtTime - Duration; } }
    public POItem(string name)
        Name = name;
        NumBeforeMe = 0;
        ItemsAfterMe = new List();
        Duration = 1;
        DoneAtTime = 0;

The only change to the algorithm itself is to select the proper item from the no_prerequisites list. The previous algorithm simply removed the first item from the list. The new algorithm removes the item that has the soonest DoneAtTime value. Of the tasks that are currently being performed, that is the one that finishes first so the tasks that must be performed after it are the ones the program should consider next.

The following code shows how program ParallelPartialOrdering implements this algorithm. The key changes to the code are shown in red.

// Return an array giving the items in a complete ordering.
public List CompleteOrdering()
    List results = new List();

    // Find items that have no prerequisites.
    var no_prereqs_query =
        from POItem po_item in AllItems.Values
        where po_item.NumBeforeMe == 0
        select po_item;
    List no_prerequisites =
        new List(no_prereqs_query);

    // Start at elapsed time = 0.
    int elapsed_time = 0;

    // Output the no prerequisites items.
    foreach (POItem item in no_prerequisites)
        results.Add(item.Name + ": " + item.StartAtTime +
            " --> " + item.DoneAtTime);

    // Process items with no prerequisites.
    while (no_prerequisites.Count > 0)
        // See when the first items without
        // prerequisites will be done.
        int first_done_time =
            (from POItem item in no_prerequisites
             select item.DoneAtTime).Min();

        // Update the current time to this time.
        elapsed_time = first_done_time;

        // Perform tasks with this minimum done time.
        // Use ToArray to cache this so we don't get in trouble
        // for modifying the list while we are enumerating it.
        POItem[] ready_items =
            (from POItem item in no_prerequisites
            where item.DoneAtTime == first_done_time
            select item).ToArray();
        foreach (POItem item in ready_items)
            // Perform this task.
            // Remove it from the no_prerequisites list.

            // Update the items after this task. 
            foreach (POItem after_me in item.ItemsAfterMe)
                // Subtract 1 from this item's prerequisite count.
                if (--after_me.NumBeforeMe == 0)
                    // This one is ready to start.
                    // Calculate when this task will finish.
                    after_me.DoneAtTime = elapsed_time +

                    // Add this task to the no_prerequisites list.

                    // Output this task.
                    results.Add(after_me.Name + ": " +
                        after_me.StartAtTime +
                        " --> " + after_me.DoneAtTime);
            } // End updating items after the current one.
        } // End processing the ready items.
    } // End while (no_prerequisites.Count > 0)

    // See if any items are left with prerequisites.
    // If so, then there are circular dependencies.
    var check_query =
        from POItem po_item in AllItems.Values
        where po_item.NumBeforeMe != 0
        select po_item;
    if (check_query.FirstOrDefault() != null)
        // There are items remaining.
        throw new Exception("There is no complete ordering for " +
            "this partial ordering");

    return results;
The red code selects the next item to remove from the no_prerequisites list. It starts by using LINQ to get the smallest DoneAtTime value in the list. It updates the current time counter to hold the time when these soonest-done tasks finish. (I use an integer representing days but it could represent hours, weeks, or whatever unit is appropriate.) That time is also the time when the next set of tasks can begin.

Next the code uses LINQ to get a list of the items in the no_prerequisites list that have this minimum DoneAtTime value (there may only be one). The code converts this list into an array to make LINQ execute the query and to cache the results. (If you don't do this, LINQ defers executing the query until you try to loop through the results. While it loops through the results, the program modifies the underlying list and LINQ gets all confused trying to loop through a list that's being modified.)

Now the program loops through the minimum DoneAtTime items and processes them as before. For each of those items, the code loops through its ItemsAfterMe list, adding those items to no_prerequisites and adding them to the output.

Notice that the output includes each task's name and the times during which it is being performed.

Figure 7 shows the ParallelPartialOrdering program in action. The final task is Paint which starts in day 83 and finishes in day 111.

Figure 7. Satisfying Schedule: Program ParallelPartialOrdering displays the days during which each task is performed.

Extending a partial ordering like this won't solve all of your scheduling problems in the real world. Some tasks will take longer than expected, weather may delay some tasks, and new tasks that you didn't know about will appear. Even a task that takes less time than expected can mess up the schedule. For example, suppose the Drywall task finishes early on day 75 but you told the painters to show up on day 83. They may be unable to change their schedule to take advantage of the change to finish the project early.

Still, these kinds of schedules give you something to work with. As Dwight D. Eisenhower said, “No battle was ever won according to plan, but no battle was ever won without one.” These algorithms give you a plan that you can track, update, use to build Gantt charts, and otherwise struggle to keep things on track.

Rod Stephens is a consultant and author who has written more than a dozen books and two hundred magazine articles, mostly about Visual Basic. During his career he has worked on an eclectic assortment of applications for repair dispatch, fuel tax tracking, professional football training, wastewater treatment, geographic mapping, and ticket sales. His VB Helper web site receives more than 7 million hits per month and provides three newsletters and thousands of tips, tricks, and examples for Visual Basic programmers.
Email AuthorEmail Author
Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date