Project Overview

Stundenplan25 is an automated timetabling software designed to generate optimal schedules for educational institutions. It replaces manual planning by intelligently assigning events (lectures, seminars) to timeslots and rooms while respecting predefined constraints. The system comprises a React frontend, Spring backend, MongoDB database, and a Python-based genetic algorithm server—the core component I developed. This project was developed as a software project for the Fachhochschule Wedel.

Backend Algorithm

I worked on the python backend for the scheduling. The algorithm-backend is receiving the relevant information from the spring project to generate a schedule from, additional information (such as more specific employee details) are not shared as they are not required for the algorithm.

To solve a schedule plan that satisfies all constraints a genetic-algorithm approach has been chosen to gradiually improve towards an optimal solution. The fitness is compared by the amount of unsatisfied constraints, therefore defining optimal as a fitness of 0.

Server

It was decided to implement the algorithm behind a server to be able to have a clear seperation between the services, and not have the performance-intensive genetic algorithm impact the performance of the other modules. Communication is realized via an REST-API.

This server and all the other services in this project have been developed as easily deloyable docker images.

Constraint Hierarchy

Prioritizes three constraint types:

1. Core Constraints: Non-negotiable rules.
2. Hard Constraints: Mandatory requirements.
3. Soft Constraints: Optional preferred preferences.

Optimization Strategy

Runs until all constraints are satisfied or a generation limit is reached. Favors completeness over speed due to the NP-hard nature of scheduling resulting in uncertainty of future success.

Constraints

Core Constraints

Core constraints are predefined constraints are always being attempted to satisfy for a given data input. The constraints are:

1. No employee can be scheduled more than one time for a single given timeslot.
2. No participant can be scheduled more than one time for a single given timeslot.
3. No event can be scheduled in a room with a wrong roomtype.
4. No event can be scheduled in a room with insufficient capacity.

Hard & Soft Constraints

Hard and soft constraints are only sementically seperated, logically they are the same. Hard constraints differ from soft constraints in the way that they have a higher priority of being satisfied than soft constraints.

EmployeeFreeTimeslots

Normal	Inverted
The specified employee (owner) does not want to have events scheduled during the given timeslots	The employee (owner) wants to only have events scheduled during the given timeslots

{
  "id": "string",
  "type": "EmployeeFreeTimeslots",
  "owner": "string",
  "inverted": boolean
  "fields": {
    "timeslots": [
      {"day": integer, "timeslot": integer}
    ]
  }
}

EmployeeSubsequentTimeslots

The employee (owner) wants no more than the specified amount (limit) of events to be scheduled subsequently.

{
  "id": "string",
  "type": "EmployeeSubsequentTimeslots",
  "owner": "string",
  "inverted": boolean // ignored
  "fields": {
    "limit": integer
  }
}

EventDistributeWeeklyBlocks

Normal	Inverted
All events with the specified event-name have to be scheduled at different days	All events with the specified event-name have to be scheduled at the same day

{
  "id": "string",
  "type": "EventDistributeWeeklyBlocks",
  "owner": "string",
  "inverted": boolean
  "fields": {
    "event": "string"
  }
}

Advanced Expressions

Expression constraints are a advanced type of constraints and are highly flexible. They are not evaluated by predefined logic, but instead the specified expression is evaluated.

{
  "id": "string",
  "type": "Expression",
  "owner": "string",
  "inverted": boolean // ignored
  "fields": {
    "expression": "string"
  }
}

An example would be: For all events it must apply that no event has employee "BOE" and is on day "1"

"expression": "all(not (has_employee('BOE', event) and on_day(event, 1)) for event in events)"

Data Format

Input

This is the required structure of input data. This data holds all relevant information for the algorithm to create a schedule from.

{
  "timeslots": [
    {
      "day": 1,
      "timeslot": 1
    }
  ],
  "rooms": [
    {
      "name": "ROOM_NAME",
      "capacity": 30,
      "room_type": "ROOM_TYPE" // e.g., "Hörsaal" or "Seminarraum"
    }
  ],
  "events": [
    {
      "name": "EVENT_NAME",
      "employees": ["EMPLOYEE_NAME"],
      "participants": ["PARTICIPANT_NAME"],
      "size": 25,
      "weekly_blocks": 1,
      "room_type": "REQUIRED_ROOM_TYPE"
    }
  ],
  "constraints": {
    "hard": [constraint],
    "soft": [constraint]
  }
}

Output

This is the structure of the result from the algorithm. This contains the final schedule with additional information about the satisfaction of the constraints.

{
  "data": {
    "timetable": [
      {
        "day": 1,
        "timeslot": 1,
        "event": "EVENT_NAME",
        "room": "ROOM_NAME",
        "participants": ["PARTICIPANT_NAME"]
      }
    ],
    "metadata": {
      "fitness": 0,
      "runtime": "0.00"
    },
    "constraints": {
      "core": {
        "fitness": 0,
        "unsatisfied": {
          "employee_conflicts": 0,
          "student_conflicts": 0,
          "room_capacity": 0,
          "room_type": 0
        },
        "satisfied": {
          "employee_conflicts": 0,
          "student_conflicts": 0,
          "room_capacity": 0,
          "room_type": 0
        }
      },
      "hard": {
        "fitness": 0,
        "unsatisfied": [constraint],
        "satisfied":  [constraint]
      },
      "soft": {
        "fitness": 0,
        "unsatisfied": [constraint],
        "satisfied": [constraint]
      }
    }
  },
  "timestamp": "YYYY-MM-DDTHH:MM:SS.SSSSSS",
  "status": "success"
}