Two floors on the finish
Two numbers tell you how early a plan could finish. The first is the work: add every task’s duration and halve it, rounding up, because two workers share it. The second is the longest chain: follow the “after” links and add the durations along the longest path. No plan finishes before either.
Give the longest chain to one worker from time 0, with no gaps, since any wait on it delays the finish. Then fit the other tasks into the other worker’s time, starting each only after everything it waits for has finished.
If the plan finishes at the larger floor, it is a shortest plan. If not, find the chain task that had to wait and move whatever was in its way.
1Work floor: total time halved, rounded up.
2Chain floor: the longest run of “after” links.
3Start that chain at 0 and fill the other worker around it.
Both floors at 5
The work is 3 + 2 + 2 + 3 = 10, so two workers need at least 5. The chains are A then C, 3 + 2 = 5, and B then D, 2 + 3 = 5. Both floors are 5.
Worker 1 does A from 0 to 3, then C from 3 to 5. Worker 2 does B from 0 to 2, then D from 2 to 5. It finishes at 5, the floor, so no plan can do better.
Which tasks start at 0?
Find both floors first. Then decide which two tasks the workers should start at time 0.
Try it
Which two tasks should start at time 0?
- A and D
- B and D
Show the answer
B and D
Right. The work floor is 8 halved, 4, and the chain floor is B then C, 3 + 2 = 5. Start B at 0 and C follows from 3 to 5. D runs from 0 to 2 on the other worker and A from 2 to 3.
Enable JavaScript to answer interactively and save your place.
Practice Plan for two workers