For this assignment, you are required to implement a search algorithm to solve examination timetabling problems. You have some latitude in your selection of language and algorithm. For language, if you wish to choose a language other than C, C++, Java or Python, you must obtain instructor's permission. Your code must be able to run on the linux machines in the Computer Science department. Make sure you test them there. If you do not have an account, please contact the instructor. If you don't know which machines are available, log into a machine and look at the file ~info/machines for a listing. The best machines to use are those in CSB120.
Implementations must be single-threaded. Solid understanding of the algorithms and application should be more important than clever programming or exploiting parallelism.
NEW as of 2/16 Reminder -- you must follow the I/O and submission guidelines exactly. We have set up the checkin program to ensure that you follow the instructions. The following has been repeated in the discussion board.
The assignment has two parts: the programming of the Examination Timetabling Problem (worth 66 points) and essays answering some questions about your implementation (worth 34 points).
The basics of the problem have already been described in class (see the first reading listed on the progress page). In our case, we assume that only one room with finite seating capacity is available for timetabling and five timeslots are available every day. Here is the list of hard and soft constraints:
Soft Constraints (Objective Functions):Our version of the problem will allow for one of the following two objective functions:
Total student cost is calculated as the following:
S is the total list of students and s' is a student.
Consecutive assignment penalty is calculated only for exams occurring on the same day and is calculated as follows:ConsecutiveAssignmentPenalty(s') =
Overnight Assignment Penalty is calculated only for exams occurring on different days and is calculated as follows:OvernightAssignmentPenalty(s') =
The objective, here, is to space out the assignment of exams as much as possible so that students have more time to prepare between their exams. Therefore, you must try to minimize the total student cost. This heuristic allows for exams with more students to be preferred for spacing out.
[Note: The terms "course" and "exam" can be used interchangeably in the following description]
1. Course file:
In the course file, the first row contains the room capacity and the maximum number of timeslots, respectively. The second row onward, every row has two columns, namely course code and total enrollment for that course. Enrollment represents the total number of students enrolled for that course.
Course File: instance1.crs
8 10 001 1 002 4 003 4 004 3 005 3 006 2 007 5 008 3 009 1 010 1
The room capacity in this problem is 8 and the maximum number of time slots is 10. Course 001 has 1 student enrollment; course 002 has 4 student enrollments and so on...
2. Student file:
In the student file, every row represents courses that a student has enrolled for.
Student File: instance1.stu
003 002 005 004 001 003 002 005 002 002 004 007 003 005 006 006 007 003 008 007 007 008 009 007 008 010 004
Student 1 has taken course 003 and course 002; Student 2 has taken course 005 and course 004; and so on...
In the output file, the first row has two columns, representing the two objective functions: total number of timeslots and the total student cost. The second row and the rows that follow contain the course number, date and time slot assigned to the course exam, respectively.
Solution File: instance1.sol
7 133.75 001 1 1 004 1 1 006 1 1 002 1 2 003 1 3 005 1 4 007 1 4 008 1 5 009 2 1 010 2 2
The number of time slots used is 7 and the total student cost is 133.75. Course 001, Course 004 and Course 006 are assigned day 1, timeslot 1; Course 002 is assigned day 1, timeslot 2; and so on...To make sure that everyone has implemented it properly, we will be verifying your solutions (as formatted above) as conforming to the problem constraints and verifying the reported objective function values.
For testing your program, you should run the instance1 problem described above.You should name your script "timetableA2.sh". Your script should take the following as its first 4 arguments, in the exact same sequence:
If your code needs to be compiled, your script should use a makefile to compile your code before running it.
Here's an example of how we will run your code:
$ ./timetableA2.sh instance1.crs instance1.stu instance1.sol 0
In the above case, your code is expected to produce instance1.sol, a valid timetable solution to the problem instance, in the same folder as your script.
Here's an example of a script that runs python source code timetableA2.py with command line arguments:
#!/bin/bash python timetableA2.py $1 $2 $3 $4
For algorithm, you should use one of the algorithms (with tuning) described in class or in the text; if you wish to use an algorithm other than that, you need to obtain instructor's permission. You get to choose the search algorithm and select parameters for implementation, e.g., ordering heuristics, neighborhood, initialization. In comments in your code, you should name the algorithm and cite your source for it.
The last 10 points will be awarded based on how well your program did on two test cases. Each evaluation trial will be allotted up to 10 minutes. The script will terminate the run at 10 minutes, so make sure your program writes its output before that. These points will be awarded as a direct function of rank based on minimizing the two objective functions. Ranks for each will be combined for a final ranking. Your program will be run on one of the Linux machines in the first floor lab (named after US Capitols); make sure your code runs on those machines.
The grading will include points for the quality of your implementation: how carefully you followed the instructions, how well it implements the method chosen, how efficiently it has been written, how easy it is to read and how creative/well justified were your design decisions.
You must submit your script and source code in a single TAR file. Your TAR file must be named PA2.tar.
Your submission must include the following things:
The script and the source code should be turned in via the checkin link on the class webpage. The essays should be turned in via Canvas.
Note: Your code MUST accept input in exactly the format specified. You code MUST produce an output file whose name can be specified (no hardcoding!) as an argument and be in exactly the format specified in this document. An automated test script will be used to run your code and validate your answers. If your format does not match, you will lose all points for program correctness and quality of results!Grading Criteria: