Making a Class Schedule Using a Genetic Algorithm

Contents

• Introduction
• Background
• Objects of the Class Schedule
• Professor
• Student Group
• Classroom
• Course
• Class
• Chromosome
• Representation
• Fitness
• Crossover
• Mutation
• Algorithm
• Observing
• Configuration
• Configuration File
• Example of the Configuration File
• Parsing the Configuration
• Additional Information

Introduction

Making a class schedule is one of those NP hard problems. The problem can be solved using heuristic search algorithm to find optimal solution, but it works only for simple cases. For more complex inputs and requirements, finding a considerably good solution can take a while or it may be impossible. This is where genetic algorithms come into the game. In this article, I assume that you are familiar with the basic concepts of genetic algorithms, and won’t describe them in details because it has been done so many times before.

Background

When you make a class schedule, you must take into consideration many requirements (number of professors, students, classes and classrooms, size of classroom, laboratory equipment in classroom and many other). These requirements can be divided into several groups by their importance.

Hard requirements (if you break one of these, the schedule is infeasible):

• The class can be placed only in a spare classroom.
• No professor or student group can have more then on class at one time.
• The classroom must have enough seats to accommodate all students.
• To place a class in a classroom, the classroom must have laboratory equipment (computers in your case) if the class requires it.

Some soft requirements (can be broken but schedule is still feasible):

• Preferred time of class by professors.
• Preferred classroom by professors.
• Distribution (in time or space) of classes for student groups or professors.

Hard and soft requirements, of course, depend on the situation. In this example, only hard requirements are implemented. Let me start by explaining the objects on the class schedule.

Objects of the Class Schedule

Professor

The Professor class has the ID and name of professor. It also contains a list of classes that the professor teaches.

Student Group

The StudentsGroup class has the ID and name of the student group, as well as the number of students (size of group). It also contains a list of classes that the group attends.

Classroom

The Room class has the ID and name the of classroom, as well as the number of seats and information about equipment (computers). If the classroom has computers, it is expected that there is a computer for each seat. IDs are generated internally and automatically.

Course

The Course class has the ID and name of each course.

Class

CourseClass holds a reference to the course to which the class belongs, reference to the professor who teaches the class, and a list of student groups that attend the class. It also stores how many seats (sum of student groups’ sizes) are needed in the classroom, if the class requires computers in classroom and the duration of class (in hours).

Chromosome

The first thing you should consider when you deal with genetic algorithms is how to represent your solution in such a way that is feasible for genetic operations such as crossover and mutation. Also, you should know how to specify how good your solution is. In other words, you should be able to calculate the fitness value of your solution.

Representation

How do you represent chromosome for the class schedule? You need a slot (time-space slot) for each hour (assume that time is in one hour granules), for every room of every day. Also, assume that classes cannot begin before 9am and should finish before or at 9pm (12 hours total) and working days are from Monday to Friday (5 days total). You can use std::vector with size 12*5*number_of_rooms. Slot should be std::list because, during execution of your algorithm, you allow multiple classes at the same time-space slot.

There is an additional hash map that is used to obtain the first time-space slot at which class begins (its position in vector) from the address of a class’s object. Each hour of a class has a separate entry in the vector, but there is only one entry per class in the hash map. For instance, if a class starts at 1pm and lasts for three hours, it has entries in the 1pm, 2pm, and 3pm slots.

Figure 1: Chromosome Representation