Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 36 ยท Projects and Practice

Project: Campus Timetable Scheduler

Build a complete exam timetable scheduler in Python: conflict graph, DSATUR, iterated greedy improvement, clique lower bound, room capacities and a validator, step by step.

In this project you will combine several ideas from the course into one working tool: a scheduler that takes student enrollments and produces a clash-free exam timetable with as few slots as it can find, together with a certificate of how close to optimal it is. You will use conflict graphs, DSATUR and greedy coloring, cliques as lower bounds, and a fast improvement method called iterated greedy.

What you will build

flowchart TD
    A["Enrollments: student -> exams"] --> B["Build conflict graph"]
    B --> C["DSATUR: first timetable"]
    C --> D["Iterated greedy: improve"]
    B --> E["Clique heuristic: lower bound"]
    D --> F["Validate against raw enrollments"]
    E --> G["Report: slots used vs lower bound"]
    F --> G

Four components: model, solver, bound and validator.

The design rule for the whole project: never trust the solver; always validate its answer against the original data with a separate, simple function. A bug in the graph construction would otherwise produce a timetable that is perfectly colored but wrong.

Step 1: generate data and build the conflict graph

We create a seeded random university: 60 exams and 300 students who each sit between 3 and 5 exams. The conflict graph joins two exams when some student takes both.

Python Step 1: random enrollments and the conflict graph

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.

Step 2: the solver, DSATUR followed by iterated greedy

DSATUR gives a good first solution. Iterated greedy (Culberson) then improves it with a clever property: if you recolor greedily in an order where all vertices of each color class are consecutive, the new coloring never uses more colors than the old one. By reordering the classes (largest first, reversed, random) and repeating, the number of colors often drops, most visibly when the starting point is weak. Because it can never get worse, it is safe to run for as long as you have time.

Python Step 2: DSATUR plus iterated greedy

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.

Step 3: a lower bound from cliques

How good is the answer? Any clique forces that many slots. Finding the maximum clique is NP-hard, but a greedy heuristic finds a decent clique quickly: grow a set by repeatedly adding the vertex adjacent to everything chosen so far (choosing the one with the most remaining candidates), starting from many different seeds. The best clique size is a valid lower bound, and if the solver matches it, you have proved optimality.

Python Step 3: a clique lower bound and the full report

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.

If the gap is zero the timetable is optimal; otherwise the true optimum lies between the bound and the slots used. For a real university this information is valuable: it tells the registrar whether running a slower exact solver (for instance a SAT or integer-programming model) could possibly help.

Step 4: room capacity and the exam-per-slot limit

The last practical constraint (note that the plain degree-ordered greedy used here is weaker than DSATUR, so its slot counts are a little higher): at most R exams per slot because only R rooms exist. Extend the greedy rule so a color is available only if it is not used by a neighbor and its class has fewer than R exams. The number of slots can then never drop below ceil(60 / R). This is a combined lower bound: max(clique, ceil(n/R)).

Python Step 4: limit exams per slot

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.

Extensions to try

  • Add precoloring: some exams are pinned to fixed slots (the order of vertices then starts with them).
  • Penalize back-to-back exams for a student with a soft cost, and minimize it over slot orderings (a small assignment problem).
  • Replace the greedy clique with an exact search (branch and bound) on this 60-vertex graph.
  • Compare with an exact solver using the backtracking from coloring basics on a smaller instance.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why validate the timetable against the raw enrollments instead of the conflict graph?

    A bug in the graph construction would produce a "proper" coloring that still clashes for real students. Checking the raw data is an independent test.
  2. 2. Why can iterated greedy never produce a worse coloring?

    Vertices of one old class are never adjacent, so when processed consecutively they can reuse the same new color; the number of colors cannot increase.
  3. 3. What does a clique of size 14 in the conflict graph tell you?

    Pairwise conflicting exams must be in different slots, so the chromatic number is at least the clique size.
  4. 4. With R rooms and n exams, what is a capacity-based lower bound on the number of slots?

    Each slot holds at most R exams, so at least ceil(n / R) slots are required regardless of conflicts.

Summary

  • Model the data as a conflict graph, solve by coloring, and validate against the raw input.
  • DSATUR plus iterated greedy gives strong timetables with a never-worse improvement loop.
  • Clique heuristics give lower bounds that measure how far a solution can be from optimal.
  • Capacity limits are handled by restricting available colors, and add their own lower bound.

Next: Project: Volunteer Shift Planner with Max Flow