| 1 |
/*** |
| 2 |
!Test |
| 3 |
expected: |
| 4 |
- !Result |
| 5 |
solution: !Solution |
| 6 |
sum_Cs: 295 |
| 7 |
***/ |
| 8 |
|
| 9 |
%-----------------------------------------------------------------------------% |
| 10 |
% Timetabling problem |
| 11 |
% |
| 12 |
% Serge Kruk |
| 13 |
% 04/2007 |
| 14 |
% |
| 15 |
% This is a subset of a real timetabling problem. The job is to assign |
| 16 |
% students to a section of each of the courses they have chosen and assign a |
| 17 |
% timeslot for all sections of all courses so that students can attend their |
| 18 |
% assigned sections. |
| 19 |
%-----------------------------------------------------------------------------% |
| 20 |
|
| 21 |
include "globals.mzn"; |
| 22 |
|
| 23 |
%-----------------------------------------------------------------------------% |
| 24 |
|
| 25 |
int: nS; % Number of students |
| 26 |
int: nC; % Number of course |
| 27 |
int: nSC; % Number of sections per course |
| 28 |
int: nCS; % Number of courses per student |
| 29 |
int: nT; % Number of timeslots |
| 30 |
|
| 31 |
array[1..nS, 1..nCS] of 1..nC: Cs; % Courses of each student |
| 32 |
|
| 33 |
% Decision variables |
| 34 |
array[1..nS, 1..nCS] of var 1..nSC: x; % Sections assigned |
| 35 |
array[1..nC, 1..nSC] of var 1..nT: z; % Times of each section |
| 36 |
|
| 37 |
% All the course-sections of a student must have different times |
| 38 |
constraint |
| 39 |
forall (i in 1..nS) ( |
| 40 |
alldifferent (j in 1..nCS) (z[Cs[i,j], x[i,j]]) |
| 41 |
); |
| 42 |
|
| 43 |
var int: sum_Cs; |
| 44 |
constraint sum_Cs == sum(Cs); |
| 45 |
|
| 46 |
solve satisfy; |
| 47 |
|
| 48 |
%-----------------------------------------------------------------------------% |
| 49 |
|
| 50 |
output [ "timetabling:\n", |
| 51 |
"course sections assigned (1 row per student, 1 col per course):\n" ] |
| 52 |
++ |
| 53 |
[ show(x[i,j]) ++ if j = nCS then "\n" else " " endif |
| 54 |
| i in 1..nS, j in 1..nCS ] |
| 55 |
++ |
| 56 |
[ "times of each section (1 row per course, 1 col per section):\n" ] |
| 57 |
++ |
| 58 |
[ show(z[i,j]) ++ if j = nSC then "\n" else " " endif |
| 59 |
| i in 1..nC, j in 1..nSC ]; |
| 60 |
|
| 61 |
%-----------------------------------------------------------------------------% |
| 62 |
% Small data set. |
| 63 |
|
| 64 |
nS=20; |
| 65 |
nC=6; |
| 66 |
nCS=4; |
| 67 |
nSC=3; |
| 68 |
%nT=5; % To make the problem real |
| 69 |
nT=6; |
| 70 |
|
| 71 |
Cs= [| |
| 72 |
2, 5, 4, 3 | |
| 73 |
4, 6, 3, 1 | |
| 74 |
3, 1, 6, 2 | |
| 75 |
2, 3, 6, 1 | |
| 76 |
6, 4, 3, 1 | |
| 77 |
6, 4, 2, 5 | |
| 78 |
6, 2, 4, 1 | |
| 79 |
6, 1, 4, 3 | |
| 80 |
6, 4, 5, 3 | |
| 81 |
5, 4, 6, 2 | |
| 82 |
4, 2, 1, 5 | |
| 83 |
6, 2, 3, 1 | |
| 84 |
4, 3, 5, 6 | |
| 85 |
6, 3, 2, 4 | |
| 86 |
4, 6, 5, 1 | |
| 87 |
3, 2, 6, 4 | |
| 88 |
3, 6, 5, 1 | |
| 89 |
3, 5, 2, 6 | |
| 90 |
4, 3, 5, 2 | |
| 91 |
5, 4, 6, 2 | |
| 92 |
|]; |
| 93 |
|
| 94 |
%-----------------------------------------------------------------------------% |
| 95 |
%-----------------------------------------------------------------------------% |