Question

You wish to build a house and you have divided the process into a number of tasks, namely:

B. excavation and building the foundation,
F. raising the wooden frame,
E. electrical wiring,
P. indoor plumbing,
D. dry walls and flooring,
L. landscaping.

You estimate the following duration for each of the tasks (in weeks):

Tasks B F E P D L
Duration 3 2 3 4 1 2

Some of the tasks can only be started when some other tasks are completed. For instance, you can only build the frame once the foundation has been completed, i.e. F can only start after B is completed. All the precedence constraints are summarized as follows:

• F can start only after B is completed,
• L can start only after B is completed,
• E can start only after F is completed,
• P can start only after F is completed,
• D can start only after E is completed
• D can start only after P is completed.

The goal is to schedule the starting time of each task such that the entire project is completed as soon as possible. As an example, here is a feasible schedule with a completion time of ten weeks.

Tasks B F E P D L
Starting Time 0 3 6 5 9 6
End Time 3 5 9 9 10 8

Required:
Formulate this problem as an LP. Explain your formulation. Note that there is no limit on the number of tasks that can be done in parallel. (Hint: Introduce variables to indicate the times that the tasks start.)

Answer 1

x1 + x2 + x3 + x4 + x5 + x6 + x7

Step-by-step explanation:

Formulating the problem as an LP

Attached below is an AOA diagram and the completion time of each task is indicated in the diagram, The diagram was based on the conditions given for the completion of each task accordingly.

To complete the project as early as possible we will have assume

x1, x2, x3, x4, x5, x6, and x7 to be the times taken to complete each node

hence the earliest time taken to complete the project

= x1 + x2 + x3 + x4 + x5 + x6 + x7

when : x2 - x1 ≥ 3

x3 - x2 ≥ 2

x4 - x2 ≥ 2

x5 - x3 ≥ 3

x6 - x3 ≥ 3

x7 - x5 ≥ 1

x7 - x6 ≥ 1

also : x1, ............ , x7 ≥ 0