High School Course Scheduling: Student Preferences and Fairness Constraints (Student Abstract)

Mitsuka KiyoharaAAAI 2025 · DOI

TL;DR

This paper tackles the challenge of creating fair high school course schedules by extending traditional methods to incorporate student preferences and fairness constraints. They introduce a novel Integer Programming (IP) model that successfully generates equitable schedules without sacrificing feasibility, demonstrating a promising step towards more inclusive educational systems.

What Problem Does This Paper Address?

High schools are increasingly struggling with complex course scheduling due to growing student populations and a wider variety of course offerings. While existing methods like Constraint Programming (CP) focus on efficiency, they often overlook student preferences, leading to perceived unfairness in course assignments. Some schools attempt manual adjustments, but this is inefficient and error-prone. Traditional Integer Programming (IP) approaches for scheduling also haven't adequately addressed these fairness concerns. This paper aims to bridge this gap by developing a method that ensures both a feasible and equitable schedule, considering student desires and fairness principles.

Methods

The authors introduce the "Fair High School Scheduling Problem" (FHSSP) as an extension of the standard High School Scheduling Problem (HSSP). They define two key concepts:

  • Degree of Interest ($d_{s,c}$): A numerical score (0-1) representing a student's preference for a specific course.
  • Priority Order ($p_{s,c}$): A student's priority for a course, calculated based on academic performance (for prerequisite courses) or degree of interest.

To mitigate "student envy" (where a student feels disadvantaged compared to another with similar or higher interest/priority but better outcomes), they introduce a fairness constraint. This constraint ensures that a student $s$ does not envy student $s'$ if $s'$ is assigned a course $c$ that $s$ desires, $s$ has higher priority or interest, and $s$ is enrolled in fewer courses than $s'$.

They develop an Integer Programming (IP) model using binary encoding for decision variables and constraints. The solver has two objective functions: one to maximize overall course assignments (for HSSP) and another to minimize instances of student envy (for FHSSP).

Datasets

The experiments were conducted on a real-life dataset from a private high school in the San Francisco Bay Area, California. This dataset included course requests from 295 students for 121 courses. To handle missing information and ensure robust testing, artificial data was generated for instructors and rooms, incorporating assumptions about dedicated rooms, instructor capacities, weekly meeting frequencies, and maximum courses per student. Priority orders and student preferences were randomized within this artificial data.

Key Insights and Ideas

  • Bridging Market Design and Scheduling: The paper successfully adapts principles from market design (specifically fairness in matching markets) to the domain of high school course scheduling, a novel application.
  • Quantifying Fairness: By introducing "degree of interest" and "priority order," the authors provide a quantifiable way to represent student preferences and academic standing, which are crucial for defining fairness.
  • Formalizing Student Envy: The formal definition of student envy is a critical step towards mathematically modeling and mitigating this common source of dissatisfaction in scheduling.
  • Integrating Human Factors: The research highlights the feasibility of integrating subjective human preferences and emotions into objective mathematical models, paving the way for more human-centric AI systems.

Key Results

The IP model was evaluated on subsets of the real-world data. The key findings include:

  • The solver consistently produced feasible solutions for the HSSP across all experimental settings.
  • For the FHSSP, the model generated optimal solutions that eliminated all instances of student envy.
  • The experimental results, summarized in Table 1, show zero instances of student envy for all problem groups, with computation times ranging from approximately 18 to 27 seconds.

Limitations and Future Work

  • Limitations: The paper acknowledges that the artificial data generated for instructors and rooms, while necessary for experimentation, might not perfectly reflect real-world complexities. The randomization of priority orders and preferences also introduces a simplification.
  • Future Work: The authors suggest that this research is a small step towards creating more inclusive and balanced allocation systems. The approach has potential applicability to various real-world scheduling challenges beyond high schools.

Summary updated

BibTeX
@inproceedings{kiyohara2025high,
  author = {Mitsuka Kiyohara},
  title = {{High School Course Scheduling: Student Preferences and Fairness Constraints (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i28.35265},
}

Loading related content...

Figure