Scheduling a procedure for parallel distributed processing

First, list all individual tasks (or steps) to be done as part of the overall task. Label each task with a name or other unique identifier.

Tag each task with the amount of time needed to accomplish the task.

Make a table that lists all of the tasks. Next to each task, list the labels of all the tasks that must be done before this task can be started.

The following chart was created by using this technique to analyze the process of making espresso.

If that’s too hard to read, you can get a full-sized GIF version .

Begin the CPM chart by placing a ‘start’ node at the left side of the work area, like this:

Then add a node for one of the tasks that does not depend on any other task. Connect the start node to the task node with an arrow, labeled with the amount of time the task will take, like this:

To add the next task, choose another task that is dependent only on nodes already in the chart NOTE: If a task does not depend on any other task, consider it to be dependent on the start node. Add it to the chart by creating a node for it with labeled arrows coming from any nodes upon which it is dependent. Here’s the chart after adding nodes for tasks H and I.

Repeat this process until all tasks have been added to the chart. Rearrange the nodes as needed to keep lines from crossing more than necessary. Chart-drawing software (like Microsoft’s Viso, for example) is great for this.

Here’s a complete example to this point.

This chart has a flaw in it. Remember that the numbers on the arrows are supposed to tell you how long it will take to accomplish the task in the next node. Some of the nodes have more than one arrow pointing to them, and each of the arrows has a number on it. If we leave the chart like this, it seems to say that step M, for example, will need to be done twice at a cost of 45 seconds each time, for a total of 90 seconds. That’s not true, step M only has to be done once. We need to get rid of one of the time marks. But which one?

If you think about it, you will realize that the sum of the time marks between the start and any node tells how long it will take to get from the start to the end of the task identified by that node. So, for example, it would take 15 seconds to get from the start of the process to the end of step B, 5 seconds to do step C (which must come before B) and 10 seconds to do step B.

What about a node like J, which has two paths from the start to it? One path (S-A-I-J) totals 45 seconds and the other (S-H-J) totals 20 seconds. If we had two processors, one of them could start carrying out the tasks on the first path and one could carry out the tasks on the other path. The first processor would carry out tasks A and I and be ready to start J after 30 seconds. Meanwhile, the second processor would have carried out task H in only 5 seconds and be ready to do J, but J can’t be done until both I and H have been done. It will have to just sit and wait (or go on to another task) until the first processor finishes task I. So, in fact, path S-H-J takes just as long as path S-A-I-J. At least it’s not really occupying a processor during the waiting time.

We can’t just delete the line from H to J, since that would lose the information about the dependency of J on H. Instead, we’ll show that the S-H-J path is waiting for the S-A-I-J path by changing the numbered arrow from H to J into an unlabeled dashed arrow, like this:

Let’s do the same thing to all the places where two paths lead to the same node. In each case, we’ll make the last edge an unnumbered dashed line indicating that the system will have to wait for a longer path to finish before it can continue.

There is only one remaining path (S-A-I-J-K-L-M-O-P) from the start to the last node, and that’s called the critical path. It’s the longest sequence of events that has to happen sequentially, and we can’t use parallel processing to shorten it. In this case, it’s 285 seconds long.

We can get more useful information from this chart. For example, we can look at all the paths and determine how many processor we can use. Right at the start, we can see that five paths could be followed at the same time, so we could keep five processors busy then. We can also see that they will all be in use for only five seconds, until path S-H encounters a wait. Five seconds later, the processor running path S-N will become idle.

Since both of those paths are so short, we can let one processor do both of them, one after another. That will only take 15 seconds total, but for those 15 seconds 4 processors will be gainfully employed. For that matter, we can see that the critical path is so long and the rest of the paths so short (in this example) that one processor could do all of the non-critical paths while another did the critical path, so we only need two processors to get all the speed that is possible in this set of tasks.

Another kind of chart (a Gantt chart) is often used to show which resources are allocated to which tasks. We won’t do that now, but you will see Gantt charts in project management classes both in computer and business classes.