Creating schedule

The aim of the project was to develop and examine the effectiveness of a genetic algorithm in generating optimal class schedules for university students. The algorithm took into account key constraints, such as elective courses, room availability, lecturer schedules, and student preferences regarding class hours. The entire system was implemented in Python, allowing for flexible testing of various parameters and scenarios.

1. Project Assumptions

The main goal was to create a tool that automatically generates class schedules while minimizing conflicts and maximizing convenience for both students and lecturers. The project aimed to solve an NP-hard problem, namely class scheduling, by applying techniques inspired by the process of biological evolution.

Considered Constraints:

  • Elective courses: Each student could choose a set of subjects, which required them to be adapted to the overall schedule.
  • Room availability: The number of available rooms and their capacity had to be respected to avoid situations where the number of participants exceeded the capacity of a given room.
  • Lecturer schedules: Lecturers had predetermined hours of availability.
  • Class hours: Classes could not overlap in time for groups attending different subjects.

2. Description of the Genetic Algorithm

The genetic algorithm operated based on a simulation of the evolutionary process, in which „individuals” (candidates for solutions) were evaluated and optimized over successive generations.

Basic Elements of the Algorithm:

  1. Chromosome Representation:
    • A chromosome represented a potential class schedule. Each gene corresponded to an individual subject and contained information such as class time, room, and student group.
  2. Fitness Function:
    • The function evaluated the quality of the class schedule, considering:
      • Minimization of scheduling conflicts.
      • Matching the number of students to room capacity.
      • Considering lecturer availability.
      • Respecting student preferences for class times (e.g., avoiding early morning classes).
  3. Population Initialization:
    • The algorithm started by randomly generating a population of candidate solutions. Each schedule in this population was generated partially randomly but still respected basic constraints.
  4. Selection:
    • Individuals with higher fitness function values had a greater chance of advancing to the next stages (e.g., roulette wheel selection or tournament selection).
  5. Crossover:
    • Candidates were crossed to create a new class schedule by exchanging chromosome fragments (e.g., dividing into gene groups corresponding to different days of the week).
  6. Mutation:
    • Small random changes were introduced in the chromosomes, such as shifting class times or changing rooms. This helped the algorithm avoid getting stuck in local minima.
  7. Evolution:
    • The process of selection, crossover, and mutation was repeated for a defined number of generations or until stopping criteria were met (e.g., obtaining a schedule with a sufficiently high fitness function value).

3. Project Implementation Process

1. Collecting Input Data:

  • The input data included:
    • A list of subjects assigned to student groups.
    • A list of available rooms with their capacities.
    • A schedule of lecturer availability.
    • Students’ time preferences.

2. Algorithm Implementation:

  • The algorithm was implemented in Python using libraries such as numpy (for numerical computations) and matplotlib (for visualizing results).
  • Input data was represented in structures such as lists and dictionaries, allowing dynamic schedule adjustments.

3. Algorithm Testing:

  • The algorithm was tested on various datasets, ranging from small student groups to more complex scenarios involving multiple subjects, rooms, and student groups.
  • Results were compared with manually created schedules to evaluate the quality of solutions generated by the algorithm.

4. Parameter Optimization:

  • Algorithm parameters, such as population size, number of generations, and crossover and mutation rates, were fine-tuned to achieve the best results.

4. Project Results

  • Efficiency: The genetic algorithm effectively minimized scheduling conflicts, such as overlapping classes in rooms or lecturer unavailability.
  • Adaptation: In tests on large datasets, the algorithm generated schedules that met over 95% of the defined requirements (e.g., no collisions, fulfillment of student preferences).
  • Execution Time: Depending on the complexity of the problem, the generation time varied from a few seconds for simple scenarios to several minutes for more complex cases.
  • Flexibility: The algorithm easily adapted to changing conditions, such as adding new subjects, groups, or rooms.

5. Development Possibilities

  • Integration with university systems: Automatic retrieval of data on subjects, students, and classrooms.
  • Graphical interface: Visualization of the schedule in an interactive GUI, allowing manual editing.
  • Further optimization: Improving the fitness function by introducing more detailed criteria (e.g., minimizing gaps in students’ schedules).
  • Algorithm expansion: Combining the genetic algorithm with other optimization methods, such as the Simulated Annealing algorithm.

This project serves as an example of the application of genetic algorithms to practical optimization problems. The implemented solution not only automates the process of creating schedules but also allows them to be adjusted to complex constraints and preferences

pl_PLPolish
en_GBEnglish pl_PLPolish
Scroll to Top