Have you ever tried to assemble a model, piece of furniture, or garbage disposal and run into instructions like this?

“Clamp hose A onto connector B… [30 minutes of frustration later] … after removing connector cover C.”

The problem isn’t really in the instructions (although they may be badly worded, too) but in their ordering.

In any complex endeavor, some of the tasks must come before others but usually the exact order of some tasks doesn’t matter. For example, suppose you’re building a house. Obviously you need do the framing work before you can put wires and pipes in the frame, but you can probably to the plumbing first and or the wiring first without causing too many problems.

A list of tasks with some dependencies is called a partial ordering. It determines the ordering of some tasks (framing comes before plumbing) but not necessarily every task (plumbing and electrical work are independent).

A complete ordering is an ordering of the tasks that satisfies all of the requirements of the partial ordering. The process of finding a complete ordering for a partial ordering is called extending the ordering.

Note that the complete ordering is not guaranteed to be unique. In the house-building example, you could do the wiring or plumbing in either order.

Note also that a complete ordering isn’t always possible. If the plumbers insists that they must do their work first and the electricians also insist that their work come first, you’re stuck. (You may have to fire them all and find a new crew.)

The ExtendPartialOrdering program, which is shown in Figure 1 and available in C# and Visual Basic versions in the download area, extends a partial ordering to a full ordering. Enter relationships on the left using a < sign to indicate that one task must come before another. Use the Data menu's Extend Ordering item or press F5 to make the program build a complete ordering if one is possible.

Figure 1. Task Table: Program ExtendPartialOrdering extends a partial ordering to a full ordering.

The left side of the ExtendPartialOrdering program shows one way to represent a partial ordering. You can also represent a partial ordering as a network. Make a node for each task and add a directed link from each task to every task that must come after it. Figure 2 shows the house-building data from Figure 1 in a network format.

Figure 2. Network Necessities: in this task network, arrows show which tasks must come before others.

Now you can perform all sorts of interesting tricks on the network representation. For example:

* If the network contains a cycle (a series of links that lead in a circle), then there is no complete ordering. (The plumbers and electricians are claiming they must go first.)
* Any node with in-degree 0 (no links lead into it), can be started immediately.
* If the network contains more than one disconnected piece, then the pieces can be worked independently.
* The longest path through the network tells you how long it will take to perform all of the tasks.

Extending the partial ordering to a complete ordering is equivalent to moving the network’s nodes around so all of the nodes are in a line and all of the links point more or less in the same direction. The links can curve, intersect, and even pass under nodes as long as none points back to a node earlier in the list.

Figure 3 shows a complete ordering of the network shown in Figure 2. Here the downward direction indicates the passage of time so tasks higher up in the network must be performed before those lower down.

Figure 3. Ready to Run: All of these links point downward so this network shows a complete ordering.

So how do you arrange the network as shown in Figure 3 in code? You could probably bash your way through an algorithm that treats the network in a general fashion but there’s an easier way to approach the problem that relies on its special structure.

Build a class that records a task’s name, number of items that must be done before it, and list of items that it must be done before. The ExtendPartialOrdering program uses the following class.

// Represent a task.private class POItem{    public string Name { get; set; }    public int NumBeforeMe { get; set; }    public List ItemsAfterMe { get; set; }    public POItem(string name)    {        Name = name;        NumBeforeMe = 0;        ItemsAfterMe = new List();    }}

Here's the algorithm:

1. Build the POItem objects to represent the tasks.

2. Make a list called no_prerequisites containing the items that have NumBeforeMe = 0. Those tasks are ready to run.

3. While no_prerequisites is not empty, take the first item in the list (call it ready_item) and:

a. Remove ready_item from the list.

b. Add ready_item to the output. It is ready to go.

c. For each of the items in ready_item's ItemsAfterMe list (call one of those items after_item):

i. Decrement after_item.NumBeforeMe.

ii. If after_item.NumBeforeMe = 0, add after_item to no_prerequisites.

4. Continue until no_prerequisites is empty. At that point either:

a. If all of the items have been added to the output, then you're done.

b. If there are still items with NumBeforeMe > 0, then the partial ordering cannot be extended to a complete ordering.

The following code shows how the ExtendPartialOrdering program implements this algorithm. The download includes some additional debugging code that validates the results to be sure they satisfy the requirements of the partial ordering.

// 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);    // Process items with no prerequisites.    while (no_prerequisites.Count > 0)    {        // Process the first item in the list.        // Remove the item.        POItem ready_item = no_prerequisites[0];        no_prerequisites.RemoveAt(0);        // Add the item to the results.        results.Add(ready_item.Name);        // Remove this item from the other        // items' prerequisite counts.        foreach (POItem after_item in ready_item.ItemsAfterMe)        {            // Remove next_item from other_item's count            // and see if the count is 0.            if (--after_item.NumBeforeMe == 0)            {                // Add other_item to the list of                 // items without prerequisites.                no_prerequisites.Add(after_item);            }        }    }    // 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;}

When it scans the text on the left in Figure 1, the program builds its POItems. It adds all of them to the AllItems list so they're easy to find later.

The code shown here uses Language Integrated Query (LINQ) to select the objects with NumBeforeMe = 0 into a list named no_prerequisites.
Next the code enters a loop that runs while no_prerequisites is not empty. In that loop, it takes ready_item from the front of the no_prerequisites list and adds it to the output. It then loops through ready_item's ItemsAfterMe list, updating those items appropriately.
When no_prerequisites is empty. The program uses LINQ to see if any items still have NumBeforeMe > 0. If there are such items, the program throws an error.
The figures shown so far use a very simple example so you can easily verify that the ordering makes sense but real-world projects are often much bigger. You can see a sample construction schedule for a 6,000 square foot custom home at b4ubuild.com that includes almost 200 tasks. Bigger projects such as movie production or skyscraper building might include thousands of tasks.
To let you test some bigger problems, the ExtendPartialOrdering program's Data menu includes two addition commands: Random Ordering and Complete Ordering.
When you invoke the Random Ordering command, a dialog lets you enter a number of tasks and a number of conditions. The program then creates some random partial ordering requirements. For item names it uses numbers and, to guarantee that a solution is possible, it creates the relationships so smaller numbers come before larger ones. Note that this does not mean the number must be in numerical order in the final ordering. The program only satisfies the random requirements not all of the requirements needed to ensure a perfect numerical ordering. Figure 4 shows the program after solving a random network with 1,000 tasks and 10,000 relationships. You can see that the results aren't in completely numeric order but, trust me, the solution satisfies the requirements.

Figure 4. Random Relationships: The Data > Random Ordering command makes the program build random items and relationships.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.            no_prerequisites.Remove(item);            // 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 +                        after_me.Duration;                    // Add this task to the no_prerequisites list.                    no_prerequisites.Add(after_me);                    // 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.
See also  AI's Impact on Banking: Customer Experience and Efficiency