Solving a Class Scheduling Problem using Genetic Algorithm
Project Proposal
Description
As scientists we were asked to solve a Constraint Satisfaction Problem (CSP) to implement our knowledge as one of the steps in the learning process. Constraint Satisfaction Problems are problems that are defined as a set of objects whose state must be satisfied within the given limitation and constraints. In this opportunity the CSP that we choose is a class scheduling problem.
Problems
Problems happening in the real world are represented as a list of constraints that has to be satisfied by the solution of this class scheduling. The constraints are:
- Each classroom can only be use for one class in the same time
- Each class room have different student capacity amount
- Classes with class type kuliah (listen to lecturer explanation) or responsi (do problem exercise without computer) will be held in ordinary classroom
- Classes with type praktikum (practicing solving a problem with a computer) can only be held in a computer lab
Question
To ensure the effectiveness of this experiment, the following question should be answered:
- What data do we need?
- Is there a solution for this problem?
- How long does it take to find the solution?
- How many combinations of solutions can we find?
Approaches
To answer the question that we had just mentioned, the following methods and will be considered
- After some research we decided to solve the class scheduling CSP with genetic algorithm
- This algorithm will keep running until the given number of iteration, supposedly by the end we will find the solution, if there’s a solution that satisfies all the constraints
- Genetic algorithm is inspired by natural process of survival of the fittest, in this case the individual is a set of class schedule, and each individual in each generation will have fitness value that show how close they are from satisfying the constraints
- If all the constraints are satisfied, the fitness value will be one. The solution is an individual of the population with fitness value of one
Project Execution
Data
The data that we need are classrooms that will be used and each capacity, meeting times or the possible time for classes to be held, list of courses and each number of students that take them, and lastly which classes belong to class type kuliah, responsi or praktikum.
Data Entry
Because it’s not a large amount of data, we input it manually as part of the code. Later if we want to use it for different cases of classes, and rooms we can make the data input manually by the user every time we have a class scheduling problem. But for the sake of simpleness for this experiment, we put the data as a part of the program.
Customize the program
The source code of this program is from this video. We customize the program to fit our problem better. Such as adding class type, and removing the variable of lecturer.
Result
The first column shows the number of individuals in that generation, the second one is the fitness value of that individual. If that individual has only 1 conflict meaning this individual didn’t satisfy just one of the many constraints. In this case an individual is a set of class schedules.
We finally found an individual with fitness value 1 in generation 7th. Out of the two individual that have fitness value 1 we pick one of them as a solution, and here it is:
To answer the previous question of what data that we need, we need data of classrooms, meeting times, list of courses and each number of students that take them, and lastly which classes belong to class type. The next question is, is there a solution for this problem? Yes there is, the time needed was 7 iteration, and we found 2 possible solutions.
