Every semester, someone gets three papers in one day. Exam scheduling is a classic NP-hard problem — which makes it perfect FYP material: no giant dataset needed, pure algorithm comparison, and results your own faculty can actually use.
A web tool: upload courses, student enrollments, and rooms as CSV → generate a clash-free exam timetable with room allocation → interactive calendar view with conflict highlighting and manual overrides.
Three fundamentally different optimization paradigms solve the same instances: evolutionary (GA), local search (SA), and exact constraint programming (CP-SAT) — who wins on quality, speed, and scale?
Pernyataan masalah: Faculty exam timetables are drafted manually or with rigid legacy tools; clashes, back-to-back papers, and room overflows are found late, and there is no measure of how "good" a released timetable actually is.
| Experiment | Setup | What it proves |
|---|---|---|
| Eksperimen 1 Real faculty instance |
All 3 solvers on one real (or realistic) faculty dataset: ~50 courses, ~1,500 students, ~15 rooms. | Head-to-head on the practical case — the result your faculty cares about. |
| Eksperimen 2 Scalability sweep |
Synthetic instances at 25 / 50 / 100 / 200 courses, fixed constraint density. | How each paradigm scales — where the exact solver stops being feasible and heuristics take over. |
| Eksperimen 3 Constraint-density stress |
Fixed size, increasing soft constraints (spacing preferences, room capacity tightness). | Solution-quality behavior under pressure; convergence curves per solver. |
One anonymized real enrollment dataset from your faculty (or reconstructed from public course lists) + a documented synthetic instance generator (parameters: courses, students, enrollment distribution, rooms). The generator itself is a methodology contribution and makes results reproducible.
| Metric | Why it matters here |
|---|---|
| Hard-constraint violations | Clashes and room overflows must be zero — feasibility rate per solver per instance. |
| Soft-constraint penalty score | The quality number: back-to-back exams, spread over the exam period, room utilization. |
| Runtime to best solution | Seconds vs minutes vs hours — plotted against instance size from Eksperimen 2. |
| Convergence curves | Quality-over-time plots showing how GA and SA improve vs CP-SAT's exact search. |
| Chapter | What goes in it (from this package) |
|---|---|
| Bab 1 — Pengenalan | Problem statement, objectives, scope (exam timetabling only, 3 solvers), constraints list, Gantt chart. |
| Bab 2 — Sorotan Kesusasteraan | Comparison tables: timetabling approaches across studies, metaheuristics vs exact methods, university timetabling benchmarks (e.g., Toronto/ITC datasets). |
| Bab 3 — Metodologi | Formal problem model (hard/soft constraints), solver configurations, synthetic instance generator design, tool architecture (CSV → solver → calendar UI). |
| Bab 4 — Pembangunan & Pengujian | The 3 experiments, feasibility/penalty/runtime tables, convergence plots, timetable UI screenshots. |
| Bab 5 — Dapatan Kajian | Per-size solver recommendation, limitations (single objective weighting, invigilator scheduling excluded), future work (multi-objective, lecture timetabling). |
PythonGoogle OR-ToolsDEAP (GA) Flask / FastAPIFullCalendar.jsPandas
← Back to all FYP ideas · Assignment Helper