python/school-timetabling.ipynb

{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# School timetabling with Timefold in a Python Notebook\n",
    "\n",
    "This Python Jupyter Notebook solves a school timetabling problem with [Timefold](https://timefold.ai), the open source planning solver AI.\n",
    "It optimizes the school schedule for students and teachers.\n",
    "\n",
    "![School timetabling input output](https://timefold.ai/docs/timefold-solver/latest/_images/quickstart/school-timetabling/schoolTimetablingInputOutput.png)\n",
    "\n",
    "This Notebook automatically assigns each lesson to a timeslot and a room, while adhering to hard and soft constraints: \n",
    "\n",
    "* A room can have at most one lesson at the same time.\n",
    "* A teacher can teach at most one lesson at the same time.\n",
    "* A student can attend at most one lesson at the same time.\n",
    "* A teacher prefers to teach all lessons in the same room.\n",
    "* A teacher prefers to teach sequential lessons and dislikes gaps between lessons.\n",
    "* A student dislikes sequential lessons on the same subject.\n",
    "\n",
    "## Dependencies\n",
    "\n",
    "Add the Timefold solver dependency:"
   ],
   "id": "6dec503fd3832d94"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:50.207317Z",
     "start_time": "2024-12-03T17:01:49.652190Z"
    }
   },
   "cell_type": "code",
   "source": "pip install timefold==1.16.0b0",
   "id": "cba987b8c96efaf9",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: timefold==1.16.0b0 in ./.venv/lib/python3.12/site-packages (1.16.0b0)\r\n",
      "Requirement already satisfied: JPype1>=1.5.0 in ./.venv/lib/python3.12/site-packages (from timefold==1.16.0b0) (1.5.0)\r\n",
      "Requirement already satisfied: packaging in ./.venv/lib/python3.12/site-packages (from JPype1>=1.5.0->timefold==1.16.0b0) (24.1)\r\n",
      "\r\n",
      "\u001B[1m[\u001B[0m\u001B[34;49mnotice\u001B[0m\u001B[1;39;49m]\u001B[0m\u001B[39;49m A new release of pip is available: \u001B[0m\u001B[31;49m23.2.1\u001B[0m\u001B[39;49m -> \u001B[0m\u001B[32;49m24.3.1\u001B[0m\r\n",
      "\u001B[1m[\u001B[0m\u001B[34;49mnotice\u001B[0m\u001B[1;39;49m]\u001B[0m\u001B[39;49m To update, run: \u001B[0m\u001B[32;49mpip install --upgrade pip\u001B[0m\r\n",
      "Note: you may need to restart the kernel to use updated packages.\n"
     ]
    }
   ],
   "execution_count": 1
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "\n",
    "## Domain\n",
    "\n",
    "Create the domain data classes:\n",
    "\n",
    "### Room\n",
    "\n",
    "The `Room` class represents a location where lessons are taught, for example, `Room A` or `Room B`. For simplicity’s sake, all rooms are without capacity limits and they can accommodate all lessons."
   ],
   "id": "12dc3a813b0947a6"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:50.210957Z",
     "start_time": "2024-12-03T17:01:50.208545Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from dataclasses import dataclass\n",
    "\n",
    "@dataclass\n",
    "class Room:\n",
    "    name: str\n",
    "\n",
    "    def __str__(self):\n",
    "        return f'{self.name}'"
   ],
   "id": "757137072877cecd",
   "outputs": [],
   "execution_count": 2
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### Timeslot\n",
    "\n",
    "The `Timeslot` class represents a time interval when lessons are taught, for example, `Monday 10:30 - 11:30` or `Tuesday 13:30 - 14:30`. For simplicity’s sake, all time slots have the same duration and there are no time slots during lunch or other breaks."
   ],
   "id": "48cf34f40d476764"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:50.213742Z",
     "start_time": "2024-12-03T17:01:50.211558Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from dataclasses import dataclass\n",
    "from datetime import time\n",
    "\n",
    "@dataclass\n",
    "class Timeslot:\n",
    "    day_of_week: str\n",
    "    start_time: time\n",
    "    end_time: time\n",
    "\n",
    "    def __str__(self):\n",
    "        return f'{self.day_of_week} {self.start_time.strftime(\"%H:%M\")}'\n"
   ],
   "id": "fbb3e03a19772d26",
   "outputs": [],
   "execution_count": 3
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### Lesson\n",
    "\n",
    "During a lesson, represented by the `Lesson` class, a teacher teaches a subject to a group of students, for example, `Math` by `A.Turing` for `9th grade` or `Chemistry` by `M.Curie` for `10th grade`. If a subject is taught multiple times per week by the same teacher to the same student group, there are multiple `Lesson` instances that are only distinguishable by `id`. For example, the 9th grade has six math lessons a week.\n",
    "\n",
    "During solving, Timefold Solver changes the `timeslot` and `room` fields of the `Lesson` class, to assign each lesson to a time slot and a room. Therefore, those fields are annnoted with `@PlanningVariable` and the class with `@PlanningEntity`:"
   ],
   "id": "aecc532d51aa902b"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:50.686563Z",
     "start_time": "2024-12-03T17:01:50.214968Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from timefold.solver.domain import (planning_entity, PlanningVariable, PlanningId)\n",
    "from dataclasses import dataclass, field\n",
    "from typing import Annotated\n",
    "\n",
    "@planning_entity\n",
    "@dataclass\n",
    "class Lesson:\n",
    "    id: Annotated[str, PlanningId]\n",
    "    subject: str\n",
    "    teacher: str\n",
    "    student_group: str\n",
    "    timeslot: Annotated[Timeslot | None, PlanningVariable] = field(default=None)\n",
    "    room: Annotated[Room | None, PlanningVariable] = field(default=None)"
   ],
   "id": "e0b7bdd54c095a8d",
   "outputs": [],
   "execution_count": 4
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Constraints\n",
    "\n",
    "The solver takes into account hard and soft constraints:"
   ],
   "id": "5de0f51c16a9a40d"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:51.895573Z",
     "start_time": "2024-12-03T17:01:50.687407Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from timefold.solver.score import (constraint_provider, HardSoftScore, Joiners,\n",
    "                                   ConstraintFactory, Constraint)\n",
    "from datetime import time\n",
    "\n",
    "@constraint_provider\n",
    "def define_constraints(constraint_factory: ConstraintFactory):\n",
    "    return [\n",
    "        # Hard constraints\n",
    "        room_conflict(constraint_factory),\n",
    "        teacher_conflict(constraint_factory),\n",
    "        student_group_conflict(constraint_factory),\n",
    "\n",
    "        # Soft constraints\n",
    "        teacher_room_stability(constraint_factory),\n",
    "        teacher_time_efficiency(constraint_factory),\n",
    "        student_group_subject_variety(constraint_factory),\n",
    "    ]\n",
    "\n",
    "\n",
    "def room_conflict(constraint_factory: ConstraintFactory) -> Constraint:\n",
    "    # A room can accommodate at most one lesson at the same time.\n",
    "    return (constraint_factory\n",
    "            # Select each pair of 2 different lessons ...\n",
    "            .for_each_unique_pair(Lesson,\n",
    "                                  # ... in the same timeslot ...\n",
    "                                  Joiners.equal(lambda lesson: lesson.timeslot),\n",
    "                                  # ... in the same room ...\n",
    "                                  Joiners.equal(lambda lesson: lesson.room))\n",
    "            # ... and penalize each pair with a hard weight.\n",
    "            .penalize(HardSoftScore.ONE_HARD)\n",
    "            .as_constraint(\"Room conflict\"))\n",
    "\n",
    "\n",
    "def teacher_conflict(constraint_factory: ConstraintFactory) -> Constraint:\n",
    "    # A teacher can teach at most one lesson at the same time.\n",
    "    return (constraint_factory\n",
    "            .for_each_unique_pair(Lesson,\n",
    "                                  Joiners.equal(lambda lesson: lesson.timeslot),\n",
    "                                  Joiners.equal(lambda lesson: lesson.teacher))\n",
    "            .penalize(HardSoftScore.ONE_HARD)\n",
    "            .as_constraint(\"Teacher conflict\"))\n",
    "\n",
    "\n",
    "def student_group_conflict(constraint_factory: ConstraintFactory) -> Constraint:\n",
    "    # A student can attend at most one lesson at the same time.\n",
    "    return (constraint_factory\n",
    "            .for_each_unique_pair(Lesson,\n",
    "                                  Joiners.equal(lambda lesson: lesson.timeslot),\n",
    "                                  Joiners.equal(lambda lesson: lesson.student_group))\n",
    "            .penalize(HardSoftScore.ONE_HARD)\n",
    "            .as_constraint(\"Student group conflict\"))\n",
    "\n",
    "\n",
    "def teacher_room_stability(constraint_factory: ConstraintFactory) -> Constraint:\n",
    "    # A teacher prefers to teach in a single room.\n",
    "    return (constraint_factory\n",
    "            .for_each_unique_pair(Lesson,\n",
    "                                  Joiners.equal(lambda lesson: lesson.teacher))\n",
    "            .filter(lambda lesson1, lesson2: lesson1.room != lesson2.room)\n",
    "            .penalize(HardSoftScore.ONE_SOFT)\n",
    "            .as_constraint(\"Teacher room stability\"))\n",
    "\n",
    "\n",
    "def to_minutes(moment: time) -> int:\n",
    "    return moment.hour * 60 + moment.minute\n",
    "\n",
    "\n",
    "def is_between(lesson1: Lesson, lesson2: Lesson) -> bool:\n",
    "    difference = to_minutes(lesson1.timeslot.end_time) - to_minutes(lesson2.timeslot.start_time)\n",
    "    return 0 <= difference <= 30\n",
    "\n",
    "\n",
    "def teacher_time_efficiency(constraint_factory: ConstraintFactory) -> Constraint:\n",
    "    # A teacher prefers to teach sequential lessons and dislikes gaps between lessons.\n",
    "    return (constraint_factory.for_each(Lesson)\n",
    "            .join(Lesson,\n",
    "                  Joiners.equal(lambda lesson: lesson.teacher),\n",
    "                  Joiners.equal(lambda lesson: lesson.timeslot.day_of_week))\n",
    "            .filter(is_between)\n",
    "            .reward(HardSoftScore.ONE_SOFT)\n",
    "            .as_constraint(\"Teacher time efficiency\"))\n",
    "\n",
    "\n",
    "def student_group_subject_variety(constraint_factory: ConstraintFactory) -> Constraint:\n",
    "    # A student group dislikes sequential lessons on the same subject.\n",
    "    return (((constraint_factory.for_each(Lesson)\n",
    "              .join(Lesson,\n",
    "                    Joiners.equal(lambda lesson: lesson.subject),\n",
    "                    Joiners.equal(lambda lesson: lesson.student_group),\n",
    "                    Joiners.equal(lambda lesson: lesson.timeslot.day_of_week))\n",
    "              .filter(is_between))\n",
    "             .penalize(HardSoftScore.ONE_SOFT))\n",
    "            .as_constraint(\"Student group subject variety\"))\n"
   ],
   "id": "fed72b2424334a18",
   "outputs": [],
   "execution_count": 5
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### TimeTable\n",
    "\n",
    "The `TimeTable` class represents a single dataset. It wraps all `Timeslot`, `Room`, and `Lesson` instances. Furthermore, because it contains all lessons, each with a specific planning variable state, it is a planning solution, and it has a `score` field:"
   ],
   "id": "1c66d25d005f531"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:51.900315Z",
     "start_time": "2024-12-03T17:01:51.896387Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from timefold.solver.domain import (planning_solution, \n",
    "                                    PlanningEntityCollectionProperty, ProblemFactCollectionProperty,\n",
    "                                    ValueRangeProvider,\n",
    "                                    PlanningScore)\n",
    "from timefold.solver.score import HardSoftScore\n",
    "from dataclasses import dataclass, field\n",
    "from typing import Annotated\n",
    "\n",
    "@planning_solution\n",
    "@dataclass\n",
    "class Timetable:\n",
    "    timeslots: Annotated[list[Timeslot], ProblemFactCollectionProperty, ValueRangeProvider]\n",
    "    rooms: Annotated[list[Room], ProblemFactCollectionProperty, ValueRangeProvider]\n",
    "    lessons: Annotated[list[Lesson],  PlanningEntityCollectionProperty]\n",
    "    score: Annotated[HardSoftScore, PlanningScore] = field(default=None)"
   ],
   "id": "f62624e265cbf78a",
   "outputs": [],
   "execution_count": 6
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Data generator\n",
    "\n",
    "Generate some data for a small school timetable:"
   ],
   "id": "742518a0d8763b59"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:51.904492Z",
     "start_time": "2024-12-03T17:01:51.900930Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def generate_demo_data() -> Timetable:\n",
    "    timeslots = [\n",
    "        Timeslot(day, start, start.replace(hour=start.hour + 1))\n",
    "        for day in ('MONDAY', 'TUESDAY')\n",
    "        for start in (time(8, 30), time(9, 30), time(10, 30), time(13, 30), time(14, 30))\n",
    "    ]\n",
    "\n",
    "    rooms = [Room(f'Room {name}') for name in ('A', 'B', 'C')]\n",
    "\n",
    "    lessons = []\n",
    "\n",
    "    def id_generator():\n",
    "        current = 0\n",
    "        while True:\n",
    "            yield str(current)\n",
    "            current += 1\n",
    "    ids = id_generator()\n",
    "    lessons.append(Lesson(next(ids), \"Math\", \"A. Turing\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Math\", \"A. Turing\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Physics\", \"M. Curie\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Chemistry\", \"M. Curie\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Biology\", \"C. Darwin\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"History\", \"I. Jones\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"English\", \"I. Jones\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"English\", \"I. Jones\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Spanish\", \"P. Cruz\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Spanish\", \"P. Cruz\", \"9th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Math\", \"A. Turing\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Math\", \"A. Turing\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Math\", \"A. Turing\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Physics\", \"M. Curie\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Chemistry\", \"M. Curie\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"French\", \"M. Curie\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Geography\", \"C. Darwin\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"History\", \"I. Jones\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"English\", \"P. Cruz\", \"10th grade\"))\n",
    "    lessons.append(Lesson(next(ids), \"Spanish\", \"P. Cruz\", \"10th grade\"))\n",
    "\n",
    "    return Timetable(timeslots, rooms, lessons)"
   ],
   "id": "f12e88884314eab9",
   "outputs": [],
   "execution_count": 7
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Solve it\n",
    "\n",
    "Configure and run the solver:"
   ],
   "id": "59d1a178f2e52c55"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:57.163746Z",
     "start_time": "2024-12-03T17:01:51.905065Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from timefold.solver.config import (SolverConfig, ScoreDirectorFactoryConfig,\n",
    "                                    TerminationConfig, Duration)\n",
    "from timefold.solver import SolverFactory\n",
    "\n",
    "solver_factory = SolverFactory.create(\n",
    "    SolverConfig(\n",
    "        solution_class=Timetable,\n",
    "        entity_class_list=[Lesson],\n",
    "        score_director_factory_config=ScoreDirectorFactoryConfig(\n",
    "            constraint_provider_function=define_constraints\n",
    "        ),\n",
    "        termination_config=TerminationConfig(\n",
    "            # The solver runs only for 5 seconds on this small dataset.\n",
    "            # It's recommended to run for at least 5 minutes (\"5m\") otherwise.\n",
    "            spent_limit=Duration(seconds=5)\n",
    "        )\n",
    "    ))\n",
    "\n",
    "problem = generate_demo_data()\n",
    "\n",
    "print(f'Solving the problem ...')\n",
    "solver = solver_factory.build_solver()\n",
    "solution = solver.solve(problem)\n",
    "print(f'Solving finished with score ({solution.score}).')"
   ],
   "id": "1ff2655f5e7cb952",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving the problem ...\n",
      "Solving finished with score (0hard/9soft).\n"
     ]
    }
   ],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Visualize the schedule\n",
    "\n",
    "Show the timetable:"
   ],
   "id": "1507377c5b4202eb"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:57.165598Z",
     "start_time": "2024-12-03T17:01:57.164373Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "c07ec007586d9b1f",
   "outputs": [],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Statistics\n",
    "\n",
    "For a big dataset, a schedule visualization is often too verbose.\n",
    "Let's visualize the solution through statistics:"
   ],
   "id": "af3104e744aaab5c"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:57.168302Z",
     "start_time": "2024-12-03T17:01:57.167082Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "de2f517b6984e6a9",
   "outputs": [],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### Lessons per teacher per weekday",
   "id": "b386244b443664b4"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:57.170275Z",
     "start_time": "2024-12-03T17:01:57.168886Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "15f7406561f9b654",
   "outputs": [],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### Lessons per teacher per hour",
   "id": "9e9d6234afcea2a7"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:57.171920Z",
     "start_time": "2024-12-03T17:01:57.170794Z"
    }
   },
   "cell_type": "code",
   "source": "",
   "id": "e05dff3172e2a086",
   "outputs": [],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Analyze the score\n",
    "\n",
    "Let's break down the score per constraint:"
   ],
   "id": "2ef86c5b9b2f3d70"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T17:01:57.184875Z",
     "start_time": "2024-12-03T17:01:57.172408Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from timefold.solver import SolutionManager\n",
    "\n",
    "solution_manager = SolutionManager.create(solver_factory)\n",
    "score_analysis = solution_manager.analyze(solution)"
   ],
   "id": "21360362608c6152",
   "outputs": [],
   "execution_count": 9
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "And visualize it:",
   "id": "2c9dd9ef8ac27fff"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-12-03T19:00:08.945516Z",
     "start_time": "2024-12-03T19:00:08.941667Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from IPython.core.display import HTML\n",
    "\n",
    "html_content = f\"<p style='font-size: x-large'>Score: {score_analysis.score}</p>\"\n",
    "html_content += \"<ul>\"\n",
    "for constraint in score_analysis.constraint_map.values():\n",
    "    html_content += f\"<li>{constraint.constraint_name}: {constraint.score}</li>\"\n",
    "html_content += \"</ul>\"\n",
    "\n",
    "HTML(html_content)"
   ],
   "id": "cc07c2e07d3ba32",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ],
      "text/html": [
       "<p style='font-size: x-large'>Score: 0hard/9soft</p><ul><li>Teacher time efficiency: 0hard/9soft</li><li>Student group subject variety: 0hard/0soft</li><li>Teacher room stability: 0hard/0soft</li><li>Room conflict: 0hard/0soft</li><li>Student group conflict: 0hard/0soft</li><li>Teacher conflict: 0hard/0soft</li></ul>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "execution_count": 12
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Conclusion\n",
    "\n",
    "To learn more about planning and scheduling optimization, visit [timefold.ai](https://timefold.ai)."
   ],
   "id": "ccd11e80f0f48800"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}