Skip to content
Tutorials Center
My learning

Topics

Lesson 215 of 225 ยท Projects

Project: Task Scheduler

Build a task scheduler with dependencies in stages. Use topological sort to order tasks, a priority queue to pick the next one, and a simulation for many workers.

Build systems, CI pipelines, job queues, project plans and the operating system itself all face the same puzzle. There is a set of tasks. Some cannot start until others have finished. Some are more urgent than others. And there may be several workers available at once. Which task should run next, and when does everything finish?

In this project you will build a scheduler that answers those questions. It combines two ideas from earlier chapters: a topological sort to respect dependencies and detect impossible plans, and a priority queue to choose among the tasks that are ready. You will finish with a multi-worker simulation, a critical path calculation that tells you the best possible finishing time, and a randomized test that checks the scheduler against provable bounds.

The project

We will schedule the launch of a small app. Each task has a name, a duration (in hours), a priority (higher means more important) and a list of tasks that must finish first:

TEXT
spec(2) โ”€โ”€โ”ฌโ”€โ”€ design(3) โ”€โ”€โ”€โ”€ frontend(4) โ”€โ”€โ”
          โ”‚                                 โ”œโ”€โ”€ tests(3) โ”€โ”€ deploy(1)
          โ””โ”€โ”€ database(4) โ”€โ”€ backend(5) โ”€โ”€โ”€โ”ค                  โ”‚
                                  โ””โ”€โ”€โ”€โ”€โ”€โ”€โ”€ api-docs(2) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜

Reading the picture: backend needs database; tests need both backend and frontend; deploy needs tests and api-docs. This kind of graph, with directed edges and no cycles, is a DAG (directed acyclic graph).

Stage 1: is the plan even possible?

Before scheduling anything, check that the dependencies can be satisfied. If task A needs B, B needs C and C needs A, nothing can ever start. Kahn's algorithm finds a valid order and detects cycles in one pass: repeatedly take a task with no unfinished dependencies, "finish" it, and reduce the waiting count of the tasks that depend on it. If we run out of such tasks before finishing everything, a cycle remains.

Python Stage 1: dependency order and cycle detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The algorithm touches each task and each dependency once, so it takes O(V + E) time. The order it prints is a valid order, not the only one: design and database could swap places. Which valid order we actually want depends on priorities and available workers, which brings in the second ingredient.

Stage 2: pick by priority among the ready tasks

At any moment, the ready tasks are those whose dependencies are all finished. A scheduler with one worker must pick one of them. Picking the highest-priority ready task is the job of a priority queue: a binary heap gives us the best item in O(log n) and lets new ready tasks join in O(log n).

Python's heapq is a min-heap, so we push (-priority, name). Equal priorities then fall back to the name, which keeps the schedule deterministic.

Python Stage 2: one worker, highest priority first

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at hour 2: both design (priority 4) and database (priority 3) are ready, and the scheduler picks design. At hour 5, frontend (priority 4) beats database (priority 3) the same way, and backend (priority 5) runs as soon as database has finished. With one worker the total time is simply the sum of durations (24 hours), whatever the order. Priorities only decide which tasks finish earlier, which matters when the project might be cut short or when some tasks are urgent. The order matters far more when we have several workers.

Stage 3: simulating many workers

With several workers the problem becomes a simulation. Time jumps from one event to the next, and an event is "a task finishes". We need two heaps:

  • the ready heap, as before, ordered by priority;
  • the running heap, ordered by finish time, so we always know which task ends next.
TEXT
loop:
  while a worker is free and a task is ready:   start the best ready task on a free worker
  if nothing is running: stop (all done, or a cycle)
  jump the clock to the earliest finish time
  finish every task ending at that time; free their workers; unlock dependents
Python Stage 3: event simulation with two workers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Going from one worker to two cuts the finishing time from 24 hours to 15, but a third worker does not help at all (look at the output): some tasks simply have to wait for others no matter how many hands are available. That limit has a name.

Stage 4: the critical path

The chain of tasks that takes the longest, following dependencies, sets a floor on the project's duration. No number of workers can make deploy start before spec -> database -> backend -> tests -> deploy is done. This longest path is the critical path. We can compute it with a longest-path DP over the DAG: process tasks in topological order and let each task's earliest finish be its duration plus the latest earliest-finish among its dependencies.

Two simple lower bounds then bracket every possible schedule:

  1. Critical path: the finish time can never be less than the critical path length.
  2. Work bound: with m workers the finish time can never be less than total work / m (rounded up).
