Page 1 of 1

Need Help - Examination Timetable Generation

Posted: Fri May 09, 2008 2:39 am
by aa85
Hi all :mrgreen: ,
I'm a senior IT student and I'm working now on my final IT project. I've been assigned by my university to develop a web-based system to generate final examination time table for them, didn't really have a choice. I've been told to use php to code my system and connect it to a MySQL database (which is not a problem for me as I've done a dynamic website using php and MySQL before). My problem, and I really hope that u'll help me out here, is how to write an algorithm for generating the time table using php T_T ... my supervisor told me to use genetic algorithm :( which I don't have an idea about. So please, I really really need some help with this ... Really appreciate any help ^_^

With Heartfelt Thanks,
aa85

Re: Need Help - Examination Timetable Generation

Posted: Fri May 09, 2008 2:51 am
by onion2k
Sounds like your tutor has something pretty specific in mind. I think you'd be better off asking for more detail from him rather than us guessing.

Re: Need Help - Examination Timetable Generation

Posted: Tue May 20, 2008 8:51 am
by aa85
Hi all,

I tried to understand the idea of the algorithm from my supervisor and started to code using php. However, since I am not an expert in php programming, I faced problems in completing the code. Here is the code that I got till now, please I need ur comments and suggestions:
(The html form will contain: 1. Exam Period (in weeks) 2. starting date 3. ending date 4. program (BIT/BBA/Both))

<?php
extract($_POST);

//Connect to database and get list of subjects offered

if(!($database = mysql_connect("localhost", "timetable", "")))
die("Could not connect to database");
if(!mysql_select_db("CourseRegistration", $database))
die("Could not open Course Registration database");
$query = "Select * from Subjects";
if(!($subjects_array = array(mysql_query($query, $database)))){
print("Could not execute query! <br/>");
die(mysql_error());}

//Declare variables that will be needed

$no_of_days = 6*$weeks;
$total_students = 0;
$total_room_capacity = mysql_query("Select sum(capacity) from Halls", $database);
$TimeTableArray; //need it to be 2-dimensional

//Two loops (inner & outer) to generate the time table

for($rows = 0; $rows<$no_of_days; $rows++){
here I need to pick up the first subject in the array($subjects_array) and put it in the TimeTabelArray. Then delete the subject from the array, so that the program won't choose it again.
Make $total_students += student of the chosen subject.


for($cols = 0; $cols<5; $cols++){ //5 because only 5 halls are available, so max. 5 exams per day
here I need to pick up the next subject in the array($subjects_array), compare the students under this subject with the students of the previously chosen subject. If a student was found in both subjects, drop it and go back to the first for loop; otherwise, add the subject to the TimeTableArray, add the no. of students to the $total_students, and delete it from the $subjects_array.

if ($total_students < total_room_capacity/2) //coz two programs BIT & BBA so rooms should be divided equally between them.
continue in the same day (continue in the second loop)

else{
Use a method to rearrange the $subjects_array (to shift the still available subjects to the beginning of the array)
go to loop1}

}
}

//Assigning Halls

After the time table is generated, halls must be assigned to each exam (knapsack problem)...


//Assigning Chief Invigilators (all lecturers are assigned as chief invigilators)

This should be done using an array that will contain all the lecturers' names + the subjects they teach. Randomly assign each to an exam hall while checking that no lecturer assigned has one of his/her subjects' exam on that day.

?>

This is the whole idea of the code I need to write. Can anyone help me move step-by-step through it? I'd really appreciate any constructive modifications :D

Thank u in advance