4. ("A Gentle Introduction to Optimization", by B. Guenin, J. K¨onemann and L. Tun¸cel, CambridgeUniversity Press, 2014) You wish to build a house and you have divided the processinto 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 startafter 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 completedas soon as possible. As an example, here is a feasible schedule with a completion time of tenweeks.
Tasks B F E P D L
Starting time 0 3 6 5 9 6
End time 3 5 9 9 10 8
Formulate this problem as an LP. Explain your formulation. Note that there is no limit onthe number of tasks that can be done in parallel. (Hint: Introduce variables to indicate thetimes that the tasks start.)