Python Stage 4: critical path and lower bounds

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare these bounds with the simulation from stage 3: with one worker the bound is 24 and the schedule finishes at 24; with two or more workers the bound is 15, and so is the finish time. When the simulated finish time equals the bound, the schedule is provably optimal. In general, finding the optimal schedule on several workers is NP-hard (see P, NP and hard problems), but this greedy "never leave a worker idle" strategy is guaranteed to be close. Graham's bound says that any such list schedule finishes within work/m + (1 - 1/m) * critical_path of the start. We will test that claim next.

Project managers call the tasks on the critical path "zero slack" tasks: delaying any of them delays the whole project, while tasks off the path (like api-docs here) have room to slip. Scheduling tools compute slack with a forward pass (earliest start) and a backward pass (latest start), the same DP run in both directions.

Stage 5: the finished scheduler and a randomized test

Now we pull it together into one Scheduler class and test it hard. A schedule is valid when (1) every task runs exactly once for exactly its duration, (2) every task starts after all its dependencies have ended, and (3) no worker runs two tasks at once. We write a separate validate function, check random schedules with it, and also verify the bounds above.

Python Stage 5: the Scheduler class with randomized tests

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every generated schedule passes the validator, and the finish times always fall between the two lower bounds and Graham's upper bound. A good share of them hit the lower bound exactly, which proves they are optimal. A single randomized test like this gives far more confidence than a few hand-picked examples.

Complexity

Let V be the number of tasks, E the number of dependencies and m the number of workers.

Step Time Why
Build graph and topological order O(V + E) each task and edge visited once
Each push/pop on the ready or running heap O(log V) binary heap
Full simulation O((V + E) + V log V) every task is pushed and popped once per heap
Critical path O(V + E) one pass in topological order
Space O(V + E) adjacency lists, heaps, schedule

The number of workers m only affects the free-worker heap, which costs O(log m) per operation.

Ideas to extend it

  • Deadlines. Order the ready heap by earliest deadline first, a classic real-time scheduling rule.
  • Shortest job first. Try ordering by duration instead of priority and compare the average completion time of tasks.
  • Resources. Give tasks resource needs (memory, a database lock) and start a task only when enough remain.
  • Recurring jobs. Re-add a task to the ready heap at fixed intervals, like cron.
  • Failures and retries. Return a failed task to the ready heap and delay its dependents.
  • Preemption. Let a higher-priority task interrupt a running one; an operating system CPU scheduler does this.

Common mistakes

  • Using heapq with the wrong sign. heapq pops the smallest item first, so push -priority to get the highest priority first.
  • Starting tasks when the heap is non-empty but all workers are busy. Always check for a free worker.
  • Finishing only one task per event. Several tasks can end at the same time; finish them all before starting new ones, or the schedule becomes order-dependent.
  • Forgetting cycle detection. A cycle makes both ready and running empty while tasks remain; compare the number of scheduled tasks with the total.
  • Treating priority as a guarantee of order. A low-priority task still runs first if it is the only one ready.
  • Comparing non-comparable heap items. If two heap entries tie on every earlier field, Python compares the next one. Putting the task name in the tuple keeps comparisons well defined.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does Kahn's algorithm report when the dependencies contain a cycle?

    Tasks in a cycle always have at least one unfinished dependency, so their waiting count never reaches zero. Counting the tasks that were ordered reveals the cycle.
  2. 2. Which structure picks the next task to run among those whose dependencies are done?

    A heap returns the best ready task in O(log n). Negating the priority makes Python's min-heap pop the highest priority first.
  3. 3. Why do we need a second heap ordered by finish time in the multi-worker simulation?

    The simulation advances from event to event. The running heap always has the earliest finishing task on top.
  4. 4. What is the critical path?

    Tasks on the longest dependency chain must run one after another, so no number of workers can finish the project sooner than that chain's total duration.
  5. 5. With 4 workers, a project of 40 hours of total work whose critical path is 18 hours. What is the lower bound on the finishing time?

    The work bound is 40 / 4 = 10 hours, and the critical path is 18 hours. The finish time can never be less than the larger of the two, which is 18.

Summary

  • A schedule with dependencies is a DAG; Kahn's algorithm gives a valid order in O(V + E) and detects cycles.
  • A priority queue (heap) selects the best ready task; push -priority with heapq.
  • A multi-worker simulation is event-driven: a ready heap, a running heap ordered by finish time, and a heap of free workers.
  • The critical path (longest dependency chain) and work / m give lower bounds; greedy list scheduling stays within Graham's bound work/m + (1 - 1/m) * critical path.
  • Validate schedules with an independent checker and randomized tests; always report cycles instead of looping.

Next: Project: Spell Checker