Description

 A set of 13 real-world exam timetabling problems http://www.cs.nott.ac.uk/~pszrq/data.htm http://www.asap.cs.nott.ac.uk/external/resources/
 For this assignment, we use five benchmark cases:
 CAR91, CAR92, KFU93, TRE92, YOR83
 yor-f-83.crs (input: course file), yor-f-83.stu (input: student file)
 yor83.sol (output: solution file)
 A part of yor-f-83.crs (input: course file)
0001 23 (COURSE 0001 HAS 23 STUDENTS) 0002 19 (COURSE 0002 HAS 19 STUDENTS)
0003 67
…
…
…
0180 22
0181 22

A part of yor-f-83.stu (input: student file)
0031 0059 0091 0110 0133 0153 0166 0174 (COURSES OF STUDENT 0001) 0007 0024 0031 0060 0079 0110 0130 0152 (COURSES OF STUDENT 0002)
…
…
…
0040 0053 0074 0101 0103 0118 0179 (COURSES OF STUDENT 0939)
0073 0074 0088 (COURSES OF STUDENT 0940)
0043 0098 0100 0102 0151 0158 (COURSES OF STUDENT 0941)
 A part of yor83.sol (output: solution file)  The solution has 21 timeslots.
118 0
114 0
37 20
…
…
…
HOW TO SOLVE?
 Constructive Heuristics
 Used for building a feasible solution
 Can be viewed as providing an ordering of nodes
 Largest degree, Saturation degree, Largest enrollment, Largest weighted degree, Random ordering
 Perturbative Heuristics
 Used for finding an improved solution in the vicinity or proximity of the current solution
 Kempe-chain Interchange
 Pair-swap Operator
 SWO
 a general approach to optimization: `Squeaky Wheel’ Optimization
 Construct/Analyze/Prioritize cycle
 can be viewed as operating on two search spaces: solutions and prioritizations.
 coupled search

HOW TO SOLVE? (CONSTRUCTIVE HEURISTICS)
 Largest degree
 The node with the largest number of edges (conflicting examinations) is scheduled first.
 Saturation degree
 The well-known Brelaz heuristic (used in DSatur algorithm)
 provides dynamic variable (or node) ordering
gives priority to the node with the least colour available.
 Largest enrollment
 The largest number of students registered for the examinations is scheduled first.
 Largest weighted degree
The examination with the largest number of students whoare involved in the conflict is scheduled first.
 Random ordering
HOW TO SOLVE? (PERTURBATIVE HEURISTICS)
 Kempe-chain Interchange
 A Kempe chain is defined as a connected subgraph that contains v, and that only comprises vertices coloured with colours i and j.
 Kempe (v, c(v), j) or Kempe (v, i, j)
 take a particular Kempe chain and swap the colours of all vertices contained within it.
 Pair swap Operator
 a pair-swap is the simultaneous application of two Kempe-chain interchanges applied to Kempe (v,c(v),c(u)) and Kempe (u,c(u),c(v)).
 Let the Kempe chains KEMPE (u,i, j) and KEMPE (v, j,i) both contain just one vertex each (therefore implying that u and v are nonadjacent.) A pair swap involves swapping the colours of u and v.
HOW TO SOLVE? (SWO)
 The components of SWO
 The constructor: A greedy algorithm is invoked.
 The analyzer:
 Find the trouble spots, i.e., those elements, that, if improved, are likely to improve the objective function score.
 Identify the so-called “trouble makers” and assign blame values to them.
 The prioritizer:
 Use the results of the analysis to generate new priorities that determine the order in which the greedy algorithm constructs the next solution.
 The nodes with higher blame values will be moved forward in the priority sequence while the ones with small blame values will remain in the back of the sequence.
OUTPUT
Benchmark Data Toronto Results (known best solution) My result
(my scheme-1)
Timeslots Penalty Timeslots Penalty
CAR91 35 4.42
CAR92 32 3.74
KFU93 20 12.96
TRE92 23 7.75
YOR83 21 34.84