Automated Exam Timetabling for a Multi-Programme College: Graph Colouring versus Simulated Annealing (Python)

Every end-semester examination, the exam section of a multi-programme college must place 40–50 courses into about 10 working days of morning and afternoon sessions so that no student faces two exams in one session, every hall fits its enrolment, and students are not ground down by back-to-back papers. Under Calcutta University's CCF, a B.Sc (Hons) student reads Major, Minor, MDC and SEC courses drawn from different departments, so the enrolment graph is dense and the schedule built by hand in a spreadsheet almost always hides clashes that surface on exam day.

This research project builds ExamTT, a Python tool that models the problem as graph colouring — courses are nodes, two courses share an edge when at least one student takes both, and sessions are colours — and measures four solution strategies on realistic instances: a random greedy baseline, Welsh–Powell, DSATUR, and simulated annealing that repairs and refines any initial schedule against a weighted cost of hard clashes and soft penalties (same-day repeats, consecutive-session clashes, rooms opened).

The contribution is an empirical comparison, not just a tool. Ten generated instances calibrated to the college's enrolment profile (3,200 enrolments, 12 halls, 2 sessions a day) are solved five times each with fixed random seeds; the study reports hard-conflict counts, soft-cost breakdowns, convergence curves and runtimes, and tests whether differences are significant. The dissertation is a defensible piece of undergraduate research: a clear problem, formal constraints, standard algorithms, honest measurement — and a tool the exam section can use.

The exam section of a multi-programme college builds the end-semester examination timetable by hand in a spreadsheet. Under CCF, each honours student combines a Major with Minor, MDC and SEC courses from other departments, so the pattern of shared students across 40+ courses is far too dense to track mentally. The consequence repeats every semester: two exams land in the same session for some students and are discovered only when admit cards are printed; large courses are given halls that cannot seat them; some students get three exams in one day while others get a week free. Fixes are ad-hoc room changes that create new clashes elsewhere.

The problem is not carelessness but complexity — the task is equivalent to graph colouring, which is NP-hard, so a human cannot verify clash-freeness for thousands of enrolments. There is a need for a measured, automated approach: a formal constraint model, algorithms with guarantees about what they optimise, and an independent validator that proves the published schedule is clash-free before it reaches students.

Abstract

Examination timetabling is a classic NP-hard scheduling problem, still solved manually in Indian multi-programme colleges. This project formalises the exam-timetabling problem for a college running Calcutta University's CCF curriculum, implements a graph-colouring-based solver in Python with three constructive heuristics (random greedy, Welsh–Powell, DSATUR) and one metaheuristic refinement (simulated annealing), and measures quality and runtime on ten realistic instances. The central research question is: does annealing a DSATUR seed produce significantly better schedules than constructive heuristics alone, and at what runtime cost?

Introduction

A typical CCF college examines several honours programmes at once. Every student mixes a Major with Minor, MDC and SEC courses, so the courses any two programmes share are many; a clash is easy to create and hard to spot by eye.

Existing System and Literature

• Schedules are assembled in a spreadsheet by trial and error; clashes are found when a student's admit cards collide; the fix is an ad-hoc room change.
• The literature treats timetabling as graph colouring since Welsh and Powell (1967); Carter and Laporte (1996) survey the field; Kirkpatrick et al. (1983) introduced simulated annealing, now a standard refinement method.
• Published work benchmarks mostly on international datasets (Toronto, ITC). This project generates instances calibrated to an Indian multi-programme college under CCF, where cross-programme enrolments dominate — a stated gap.

Problem Formalisation

• Hard constraints: (H1) no student has two exams in one session; (H2) every course is scheduled exactly once; (H3) per-session seating demand never exceeds hall capacity; violating any makes a schedule infeasible.
• Soft constraints (penalised): (S1) a student with two exams on one day; (S2) exams in consecutive sessions; (S3) each hall opened beyond the minimum.
• Decision variables: each course is assigned one of 20 sessions (10 days × 2) plus a seat allocation across 12 halls.

Proposed System

1. An instance builder: course, student and enrolment tables in SQLite, importable from the spreadsheets the office already keeps, plus a generator producing ten instances with realistic density.
2. A conflict-graph builder in NetworkX over enrolments.
3. Four solvers: random first-fit; Welsh–Powell (descending degree); DSATUR (saturation-largest-first); and simulated annealing with relocate/swap moves and geometric cooling, seeded from the best constructive solution.
4. An independent validator that re-checks H1–H3 for every output, a metrics module that decomposes cost into hard and soft parts, and matplotlib convergence curves.
5. An experiment runner: 10 instances × 5 seeds per algorithm, analysed in pandas with mean ± standard deviation and a Wilcoxon test.

Feasibility Study

