Exam Scheduling

Contents

Problem description

At a technical university every term the third-year students choose eight modules from the eleven modules that are taught, depending on the option they wish to choose in the fourth year (there are two possible choices: "Production planning" and "Quality and security management"). In the current term, certain modules are obligatory for students who wish to continue with one of these options. The obligatory courses are Statistics (S), Graph models and algorithms (GMA), Production management (PM), and Discrete systems and events (DSE). The optional modules are: Data analysis (DA), Numerical analysis (NA), Mathematical programming (MP), C++, Java (J), Logic programming (LP), and Software engineering (SE).

Incompatibilities between different exams

+---+---+---+---+---+---+---+---+---+---+---+---+
|   | DA| NA|C++| SE| PM| J |GMA| LP| MP| S |DSE|
+---+---+---+---+---+---+---+---+---+---+---+---+
|DA | - | X | - | - | X | - | X | - | - | X | X |
|NA | X | - | - | - | X | - | X | - | - | X | X |
|C++| - | - | - | X | X | X | X | - | X | X | X |
|SE | - | - | X | - | X | X | X | - | - | X | X |
|PM | X | X | X | X | - | X | X | X | X | X | X |
|J  | - | - | X | X | X | - | X | - | X | X | X |
|GMA| X | X | X | X | X | X | - | X | X | X | X |
|LP | - | - | - | - | X | - | X | - | - | X | X |
|MP | - | - | X | - | X | X | X | - | - | X | X |
|S  | X | X | X | X | X | X | X | X | X | - | X |
|DSE| X | X | X | X | X | X | X | X | X | X | - |
+---+---+---+---+---+---+---+---+---+---+---+---+

Mrs Edeetee needs to schedule the exams at the end of the term. Every exam lasts two hours. Two days have been reserved for the exams with the following time slices: 8:00-10:00, 10:15-12:15, 14:00-16:00, and 16:15-18:15. For every exam she knows the set of incompatible exams that may not take place at the same time because they have to be taken by the same students. These incompatibilities are summarized in the table above.

Help Mrs Edeetee construct a timetable so that no student has more than one exam at a time.

Variables

incompatmat                Matrix of incompatabilities
slots                      Timeslots (2 days * 4 per day)

Reference

Applications of optimization... Gueret, Prins, Seveaux

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$
% Written Oct 7, 2005.   Last modified Apr 8, 2009.

Problem setup

incompatmat = [ 0 1 0 0 1 0 1 0 0 1 1;...
    1 0 0 0 1 0 1 0 0 1 1;...
    0 0 0 1 1 1 1 0 1 1 1;...
    0 0 1 0 1 1 1 0 0 1 1;...
    1 1 1 1 0 1 1 1 1 1 1;...
    0 0 1 1 1 0 1 0 1 1 1;...
    1 1 1 1 1 1 0 1 1 1 1;...
    0 0 0 0 1 0 1 0 0 1 1;...
    0 0 1 0 1 1 1 0 0 1 1;...
    1 1 1 1 1 1 1 1 1 0 1;...
    1 1 1 1 1 1 1 1 1 1 0];

slots = 8;

e = size(incompatmat, 1); %exams
t = slots;                %8 time slots

plan = tom('plan',e,t,'int');

% All variables are binary
bnds = {0 <= plan <= 1};

% Exam constraint
con1 = {sum(plan,2) == 1};

% Incompatibility constr.
ncon = nnz(triu(incompatmat));
con2 = cell(ncon,1);
count = 1;
for i=1:e-1
    for j=i+1:e
        if incompatmat(i,j) == 1
            for k=1:t
                con2{count} = {plan(i,k)+plan(j,k) <= 1};
                count = count + 1;
            end
        end
    end
end

% Objective
objective = 0;

constraints = {bnds, con1, con2};
options = struct;
options.solver = 'cplex';
options.name   = 'Exam Scheduling';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
    e_names = ['DA  '; 'NA  '; 'C++ '; 'SE  ';
        'PM  '; 'J   '; 'GMA '; 'LP  ';
        'MP  '; 'S   '; 'DSE '] ;
    exams   = length(e_names); % number of exams
    days    = 2;               % number of days
    times   = ['0800-1000'; '1015-1215'; '1400-1600'; '1615-1815'; ];
    slots   = size(times,1);   % time slots per day
    temp    = sol.plan;

    for d = 1:days,
        disp([' day number ' num2str(d)])
        for s = 1:slots,
            i = s + (slots)*(d-1);
            exams_now = find(temp(:,i));
            e_list = [];
            for e = 1:length(exams_now),
                e_list = [e_list e_names(exams_now(e),:)];
            end
            if ~isempty(e_list),
                disp(['  during ' times(s,:) ': ' num2str(e_list)])
            end
        end
    end
end

% MODIFICATION LOG
%
% 051205 med   Created.
% 060117 per   Added documentation.
% 060126 per   Moved disp to end
% 090308 med   Converted to tomSym
Problem type appears to be: mip
===== * * * =================================================================== * * *
TOMLAB - Tomlab Optimization Inc. Development license  999001. Valid to 2010-02-05
=====================================================================================
Problem: ---  1: Exam Scheduling                f_k       0.000000000000000000
                                              f(x_0)      0.000000000000000000

Solver: CPLEX.  EXIT=0.  INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found

FuncEv   40 
 day number 1
  during 0800-1000: DSE 
  during 1015-1215: S   
  during 1400-1600: GMA 
  during 1615-1815: PM  
 day number 2
  during 0800-1000: NA  J   LP  
  during 1015-1215: DA  C++ 
  during 1400-1600: SE  MP