Schedule Advisory: Investigating Genetic Algorithms to Solve Class Scheduling

Overview

A genetic algorithm is a heuristic that attempts to mimic natural selection and biological evolution. A genetic algorithm continuously modifies a population of individual solutions to a problem and uses a fitness function to select the best among the different solutions to the problem. In this project, the application of a genetic algorithm to the exponential time problem of scheduling students to their requested courses with a limited number of open spots is discussed. Because no polynomial solutions for this problem exist, heuristics and approximate solutions must be used. After experimenting with various algorithm parameters and measuring changes in fitness, it is shown that excellent scheduling results can be achieved when running the genetic algorithm for only 500 to 1000 iterations. Using the algorithm, 500 students can be scheduled within 425 minutes. For a typical school with 2,500 students, the genetic algorithm will be able to generate schedules for all students within hours, a major improvement from current scheduling systems which may take days to generate all students’ schedules. Furthermore, the genetic algorithm provides successful solutions on sample data for over 90% of students. Based on the results, it is shown that the proposed methods were successful in generating a quick and accurate approximate solution to the difficult problem of school class scheduling.

Awards (1)

• Oracle Academy: Award of $5,000 for outstanding project in the systems software category. $5,000

Competition history

• ISEF 2016 Category not listed · Entry SOFT041

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.