Metaheuristic Approaches for the University Course Timetabling Problem

A C++ implementation of four metaheuristic approaches for solving the University Course Timetabling Problem (UCTP): Hill Climbing, Iterated Local Search (ILS), a Memetic Algorithm, and a convergence analysis mode.

Problem Description

Given a set of courses, classrooms, instructors, and time slots, the objective is to assign each lecture to a room and a schedule while minimizing both hard and soft constraint violations.

Hard Constraints

• Room conflicts
• Instructor conflicts
• Curriculum conflicts
• Unavailable periods

Soft Constraints

• Minimum working days per curriculum
• Curriculum compactness
• Room stability

The overall goal is to produce feasible timetables with the lowest possible penalty cost.

---

Implemented Metaheuristics

Mode	Algorithm	Description
hc	Hill Climbing	Local search starting from a greedy initial solution
ils	Iterated Local Search	Repeated Hill Climbing with random perturbations
ga	Memetic Algorithm	Population-based search with crossover and ILS-based local improvement
conv	ILS + Convergence Analysis	ILS with historical tracking of the best solution cost

---

Compilation

g++ -O2 -o timetabling main.cpp timetabling.h

---

Usage

./timetabling instance.json <mode> <time_limit_sec> <seed> [options]

# Examples:
./timetabling instance.json ils 60 42
./timetabling instance.json ga 120 42 --pop_size 10 --p_mut 0.3
./timetabling instance.json conv 60 42 --out convergence.csv

---

Available Options

Option	Description	Default
--k_perturb N	Perturbation strength (ILS)	4
--pop_size N	Population size (GA)	8
--p_mut F	Mutation probability (GA)	0.3
--out file.csv	Save results to CSV	—
--quiet	Suppress detailed console output	—

---

CSV Output Format

instance, config, seed, hard_total, soft_total, total_cost, runtime,
hard_room, hard_professor, hard_curriculum, hard_unavailability,
soft_mindays, soft_compactness, soft_room_stability

The generated CSV file provides a detailed breakdown of hard and soft constraint violations, total solution cost, and execution time for subsequent statistical analysis.

---

Technologies

• C++17

• Standard Template Library (STL)

  • chrono
  • fstream
  • sstream

• JSON-based instance format

---

Research Context

This project explores the effectiveness of local search and population-based metaheuristics for solving the University Course Timetabling Problem. The implementation includes:

• Greedy constructive initialization
• Neighborhood-based local search
• Iterated Local Search with controlled perturbations
• Memetic optimization combining genetic recombination and local improvement
• Convergence tracking for performance analysis

The framework is designed to facilitate benchmarking, parameter sensitivity studies, and comparative analyses across different timetabling instances.