Programming Assignment 15/10/19, 8)36 pm
https://myuni.adelaide.edu.au/courses/42679/assignments/121079 Page 1 of 6
Programming Assignment
Due No Due Date Points 100 Submitting a file upload
Submit Assignment
The University Class Scheduling Problem
Weigth 12%
Deadlines : 1st November 2019 for code (websubmission),
5th November 2019 for report (myUni)
This assignment can be done individually or in groups of two.
If you want to work with a partner, you need to choose one and enter your group by the end of Week 9 (11th
October) both in canvas and in the websubmission system. You cannot change or create new groups after
Week 9.
The due date for this assignment is the end of semester. There will be a lot of assignments in other courses
due by then - and the last prac exam is on Friday in Week 12 - so you must plan your time carefully up that
date and start as soon as you can.
Specification
The problem of building a university schedule consists of assigning a time and a teaching room for each of
the lectures in the planned courses. Also, the solution should satisfy the conditions that the University wants
to organize its teaching as described below.
Problem statement
The problem has the following elements:
Set of courses C={c ,c , ... , c } where each course has a fixed number of hours per week which can be
taught in one session or in several sessions during the week. For example if the third course c = 2 lecture
hours, they can be organised as a 2-hour session or as 2 x 1-hour sessions.
For simplicity we assume that each course has only one class, so there is no repeat lectures and we can
ignore the class size, as all classes will fit into the available teaching rooms.
The course names are given in course names CN = {n ,n , ... , n }, and will be used for printing, but are
not relevant to the scheduling problem.
1 2 m 3 1 2 m
Programming Assignment 15/10/19, 8)36 pm
https://myuni.adelaide.edu.au/courses/42679/assignments/121079 Page 2 of 6
Set of lecturers L={l ,l , ... , l } where l is the name of the ith lecturer. Each lecturer is already allocated to
one or multiple courses. The boolean matrix (TL) describes the teaching allocation, where a 1 in cell(i,j)
indicates course "i" is taught by lecturer "j"; note TL is a (m x n) matrix and each course will have either one
or two lecturers.
A week is made up of a set of teaching periods P={p1,p2, ... , p5k }. Each day has k periods of equal
length, in our case, k is 8 hours from 9 am to 5 pm. However, no classes will be allocated during the lunch
break (12 to 1 pm). The lessons lasting for more than one period cannot be interrupted by the lunch break.
Lecturers can indicate their preferences and availabilty to teach. The matrix lecturer preferences (LP)
describes the current commitments of each lecturer. A lecturer is allowed to block one full day for research
purposes and might have other work commitments; note LP is a (nx5k) matrix.
The values in LP have the following meaning: 0 means the lecturer is busy, 1 indicates 1st preference
for teaching, 2 indicates 2nd preference for teaching and 5 indicates available but prefer not to teach at
that time if possible.
Additional constraints:
Every session has to be assigned to a period or a number of periods, depending on the session length.
No teacher can teach more than two consecutive periods without a break.
Two sessions of the same course cannot be assigned to the same day (but one session can use two
consecutive periods).
Lecturers commitments (busy periods) as described in LP must be respected.
The number of concurrent sessions for all courses is limited by the number of lecture theatres.
The values listed above are provided in the input file described below. From that input, you need to
generate a timetable matrix (m x 5k), which specifies the allocation of each course session to a lecturer
and a time period. Your best timetable should be printed into an output file. Your optimal solution must be
valid, this means it complies with all constrains. When possible, you should try to match lecturer's
preferences. The goodness of the solution is calculated as the sum of LP values for all allocated sessions.
In some cases , it may not be possible to find a full solution; in that case you should return the best partial
solution in which the largest fraction of all courses has been scheduled. When comparing partial solutions,
each hour not allocated will increase the goodness value by 20. Note that the calculation of goodness of a
schedule is done by the Eval program you are provided with, you could reuse that code in your program.
Input and Output
The input for your solution is the ucs_setup file. This file contains the input information in the format listed
1 2 n i
Programming Assignment 15/10/19, 8)36 pm
https://myuni.adelaide.edu.au/courses/42679/assignments/121079 Page 3 of 6
below. See the example in the next section to clarify the meaning of the following.
r: the number of rooms or lecture theatres available
m: the number of courses
the next line lists the values of C (hours)
the next line list the course names CN
n: the number of lectuers
next line list of lecturers L
next m lines describe the content of TL
next n lines describes the content of TP
All lines with more than one value are comma-separated.
The output of your problem is in the form of m x 40 lines of comma-separated integers that list the
Timetable matrix. A session allocated to a period contains the lecturer index. The periods not allocated are
set to -1.
The value of your matrix is to be printed to an output file called fnl_soln.sch
An example input file and output file format is shown next.
Example Problem
Consider the following instance simple1:
Rooms 2
Courses 5
Hours 2, 3, 2, 4, 2
Names ADSA, EDC, PSSD, OOP, CS
Lecturers: 4
Cruz, Mingyu, Cheryl, Fred
%TL - binary mapping 1 or 0
0,0,1,0
1,1,0,0
1,0,0,0
0,1,0,0
0,0,0,1
%LP preferences
5,2,2,0,1,1,1,2,5,2,2,0,1,1,1,2,0,0,0,0,0,0,0,0,5,2,2,0,1,1,1,2,5,2,2,0,2,2,5,5
1,1,1,5,2,2,2,5,0,0,0,0,0,0,0,0,1,1,1,5,2,2,2,5,1,1,1,5,2,2,2,5,1,1,1,5,2,2,2,5
1,1,1,2,2,5,0,0,1,1,1,2,2,5,0,0,1,1,1,2,2,5,0,0,1,1,1,2,2,5,0,0,1,1,1,0,0,0,0,0
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0
In the input file we can see Cruz set Wednesday aside to do research, while Mingyu set Tuesday instead
and Fred has reserved Friday. Cheryl blocked the 3-5pm slot as she wants to leave early.
Programming Assignment 15/10/19, 8)36 pm
https://myuni.adelaide.edu.au/courses/42679/assignments/121079 Page 4 of 6
A possible solution (output) is given below
2 2, 22,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-
1,-1,-1,-1,-1,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1, 0,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 11, 11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-
1,-1,-1,-1,-1,-1
-1,-1,-1,-1,-1,-1, 0 0,-1,-1,-1,-1,-1,-1,-1, 00,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-
1,-1,-1,-1,-1,-1
-1, 1, 1 1, 1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 3, 3 3, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1, 3, 3 3, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-
1,-1,-1,-1,-1,-1,
The Eval porgram will check the matrix is valid and print the timetable from that solution.
Most allocations in this solution followed first preferences, except the morning lecture for EDC, which is a
second preference. Thus , the goodness score is 12. As this is a simple case, you could achieve a
goodness score of 11 by moving that lecture to another period that is first preference for Cruz and has an
available room.
Resources (to be provided soon)
A directory with some input and output cases will be provided during the mid-break and linked here
There is a C++ included with these cases called Eval.cpp which evaluates your solution with respect to its
TTP setup file. Eval sanity checks the timetable to see that all courses have been allocated and all
constrains are satisfied. It also calculates the goodness of the valid solution and prints the resulting
timetable in a friendly format.
Any violations print a message to stderr and return a value of INT_MAX on stdin. If your solution is valid
then Eval will print a number indicating how good your solution is. A lower number is better.
Programming Assignment 15/10/19, 8)36 pm
https://myuni.adelaide.edu.au/courses/42679/assignments/121079 Page 5 of 6
The websubmission systems handin key will be set up by the eond of week 9. The system has a process
limit of one minute per test case, so your solutions will need to be constrained to working in a short time.
You can use algorithms or ideas (but not code) from any location that you find. However, you must
credit these ideas in your code comments and in your other submission files so that we know where they
came from. If you use someone else's idea or a published algorithm and you make clear the extent of
someone else's contribution then you cannot get into trouble for misconduct. However, the marks that you
get will be aligned with the value that you personally add. If you use a published algorithm (again not code!)
and it forms a small part of the total product and you acknowledge the use and you made substantial
intellectual effort in the rest of the program then you can still get full marks.
What is a Basic Approach?
The scheduling problem at universities is considered an NP-hard problem for the number of possible
combinations.
Most solutions are developed incrementally, focusing on one part of the problem at a time. For example, you
could try the following three-phase approach ( 1- when, 2-where, 3-how good to lecturers)
1. You generate an initial timetable allocation, ignoring the lecturers preferences, and treating all non-busy
periods the same. You will also ignore the lecture theatre limit. This will make it easier to find an initial
solution.
2. You will then check if you have enough rooms to support your provisional timetable. If not, you will pick
the sessions that overflow the room capacity and try to allocate them to spare teaching periods. You may
have to repeat this step until you have a full solution.
3. In the next phase, you try to improve your solution by following on the lecturers' preferences. Then,
iteratively you check whether swapping a randomly picked session in the timetable reduces your
goodness score (do this with the Eval executable). If the new timetable plan yields a lower goodness
score, you take this new solution and you do step 3 again... until time is up.
Make sure to generate the file in the end!
What to submit
In your svn repository in a subdirectory called 2019/s2/pssd/assign1 you are to commit the following files:
a C++ source file called Schedule.cpp
a Makefile that will compile Schedule.cpp to a binary called schedule when the user runs make.
any other source files you will need to compile
Fill the logbook as you develop your solution. It should contain your ideas, hypotheses, reflections,
pointers to resources, commentary on mistakes and test results. The English does not have to be
polished; your source documents can be text or it can be direct scan of (readable) handwritten notes.
The logbook must be a believable commentary of what you did and tried while developing your program.
Besides, you should write a short report that describes the algorithm you used in plain English (with
snippets of pseudo code if you like). The formatting of this file can be basic - it can just be plain text but the
Programming Assignment 15/10/19, 8)36 pm
https://myuni.adelaide.edu.au/courses/42679/assignments/121079 Page 6 of 6
content must be clear and informative. We expect this report to be between 500 and 1500 words.
You should submit this report as a pdf file in myuni (if you work on pairs, each group member must write and
submit its own report).
How your work will be assessed
The breakdown of marks for this assignment are:
1. 45% for the actual results on the tests in websubmission
2. 5% for style and commenting of your source code
3. 25% for having the development process convincingly detailed in the logbook
4. 25% for a clear explanation of your algorithm in your report.
Start working early so you have a chance to improve your initial approach.
References:
Here are links to some papers that deal with more compliated versions of this problem. They will provide
algorithm approaches to find or improve a solution.
https://www.sciencedirect.com/science/article/pii/S0377221701000911
(https://www.sciencedirect.com/science/article/pii/S0377221701000911)
http://www.aloul.net/Papers/faloul_sch_gcc07.pdf (http://www.aloul.net/Papers/faloul_sch_gcc07.pdf)
(http://www.aloul.net/Papers/faloul_sch_gcc07.pdf)
https://pdfs.semanticscholar.org/e2ef/444bcbecef37110708d7e14d83bc028e5ed5.pdf
(https://pdfs.semanticscholar.org/e2ef/444bcbecef37110708d7e14d83bc028e5ed5.pdf)