Advanced Project 3 — Task Scheduler¶

Difficulty: Advanced · Estimated effort: 2 weeks · Prerequisites: Module 12 — Templates, Module 14 — The STL with OOP, Module 15 — SOLID and Design Patterns · Demanded pattern decisions: strategy, template method

This is one of the designated integration projects, and one of the projects that requires a design-pattern decision: at least two patterns must be named and justified by a requirement, and one alternative must be considered and declined in writing.

No complete solution is provided. The scheduling policies are described as behaviour; the ordering machinery is yours to design.

1. Scenario¶

A build farm runs jobs that depend on each other. Some jobs need more than one worker, some cannot run until three others have finished, and some must run before a deadline. The farm wants to know: in what order should the jobs run, how long will the whole thing take, which jobs are currently runnable, and — when the dependency file is wrong — exactly which cycle is unresolvable.

The old script sorted by hand and occasionally deadlocked the farm for an hour.

2. Problem statement¶

Build a scheduler: tasks with durations, resource requirements and dependencies; a dependency graph that rejects cycles with the path; several scheduling policies producing an order; a simulation with an injected clock producing a timeline; and a report that says what ran when and why the order was chosen.

3. User requirements¶

[ ] Load a task set from a file and see the dependency graph as text.
[ ] Ask which tasks are runnable now, given what has completed.
[ ] Produce an execution order under a named policy.
[ ] Simulate the schedule and print a timeline with start and finish times.
[ ] Be told the exact cycle when dependencies are impossible.
[ ] Compare two policies on the same task set: makespan and average wait.

4. Functional requirements¶

[ ] Task with an identifier, duration, worker requirement and dependencies.
[ ] A dependency graph with topological ordering and cycle detection reporting the path.
[ ] A SchedulingPolicy interface with at least two implementations — for example shortest-duration-first, and critical-path (dependency depth) first.
[ ] A Scheduler running a policy over an injected clock, producing a Timeline.
[ ] A Timeline of assignments: task, start, finish, worker count.
[ ] Ordering must be deterministic: ties broken by a documented rule, never by container order.
[ ] A documented file format for tasks and dependencies, with line-numbered errors.

5. Non-functional requirements¶

[ ] No dependency is ever started before its prerequisites finish — checked in the simulation, not only in the policy.
[ ] Worker capacity is never exceeded at any instant.
[ ] A cycle is detected before any task runs, and the report names every task in the cycle.
[ ] Two runs of the same input produce an identical timeline.
[ ] Builds warning-free with g++ -std=c++17 -Wall -Wextra -Werror.

6. Suggested features¶

A ResourcePool abstraction, so workers are a resource rather than an integer.
Critical-path reporting: for each task, the longest path to a sink, and the slack.
Deadline tasks, with lateness reported per task.
A policy that learns nothing but is honest about it: random order with a seed, as a baseline.

7. OOP concepts involved¶

Concept	Required	Where it appears
Multiple classes	yes	`Task`, graph, policies, scheduler, timeline, resource pool, error types
Relationships	yes	Scheduler ◆ graph and policy; timeline ◆ assignments; task ──> its dependencies
Encapsulation	yes	Graph edges change only through validated operations; timeline is append-only
Inheritance or composition	yes	Policies behind an interface; the scheduler composed with, not derived from, the graph
Polymorphism	yes	Policy selection dispatches; the simulation loop contains no policy names
The STL	yes	`std::map` for tasks, `std::set` for ready sets, `std::priority_queue` or `std::sort` per policy
Exception handling	yes	Cycles, unknown dependencies, duplicate ids and bad lines each throw distinct types

8. Suggested design considerations¶

The pattern decision you must make and justify¶

Strategy, for the ordering. Ordering is the thing that varies, and the requirement that earns the strategy is compare two policies on one task set without editing the simulator. Name the alternative: an if on a policy name inside the simulation loop, or a policy passed as a comparator only. Both are defensible for small cases — argue your choice.

Template method, for the run loop. A simulation has fixed stages — find ready tasks, choose, assign, advance the clock, record — with exactly one that varies. A template method base class with a pure virtual choose() is the classic shape. The alternative is a strategy plus a free function. Pick one and say which requirement settled it. The one you decline is the declined-pattern item, and the reason must be specific.

Ideas worth weighing and recording: observer, so the timeline is built by notifications rather than by the loop pushing records (probably not earned — the loop owns the record); command, for undo of an assignment (not earned here, since nothing un-schedules).

Other design points¶

Ties must be broken deterministically. The whole point of a reproducible timeline is lost if two ready tasks with equal priority come out of a container in a different order each run.

Check the invariant in the simulation, not only in the policy. "No task started before its dependencies finished" and "workers never exceeded" are properties of the timeline; asserting them at each step is what turns a plausible schedule into a verified one.

Cycles are reported before the run. Discovering a cycle mid-simulation means your graph checks were in the wrong place.

9. Minimum viable version¶

Tasks with dependencies, a topological sort, one policy, and a timeline printed as a simple list. Cycle detection with the path. No worker limits.

10. Intermediate extension¶

Add worker capacity and the second policy, then verify with one task set that the two policies produce different orders but both respect dependencies and capacity. Report makespan and average wait for both.

11. Advanced extension¶

Add the critical-path report, deadlines with lateness, and the seeded random baseline. Then write the design note: the two patterns, the declined alternative, and the decision you would reverse — with its cost. Include the policy comparison table as evidence.

12. Testing checklist¶

[ ] A linear chain of three dependencies produces that exact order
[ ] A diamond dependency runs the two branches in either order and never the join early
[ ] A cycle is refused, naming every task in it, before anything runs
[ ] A dependency on a non-existent task is refused with both ids in the message
[ ] Duplicate task ids are refused
[ ] Worker capacity is never exceeded — checked at every step of the simulation
[ ] Every task starts at or after the finish of all its dependencies — checked every step
[ ] Two runs with the same input produce identical timelines (compared as text)
[ ] Two runs with different policies on the same input produce the documented difference
[ ] A single task with no dependencies schedules at time zero
[ ] An empty task set produces an empty timeline, not an error
[ ] The makespan equals the finish time of the last task in the timeline

13. Documentation checklist¶

[ ] The task file format, with a cycle example and its error output
[ ] The class diagram, showing the scheduler composed with the graph and policy
[ ] Each policy's rule, stated precisely enough to reproduce by hand
[ ] The tie-break rule
[ ] The policy comparison table, with the numbers you observed

14. Self-evaluation rubric¶

Criterion	Excellent looks like	Weight
Policy design	Policies independent, swappable, compared with evidence	25%
Scheduling correctness	Dependencies and capacity verified at every step	25%
Cycle handling	Detected pre-run, reported as a named path	15%
Pattern decisions	Two patterns justified; the declined alternative argued, not asserted	15%
Determinism	Identical timelines for identical inputs	10%
Documentation	Rules, format, comparison evidence and the reversed decision	10%