Start the longest chain first

Find the two floors on the finish time, give the longest chain a worker at 0, and fill around it

Two floors on the finish

A: 3 units, can start at 0B: 2 units, can start at 0C: 2 units, after AD: 3 units, after B
Four tasks. C waits for A; D waits for B.

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.

More

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.

Lesson help

Start the longest chain at time 0 and fit the other tasks around it.

About this lesson

Try the method in a practice when you are ready.

Report

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.

A: 3 units, can start at 0B: 2 units, can start at 0C: 2 units, after AD: 3 units, after B
Four tasks. C waits for A; D waits for B.

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.

A: 3 units, can start at 0B: 2 units, can start at 0C: 2 units, after AD: 3 units, after BWorker 1ACWorker 2BD0123456
Each chain gets a worker from time 0. Finish: 5.

Which tasks start at 0?

Find both floors first. Then decide which two tasks the workers should start at time 0.

A: 1 unit, can start at 0B: 3 units, can start at 0C: 2 units, after BD: 2 units, can start at 0
Four tasks. C waits for B.

Try it

Which two tasks should start at time 0?

  1. A and D
  2. 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

Sign in free

Practice without limits and keep your progress.