MACM 203 Assignment 6
Spring 2022
This assignment is due Tuesday March 8th at 10pm. Upload your solutions to Crowdmark.
Write your solutions as a single Matlab Live Script and export the script to PDF.
Write the course number and assignment number as the title of the Matlab Live Script,
followed by the table of contents, and then create a section for each part of the question.
Keep in mind that your assignment, including the source code, is a document that will
be read in order to be marked. It has to be very clear and properly formatted.
Your Matlab code must be general enough to solve any other instance of the same problem
without modification. That is, if you are asked to run your code on some data that are
specified in the assignment, then your code must run on any similar data set (or solve
any similar problem) without modification.
Assignments should be written individually. You can discuss in groups, but you have to
write your assignment yourself. In case of plagiarism SFU policies will be applied.
Preamble
This week’s assignment focuses on linear optimization.
Question 1 (20 marks)
In the current semester, the Top of the Mountain University (TMU) offers C courses
labelled 1, 2, . . . , C. The enrollment (number of students) in each course is given in the
row vector E. That is, E(i) is the number of students taking course i. Each course has a
final exam.
The university is about to schedule the final exams, and it hires you as a consultant to
design an optimal schedule of the exams. TMU students like to write their exams early
on in the examination period, as writing exams at earlier dates effectively extends the
length of the semester break that follows after the exam period. The exams are written in
S different time slots numbered 1, 2, . . . , S and scheduled in that order. The waiting time
perceived by one student when writing an exam is the number of the slot in which the
exam is written (any slot 1 exam has waiting time 1, any slot 2 exam has waiting time 2,
etc.) Therefore a course with enrollment of e students that has the exam scheduled in
slot s generates waiting time e · s.
Certain pairs of courses can not have their exams scheduled in the same slot because
there are students taking both courses. This information is represented by matrix A which
1
is C × C upper triangular matrix with zeros on the main diagonal, such that A(i, j) = 1
if courses i and j can not have exams in the same slot, and A(i, j) = 0 otherwise.
The objective of the optimal schedule is to minimize the total waiting time, which is
the sum of waiting times of all courses, subject to the scheduling constraints defined in
the previous paragraph.
Example. Suppose that C = 3, E = [37, 29, 51], S = 2 and
A =
0 0 1
0 0 0
0 0 0
.
That is, courses 1 and 3 have scheduling conflict, and there are no other conflicts. The
optimal solution is to schedule exams 2 and 3 into slot 1, and exam 1 into slot 2, at
the total waiting time 37 · 2 + 29 · 1 + 51 · 1 = 154. Another feasible solution is to
schedule exams 1 and 2 into slot 1, and exam 3 into slot 2, at the total waiting time
37 · 1 + 29 · 1 + 51 · 2 = 168. This solution is not optimal since the total waiting time is
not minimized.
Part (a)
Given C, S, E, A as above, write MATLAB code that finds an optimal schedule. You
can assume that the problem is solvable (feasible solutions exist). As a first test of your
code, use it to solve the example given above.
Hints:
- Study carefully posted solutions to Task Assignment problem and Advertisement
problem. Your solution will use ideas from these two posted solutions.
- Use C × S array x of optimization variables xi,j such that xi,j = 1 if course i has
exam scheduled in slot j, and xi,j = 0 otherwise.
- For each conflicting pair of courses i, j create the appropriate constraint by using
the sum of the i-th row of x and the j-th row of x. For simplicity you can use a double
for-loop and append the constraints one by one.
- Apply round to the optimal solution returned by MATLAB to make sure that each
entry in the optimal solution is integer 0 or 1. (MATLAB may return numerical approximations
that are not exactly 0 or 1.)
Part (b)
Download the data file a6.mat posted on the front page of Canvas, and use your code on
the data in that file to find an optimal schedule. Display the total waiting time for the
optimal schedule, and for each time slot display the courses whose exams are scheduled
into that slot.