• Technical: the pipeline runs on a standard i5 laptop; the largest instance (45 courses, 3,200 enrolments) solves in minutes. NetworkX, pandas and matplotlib are stable, documented libraries.
• Economic: zero licence cost; no special hardware.
• Operational: the office's existing spreadsheets are the only input format required.
• Research feasibility: the algorithms are standard; the novelty — the CCF-specific instance model and the measured comparison — is achievable by one student in two semesters.

In scope

• End-semester examination timetabling only (not class timetables or invigilation duty rosters).
• Instances of 30–50 courses, up to ~3,200 enrolments, 10 days × 2 sessions, up to 12 halls; one exam per course.
• Four named algorithms; costs and cooling parameters fixed by a documented tuning pass.
• Deterministic, seeded experiments with reported distributions; results analysed in pandas and reported as tables and convergence plots.

Out of scope

• Room-by-person invigilation allocation, hall split of a single course across buildings (demand is summed per session), and mid-term/continuous-assessment scheduling.
• Exact methods (integer programming, CP-SAT) as full solvers — mentioned in the dissertation as the natural next step.
• A web or GUI interface; the tool is a documented command-line pipeline.
• Real personal data: the college dataset is anonymised to enrolment counts per course pair; no student names or roll numbers are stored.

Research design: a computational-experiment (algorithmic empirical) study. The independent variable is the algorithm (4 levels); dependent variables are hard-conflict count, soft cost, runtime and iterations to convergence; controlled variables are the instance set and random seeds. Every number in the dissertation is reproducible from a single run_experiments.sh invocation with fixed seeds.

Validity controls: the validator is independent of the solvers; the test suite pins known-small instances with hand-computed optima; every run logs its seed, version hash and machine time, so the comparison survives the viva question "how do you know this is not luck?"

ExamTT is a batch pipeline of seven stages. Nothing is interactive: each stage reads files and writes files, which keeps the experiment reproducible.

1. Instance layer — SQLite database with course, student, enrolment, hall and session tables; the generator writes instances, the importer reads the office's spreadsheets.
2. Model layer — the conflict graph is built in NetworkX (nodes = courses, edge weight = number of shared students); sessions and hall capacities stay in plain dictionaries.
3. Solver layer — four solvers with one common interface (solve(instance) -> Schedule); simulated annealing accepts any constructive schedule as its seed.
4. Assurance layer — a validator that re-derives H1–H3 from the instance (never from solver state) and a metrics module that decomposes the cost into hard and soft parts.
5. Analysis layer — pandas frames over per-run CSV logs; matplotlib convergence curves; the Wilcoxon comparison.

flowchart TD
  A["Spreadsheet import / generator"] --> B[("SQLite instance store")]
  B --> C["Conflict graph (NetworkX)"]
  C --> D1["Random greedy"]
  C --> D2["Welsh-Powell"]
  C --> D3["DSATUR"]
  D1 --> E["Simulated annealing (relocate / swap)"]
  D2 --> E
  D3 --> E
  D1 --> F["Validator + metrics"]
  D2 --> F
  D3 --> F
  E --> F
  F --> G[("Results CSV + convergence plots")]
  G --> H["pandas analysis + Wilcoxon test"]

Instance schema

erDiagram
  COURSE ||--o{ ENROLMENT : "has"
  STUDENT ||--o{ ENROLMENT : "holds"
  SESSION ||--o{ ASSIGNMENT : "receives"
  COURSE ||--o{ ASSIGNMENT : "is placed in"
  HALL ||--o{ SEAT_ALLOC : "seats"
  ASSIGNMENT ||--o{ SEAT_ALLOC : "is seated by"

  COURSE {
    string code PK
    string title
    int strength
    string programme
  }
  STUDENT {
    string anon_id PK
    string programme
  }
  ENROLMENT {
    string anon_id FK
    string code FK
  }
  SESSION {
    int id PK
    int day
    string slot
  }
  HALL {
    string name PK
    int capacity
  }

Algorithm cost function

flowchart LR
  S["Candidate schedule"] --> V{"Hard check H1-H3"}
  V -->|"violation"| P["cost = hard_penalty x violations"]
  V -->|"feasible"| Q["cost = w1 x S1 + w2 x S2 + w3 x S3"]
  P --> N["SA accepts / rejects by cost"]
  Q --> N

• Tabu search and a CP-SAT (OR-Tools) exact model as a fourth and fifth solver to measure how far metaheuristics are from optimal on these instance sizes.
• Invigilation duty allocation as a second assignment problem over the published schedule, sharing the same instance store.
• Room-split handling for oversized courses and preferential morning slots for large-enrolment papers.
• A small web front end for the exam section with conflict highlighting and what-if session dragging backed by the same solver.
• Multi-objective formulation (Pareto front over S1–S3) instead of fixed weights, with an interactive weight explorer for the controller of examinations.