EXAMPLE 1 Home Construction

Let’s see how these assumptions might work for an example involving a home construction project. In this case, the processors are human workers with identical skills. Assumption 1 means that once a worker begins a task, the work on this task is finished without interruption. Assumption 2 means that no worker stays idle if there is some task for which the predecessors are finished. Assumption 3 requires that the ordering of the tasks be summarized in an order-requirement digraph. This digraph would code facts such as that the site must be cleared before the task of laying the foundation is begun. Assumption 4 requires that the tasks be ranked in a list from some perspective, perhaps a subjective view.

The task with highest priority rank is listed first in the list, followed left to right by the other tasks in priority rank. The priority list might be based on the size of the payments made to the construction company when a task is completed, even though these payments have no relation to the way the tasks must be done, as indicated in the order-requirement digraph. Alternatively, the priority list might reflect an attempt to find an algorithm to schedule the tasks needed to complete the whole job more quickly.