CS 540, Spring 2015: Assignment 2
Timetabling and Search

Due Tuesday 2/17/14 at noon MST

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.

Failure to follow these instructions means that you will not get credit for your hard work. Please follow them carefully and do not wait until late Monday night or Tuesday morning to do so.

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

I. Examination Timetabling Problem

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:

Soft Constraints (Objective Functions):

Our version of the problem will allow for one of the following two objective functions: Total number of timeslots is simply how many were needed. In this case, we are favoring packed schedules.

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]

A. Input Format

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

2. Output Format

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.

3. Submission Instructions

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

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

4. Search Algorithm

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.

II. Essay Questions

  1. 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.
  2. 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.
  3. 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?
  4. 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)?
Each answer is expected be 1/2-1 page in length.

III. Grading: What to turn in? How will it be judged?

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: