Submit Assignment
Programming Assignment Due No Due Date
Points 100
Submitting a file upload
The University Class Scheduling Problem
Weigth 12
Deadlines : 7th November 2019 for code websubmission,
10th 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 thenand the last prac exam is on Friday in Week 12so 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 Cc1,c2, … , cmwhere 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 c32 lecture hours, they can be organised as a 2hour session or as 2 x 1hour 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 CNn1,n2, … , nm, and will be used for printing, but are not relevant to the scheduling problem.
Set of lecturers Ll1,l2, … , lnwhere li 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 celli,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 Pp1,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
The values in LP have the following meaning: 0
busy, 1 indicates 1st preference for teaching,
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.
nx5k matrix.
means the lecturer is 2 indicates 2nd
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 timetablematrix 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 lecturers 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 ucssetup file. This file contains the input information in the format listed 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 commaseparated.
The output of your problem is in the form of m x 40 lines of commaseparated 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 fnlsoln.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
TLbinary mapping 1 or 0
0,0,1,0
1,1,0,0
1,0,0,0
0,1,0,1
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 35pm slot as she wants to leave early.
A possible solution output is given below
,
,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
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,1,1,1,1,1,1,1,1,1,
,
0,
1
1
1,1,1,1,1,1,
0
,1,1,1,1,1,1,1,
,1,1,1,1,1,1,
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,1,1,
,1,1,
1, 1
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,1,1,1,1,1,1,1,1,
3, 3
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
The Eval program 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 midbreak and linked here
There is a C included with these cases called EvalUCS.cpp which evaluates your solution with respect to its ucssetup 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 INTMAX on stdin. If your solution is valid then Eval will print a number indicating how good your solution is. A lower number is better.
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 elses idea or a published algorithm and you make clear the extent of someone elses 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 NPhard 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 threephase approach1 when, 2where, 3how good to lecturers
1. 2. 3.
You generate an initial timetable allocation, ignoring the lecturers preferences, and treating all nonbusy periods the same. You will also ignore the lecture theatre limit. This will make it easier to find an initial solution.
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.
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 2019s2pssdassign1 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 basicit can just be plain text but the 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. 2. 3.
4.
45 for the actual results on the tests in websubmission
5 for style and commenting of your source code
25 for having the development process convincingly detailed in the
logbook
25 for a clear explanation of your algorithm in your report.
Start working early so you have a chance to improve your initial approach.
Reviews
There are no reviews yet.