Scheduling with precedence constraints
Task dependencies form a partial order: task a ⊑ b means a must finish before b starts. With unlimited parallel workers, the minimum completion time is the length of the longest chain — the critical path. With limited workers the problem becomes a chain-cover question, which is why Dilworth’s theorem shows up in scheduling theory.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Draw the dependency posetElements are tasks and edges are direct prerequisites. Cycles mean the specification is impossible.
- Compute earliest start timesProcess in topological order; a task starts as soon as all its prerequisites are done, so its earliest start is the maximum finish time of its predecessors.
- Find the critical pathThe longest weighted path determines the minimum makespan with unlimited resources. Tasks on it have zero slack.
- Bound the workers neededThe width of the poset bounds how much parallelism is usable; the number of chains in a minimum cover is a natural worker count.
Worked example
Tasks A(3), B(2), C(4), D(1) with C after A, D after B and after C. Find the minimum completion time with unlimited workers.
- A and B have no prerequisites: both start at time 0. A finishes at 3, B at 2.
- C waits for A, so it starts at 3 and finishes at 3 + 4 = 7.
- D waits for B (done at 2) and C (done at 7), so it starts at 7.
- D finishes at 7 + 1 = 8.
Answer. Minimum completion time is 8, along the critical path A → C → D. B has 5 units of slack.
Where marks get dropped
These are the specific errors that cost credit on scheduling with precedence constraints questions — QED's rubric penalises each of them separately.
- Starting a task when only some prerequisites are complete. The earliest start is the MAXIMUM over all predecessors, not the minimum or the average.
- Assuming more workers always help. Beyond the width of the poset, extra workers idle — the critical path is a hard lower bound.
- Ignoring cycles. A dependency cycle makes the schedule infeasible, which is exactly what a failed topological sort detects.
Practise this until it is automatic
Unlimited fresh questions
QED generates new scheduling with precedence constraints problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Orderings & Lattices mastery is tracked so you know when this is exam-ready.
Scheduling with precedence constraints — frequently asked questions
What is slack?
The amount a task can be delayed without pushing back the overall finish: latest start minus earliest start. Critical-path tasks have zero slack by definition.
Why is the critical path a lower bound?
Its tasks must run strictly in sequence, so their durations add regardless of how many workers are available.
Is scheduling with limited workers easy?
No — minimising makespan on a fixed number of machines with precedence constraints is NP-hard in general, though the unlimited-worker case is solved by one topological pass.
The rest of Orderings & Lattices
Partial orders, Hasse diagrams, bounds, lattices. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Partial vs total orders
- 2Hasse diagrams
- 3Minimal, maximal, least & greatest elements
- 4Upper & lower bounds, supremum & infimum
- 5Lattices: divisibility & subset orders
- 6Chains, antichains & comparability
- 7Topological sorting
- 8Well-orderings & the least-element principle
- 9Distributive & complemented lattices
- 10Product & lexicographic orders
- 11Dilworth’s theorem & chain covers
- 12Order isomorphism & comparing posets
- 13Scheduling with precedence constraints
Ready to make scheduling with precedence constraints exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →