7 Annie (A), Brigid (B), Carla (C) and Diane ( \(D\) ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( \(M\) ), pasting the paper ( \(P\) ), hanging and then trimming the top end of the paper ( \(H\) ) and smoothing out the air bubbles and then trimming the lower end of the paper ( \(S\) ). They will each do one of these tasks.
- Annie does not like climbing ladders but she is prepared to do tasks \(M , P\) or \(S\)
- Brigid gets into a mess with paste so she is only able to do tasks \(M\) or \(S\)
- Carla enjoys hanging the paper so she wants to do task \(H\) or task \(S\)
- Diane wants to do task \(H\)
Initially Annie chooses task \(M\), Brigid task \(S\) and Carla task \(H\).
- Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path.
Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
- Maximin value \(=\)
Route \(=\)