What do planning the construction of a building, industrial production, managing orders while limiting delays, a hiker packing her backpack, and even children sharing a few coins fairly have in common? Each involves solving a scheduling problem: deciding when each task should be performed so that everything goes as smoothly as possible.
Building construction: what needs to be done, and when? ------------------------------------------
Consider the construction of a building. The site manager must arrange for each trade to come in as the work progresses. She knows which tasks must be completed, how long each will take, and their precedence relationships—that is, which tasks must be finished before another can begin (see the table). For example, the masonry must be completed before the plumbing can begin.
This can be represented by a precedence graph, as shown below, where the numbers on the arcs indicate the durations.