The University Class Scheduling Problem

The problem has the following elements: Set of courses C={c1,c2, ... , cm } 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 c3 = 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 = {n1,n2, ... , nm}, and will be used for printing, but are not relevant to the scheduling problem. Set of lecturers L={l1,l2, ... , ln } where 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 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 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 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 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,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 3-5pm slot as she wants to leave early. A possible solution (output) is given below 2, 2,-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,-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, 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,-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, 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 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 mid-break and linked here There is a C++ included with these cases called EvalUCS.cpp which evaluates your solution with respect to its ucs_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. 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 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.