Critical Paths - The problem and translating it
(Page 2 of 4 )
Assume that we have a construction company. Constructing a building, for instance, is a job composed of multiple sub-jobs. Therefore, when the company gets an assignment to create a building, the head of the company will first break down the main job into multiple sub-jobs in order to simplify the process, and to better monitor the building's progress.
Considering his experience, he will probably make an estimate of how long each of the sub-jobs should take and sign the contract accordingly. The question is that, given the time requirement for each individual sub-job, what is the shortest time within which the building can be completed?
We need to consider that some of the jobs should only be done after we complete a set of previous jobs. For example, we cannot start painting the wall until we put the walls up in the first place. Additionally, what are the sub-assignments that cannot be delayed and need to be completed in time so we do not face penalties for delay of the main project?
Some sub-jobs can be completed within a given time interval, while a few must be completed exactly one after the other, otherwise the whole project would be delayed. These are the critical jobs for which the construction company will have to take extra care.
Now we will translate all this into a graph problem. Let the edges represent the jobs, and the weight of the edges will be the time required to complete the task. These will build a graph having a single source vertex (edges only going out from it) representing the start point of the work, and a single drain (terminal) vertex representing the end point of the work.
We will arrange the other edges that the graph will represent as the connections between the jobs. If a job can only be done after another is completed, then that task will follow from the vertex where the previously-required job ended. Thus, a job can only be done if all of its incoming edge representing jobs are complete.
The solution of the whole is the longest road from the source vertex and the drain (terminal) vertex. Following this way of thinking, we will also find the road through which the longest road goes. The edges that build this will be those that are the critical ones. Increasing the length of any of these edges (i.e. increasing the sub-job time required to complete it) will also increase the overall time needed to complete the building.
As for the other jobs, these will all have an earliest time to start when their critical edges related to the starting vertex are complete, and a final time when they must be started in order to finish them by the time that the end node of the edge “enters” a critical node. For the critical jobs, the earliest time to start the job and the latest time to do this are the same of course. As for the others, we can start them any time between these intervals.
Next: The solution >>
More Code Examples Articles
More By Gabor Bernat
