Timetabling and Search

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.

- Your script must take 4 arguments -- no more and no less.
- One of those arguments is the name of an output file -- do not hardcode the name or the location to which it is written.
- Your script must be in the root/top level directory when it is un-tarred. That means not in a subdirectory created by the tar unpacking.
- Your output file must be written to the root/top level directory when it is un-tarred. That means not in a subdirectory created by the tar unpacking.

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:

**Hard Constraints:**

- Each course has one exam, which is conducted only once, and all students enrolled for the course must take the exam in the same time slot.
- The first day in the timetable is 1 and there are five time slots {1, 2, 3, 4, 5} available every day.
- There are no holidays! Also, there must be no unused timeslots between the first and the last day of exams in the timetable.
- Exams with one or more common students cannot be assigned to the same time slot, i.e. a student cannot take more than one exam in the same time slot.
- Multiple exams can be assigned to a single time slot.
- Total number of students taking exams in a given time slot should not exceed the room capacity specified in the problem.
- The total number of time slots used by the timetable should not exceed the maximum number of timeslots specified in the problem.

**Soft Constraints (Objective Functions):**

- Total number of timeslots used by the timetable should be minimized.
- Total student cost should be minimized. [See description of heuristic below]

**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:

- C(s') is the list of courses taken by the student s'.
- c1 and c2 are two different courses taken by the student s'.
- t(c1) denotes the time slot assigned to course c1.
- t(c2) denotes the time slot assigned to course c2.
- d(c1) denotes the date assigned to course c1.
- d(c2) denotes the date assigned to course c2.
- |t(c1)-t(c2)| denotes the absolute difference of the time slot assigned to c1 and that of c2.
- denotes the penalty for assigning time slots to the courses c1 and c2.

*Overnight Assignment Penalty* is calculated only for exams occurring
on different days and is calculated as follows:

- C(s') is the list of courses taken by the student s'.
- c1 and c2 are two different courses taken by the student s'.
- d(c1) denotes the date assigned to course c1.
- d(c2) denotes the date assigned to course c2.
- d(c1) and d(c2) are two different dates on which c1 and c2 are assigned.
- |d(c1)-d(c2)| denotes the absolute difference of dates assigned to c1 and that of c2.
- denotes the penalty for assigning dates to the courses c1 and c2.

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.

** **

**Example:**

**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.

**Example:**

**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.

**Example:**

**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:- the input course file
- the input student file
- the output exam file
- optimization function
- 0 indicates the number of timeslots
- 1 indicates total student cost

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

$1 is the name of the course (*.crs) file.

$2 is the name of the student (*.stu) file.

$3 is the name of the solution (*.sol) file.

$4 is the objective function and it can either be 0 or 1.

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.

- Describe your implementation. What algorithm did you chose? How did you implement it for this assignment? Treat this as though someone else is trying to re-implement what you did and provide enough details so that they could do so.
- Why did you select the search algorithm that you did? How did you choose parameter settings for it (e.g., neighborhood operator, initialization)? Cite any relevant literature or pilot experiments that you did.
- To what extent is your solution designed specifically for examination timetabling? What knowledge of the domain did you use in making your design decisions? What knowledge is the program using in constructing its solutions?
- Consider the two objective functions. To what extent is your solution designed for one or the other objective function? How did the results change with that function and with the problem type (e.g., the different test problems give)?

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:

- Script: timetableA2.sh, which must be in the root folder
- Source Code
- Your source code can be in the root folder
- Please do not run your code using an executable or binary file
- Your source code should be documented
- Essays answering the questions, which should be a PDF and should be named yourLastName.PDF

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!

- The code will be assessed on correctness, creativity and quality of solutions.
- Correctness amounts to whether you followed the requirements on I/O format, script construction, parameters and correctness of output (e.g., is the solution feasible, does the value calculated by the oracle match what was calculated by your program).
- Creativity allows us some degrees of freedom in crediting those who clearly demonstrated thought behind the solution.
- Quality is assessed relative to the rest of the class. All programs will be run on twice (once for each objective function) on two previously unreleased problems for a total of four runs per program. The quality of the solutions obtained will be ranked and points assigned based on the ranking. In sum, 10 points will be assigned based on quality rankings.
- Essays will be assessed based on readability, correctness (of both language and statements made), covering the required content and quality of the answers/thought behind the essays.