University Timetable Scheduling Project using Genetic Algorithm (JAVA)
Personal Info: Hello everyone, I'm a computer science student; who (unfortunately) has to work on this NP-Complete problem for my Final Year Project. I am not so experienced in programming beyond my assignments and things I learned in University. So I apologies for any ignorant questions I might ask.
University Timetable Scheduling Project using Genetic Algorithm:
This is my topic for Final year Project of university. I have already gathered information needed and wrote my proposal and progress report so I am fully aware of the fact that, this topic is NP-Complete. However the goal of my project is not to create golden timetable, fully optimal and with no problem but instead I just have to make sure that it is acceptable and does not break some of my rules.
Regarding my methodology and the way that I want to create this application, I have decided to use two main Artificial Intelligence techniques to solve the problem; Genetic Algorithm and Constraint satisfaction. I came up with some rules and divided them in to two main groups; soft constraints and hard constraints. So the algorithm should work this way:
Assuming that we have our inputs (classrooms and their capacities, Subject names, lecturers and the amount of students signed up for them). The application starts with generating random timetables. However I decided to Implement my hard constraints, one that cannot be ignored (such as having same lecturer teaching more than one classes at same time or classroom being occupied with more than one subject at any given time) at this stage. So basically we are generating random timetables but as we are creating them, we apply the hard constraints to them. I would like to call it guided randomly generated timetables. The next stage is to find the best possible timetable. Using the previous technique I talked about; We already know the generated timetables are acceptable in terms of hard constraints now using genetic algorithm I will find the best possible (most optimal) timetable and get that as the result. So soft constraints ( such as having break between classes, avoiding same subject having more than one class everyday and such) would be used in my GA's fitness function.
All of these was good approach to solve the problem, until I started programming. Well they looked good on paper, but my programming skills are holding me back to finish the project.
I have some questions regarding the coding part, that I would appreciate if you guys can help me.
Questions: 1. Any good tutorial and guideline, manual for Genetic algorithm libraries in java ? I decided to use Jgap, from people's suggestions on other threads but I cannot really find any good tutorial on internet about it and unfortunately after ours of looking at some examples provided in Jgap library i still cannot figure out what is happening there.
- For the constraint programming part that I want to apply, do I have to use any specific library on Java or I can do it with If/Else or switch statements ? If so please let me know of the name and details.
Most important question: 1. How to create timetable? Ok, As i said I am not a good programmer. So you can assume that I'm stuck at the very first step of my project, creating timetable. Do I have to treat it as an object? and what sort of data structure you guys usually use to create such as timetable? Array, linklist, queue ?
Here is my attempt on creating timetable:
**UPDATED**
After working for sometimes on this project. I managed to create the Timetable. Here is the update to the classes I previously shared.
public class Subject {
public String name;
public int Students;
public String NameOfLecturer;
public ClassVenu addVenues;
public Subject(String argName, String argNameofLecturer, int argStudents)
{ name = argName; NameOfLecturer=argNameofLecturer; Students=argStudents;
}
public String toString() { return name;}}
public class ClassVenu {
public String ClassName;
public int ClassCapacity;
public ClassVenu(int argClassCapacity, String argClassName)
{ ClassName = argClassName; ClassCapacity = argClassCapacity; }
}
public class Days extends Hours{
public Days(Subject a, Subject b,Subject c, Subject d,Subject e, Subject f,Subject g,Subject h, Subject j)
{int i=0;
TimeSlot[i]=a;
TimeSlot[i+1]=b;
TimeSlot[i+2]=c;
TimeSlot[i+3]=d;
TimeSlot[i+4]=e;
TimeSlot[i+5]=f;
TimeSlot[i+6]=g;
TimeSlot[i+7]=h;
TimeSlot[i+8]=j;
}
package fyp_small_timetable;
public class Hours {
public Subject [] TimeSlot = new Subject[9];
}
package fyp_small_timetable;
public static void main(String[] args) {
//creating Subjects
Subject A = new Subject("Human Computer Interaction", "Batman" , 49);
Subject B = new Subject("Artificial Intelligence", "Batman" , 95);
Subject C = new Subject("Human Computer Interaction", "Batman" ,180);
Subject D = new Subject("Human Computer Interaction", "Batman" , 20);
Subject E = new Subject("Empty", "No-One", 0);
//Creating Class Venue
ClassVenu Class1 = new ClassVenu(100,"LecturerTheater1");
ClassVenu Class2 = new ClassVenu(50,"LecturerTheater2");
ClassVenu Class3 = new ClassVenu(200,"LecturerTheater3");
//Creating Days
Days Day1 =new Days(A, A, E, B, B, E, E, A, A);
Days Day2 =new Days(C, C, E, D, D, E, E, A, A);
Days Day3 =new Days(E, E, E, B, B, E, E, A, A);
Days Day4 =new Days(C, C, E, C, C, E, E, A, A);
Days Day5 =new Days(A, A, E, B, B, E, E, A, A);
//creating Timetable
TimeTable T1 = new TimeTable(Day1, Day2, Day3, Day4, Day5);
List<Subject> answer = T1.ShowTimetable(T1);
System.out.println(answer);
}
}
Please keep in mind that, the code shown above, is just a prototype (my attempt to create timetable).
If anyone is willing to help me I can provide full documentation of what I have done so far in this project.
Thanks for anyone who helps me and wish this can help others too Hirad
Answer
I have used genetic algorithms to solve University timetable scheduling problem in a production application.
Do not worry too much about the library to use there are many great java GA libraries out there.
What you should focus you attention on is the way in which you encode your candidate timetables. Typically you would use a numeric representation, for example ['math', 'chemistry', physics] = [1, 4, 6] each number represents a unique class while the index of that number represents the time that class will be offered. The fitness function would then take a multidimensional array of values representing a population of candidate schedules, this population would then be compared to a student listing and constraints applied such as clashing and a possible fitness calculated.
You may also want to think of fitness normalization .
Most importantly do not use objects to store your timetable information instead use simple integer arrays, this will dramatically increase the speed of your Generic algorithm.