Mbot at 13:33, 8 November 2011

2011-11-08T13:33:11Z

← Older revision		Revision as of 09:33, 8 November 2011
Line 169:		Line 169:
	<pre>		<pre>
	Problem type appears to be: mip		Problem type appears to be: mip
	Time for symbolic processing: 0.~~16276~~ seconds		Time for symbolic processing: 0.14264 seconds
	Starting numeric solver		Starting numeric solver
	===== * * * =================================================================== * * *		===== * * * =================================================================== * * *
Line 182:		Line 182:

	FuncEv 67		FuncEv 67
	~~CPU time: 0.015600 sec.~~ Elapsed time: 0.006000 sec.		Elapsed time: 0.006000 sec.

	TIMETABLE FOR CLASS 1		TIMETABLE FOR CLASS 1

Mbot at 21:24, 2 November 2011

2011-11-02T21:24:20Z

← Older revision		Revision as of 17:24, 2 November 2011
Line 7:		Line 7:
	Number of 2-hour lessons per teacher and class		Number of 2-hour lessons per teacher and class

			<pre>
	+------------+-----------------+--------------+--------------+		+------------+-----------------+--------------+--------------+
	\|Teacher \|Subject \|Lsns for cls 1\|Lsns for cls 2\|		\|Teacher \|Subject \|Lsns for cls 1\|Lsns for cls 2\|
Line 20:		Line 21:
	\|Mrs Biceps \|Sport \| 0 \| 1 \|		\|Mrs Biceps \|Sport \| 0 \| 1 \|
	+------------+-----------------+--------------+--------------+		+------------+-----------------+--------------+--------------+
			</pre>

	The sport lessons have to take place on Thursday afternoon from 14:00 to 16:00. Furthermore, the first time slot on Monday morning is reserved for supervised homework. Mr Effofecks is absent every Monday morning because he teaches some courses at another college. Mrs Insulin does not work on Wednesday. And finally, to prevent students from getting bored, every class may only have one two-hour lesson per subject on a single day. Write a mathematical program that allows Mr Miller to determine the weekly timetable for the two classes.		The sport lessons have to take place on Thursday afternoon from 14:00 to 16:00. Furthermore, the first time slot on Monday morning is reserved for supervised homework. Mr Effofecks is absent every Monday morning because he teaches some courses at another college. Mrs Insulin does not work on Wednesday. And finally, to prevent students from getting bored, every class may only have one two-hour lesson per subject on a single day. Write a mathematical program that allows Mr Miller to determine the weekly timetable for the two classes.
Line 25:		Line 27:
	==Variables==		==Variables==

			<pre>
	lessons1/2 Number of lessons per subject and class		lessons1/2 Number of lessons per subject and class
	subject Subject indices		subject Subject indices
	slots Possible slots		slots Possible slots
			</pre>

	==References==		==References==

Mbot: Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== Mr. Miller is in charge of establishing the weekly timetable for two classes of..."

2011-11-02T21:01:27Z

Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== Mr. Miller is in charge of establishing the weekly timetable for two classes of..."

New page

{{Part Of Manual|title=the TomSym Manual|link=[[TomSym|TomSym Manual]]}}

==Problem description==

Mr. Miller is in charge of establishing the weekly timetable for two classes of the last year in a college. The two classes have the same teachers, except for mathematics and sport. In the college all lessons have a duration of two hours. Furthermore, all students of the same class attend exactly the same courses. From Monday to Friday, the slots for courses are the following: 8:00–10:00, 10:15–12:15, 14:00–16:00, and 16:15–18:15. The following table lists the number of two-hour lessons that every teacher has to teach the students of the two classes per week.

Number of 2-hour lessons per teacher and class

+------------+-----------------+--------------+--------------+
|Teacher |Subject |Lsns for cls 1|Lsns for cls 2|
+------------+-----------------+--------------+--------------+
|Mr Cheese |English | 1 | 1 |
|Mrs Insulin |Biology | 3 | 3 |
|Mr Map |History-Geography| 2 | 2 |
|Mr Effofecks|Mathematics | 0 | 4 |
|Mrs Derivate|Mathematics | 4 | 0 |
|Mrs Electron|Physics | 3 | 3 |
|Mr Wise |Philosophy | 1 | 1 |
|Mr Muscle |Sport | 1 | 0 |
|Mrs Biceps |Sport | 0 | 1 |
+------------+-----------------+--------------+--------------+

The sport lessons have to take place on Thursday afternoon from 14:00 to 16:00. Furthermore, the first time slot on Monday morning is reserved for supervised homework. Mr Effofecks is absent every Monday morning because he teaches some courses at another college. Mrs Insulin does not work on Wednesday. And finally, to prevent students from getting bored, every class may only have one two-hour lesson per subject on a single day. Write a mathematical program that allows Mr Miller to determine the weekly timetable for the two classes.

==Variables==

lessons1/2 Number of lessons per subject and class
subject Subject indices
slots Possible slots

==References==

Applications of optimization... Gueret, Prins, Seveaux

<source lang="matlab">
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$
% Written Dec 5, 2005. Last modified Apr 11, 2009.
</source>

==Problem setup==

<source lang="matlab">
lessons1 = [ 1 3 2 0 4 3 1 1 0]';
lessons2 = [ 1 3 2 4 0 3 1 0 1]';
subject = [ 1 2 3 4 4 5 6 7 7]';
slots = 4*5;

n1 = length(lessons1); %teachers
n2 = 2; %2
n3 = slots; %slots

t = tomArrayIdx('t',1:n1); % index over all teachers
c = tomArrayIdx('c',1:n2); % index over all classes
l = tomArrayIdx('l',1:n3); % index over all lessons

teach = tom('teach',n1*n2*n3,1,'int');
teach = tomArray(teach,[n1,n2,n3]);

% All variables are binary
bnds1 = {0 <= teach <= 1};

% Sport has to be on thursday afternoon
bnds2 = {1 <= teach(8,1,15), 1 <= teach(9,2,15)};

% No lessons Monday morning
bnds3 = {teach(t,c,1) <= 0};

% Teacher 4 is away on Monday morning
bnds4 = {teach(4,c,2) <= 0};

% Teacher 2 is away on Wednesdays
bnds5 = {teach({'t',2},c,{'l',9:12}) <= 0};

bnds = {bnds1, bnds2, bnds3, bnds4, bnds5};

% Course constraints
con1 = {sum(teach(t,c,l),l) == [lessons1 lessons2]};

% Teacher constraint, one teacher per slot and class
con2 = {sum(teach(t,c,l),t) <= 1};

% Class constraint, one class per slot
con3 = {sum(teach(t,c,l),c) <= 1};

% At most one 2-hour slot of a subject per day
con4 = cell(5,1);
con5 = cell(5,1);
con6 = cell(5,1);
con7 = cell(5,1);

for weekit=1:5
wl = tomArrayIdx('l',(weekit-1)*4+1:weekit*4); % index over slots
%Biology
con4{weekit} = {sum(teach(2,c,wl),wl) <= 1};
%History
con5{weekit} = {sum(teach(3,c,wl),wl) <= 1};
%Math
wt = tomArrayIdx('t',4:5);
con6{weekit} = {sum(teach(wt,c,wl),wl) <= 1};
%Physics
con7{weekit} = {sum(teach(6,c,wl),wl) <= 1};
end

con = {con1, con2, con3, con4, con5, con6, con7};

% Objective
mornaftslots = tomArrayIdx('l',[1 4 5 8 9 12 13 16 17 20]);
objective = sum(vec(teach(t,c,mornaftslots)));

options = struct;
options.solver = 'cplex';
options.name = 'College Time Table';
sol = ezsolve(objective,{bnds, con},[],options);

PriLev = 1;
if PriLev > 0
t_names = ['Cheese '; 'Insulin '; 'Map ';
'Effofecks'; 'Derivate '; 'Electron ';
'Wise '; 'Muscle '; 'Biceps ' ];
s_names = ['English '; 'Biology '; 'Histo-Geo ';
'Mathematics'; 'Physics '; 'Philosophy ';
'Sport ' ];
subject = [ 1 2 3 4 4 5 6 7 7]';
d_names = ['Mon'; 'Tue'; 'Wed'; 'Thu'; 'Fri' ];
l_times = ['0800-1000'; '1015-1215'; '1400-1600'; '1615-1815'; ];
t_nr = length(t_names);
s_nr = 20 ; % number of slots
temp = reshape(sol.teach,t_nr*2,s_nr);
class1 = temp(1:t_nr,:);
class2 = temp(t_nr+1:end,:);
classes= [class1 class2];
for c = 1:2,
this_class = class1;
if c == 2,
this_class = class2;
end
disp(' ')
disp(['TIMETABLE FOR CLASS ' num2str(c)])
counter = 0;
for i = 1:length(d_names),
d_name = d_names(i,:);
disp(['--' d_name '--'])
for j = 1:size(l_times,1),
time = l_times(j,:);
counter = counter + 1;
if sum(this_class(:,counter)) == 1,
teacher = find(this_class(:,counter));
disp([' ' time ' ' s_names(subject(teacher),:) ...
' (' t_names(teacher,:) ')'])
end
end
end
end
end

% MODIFICATION LOG
%
% 051205 med Created
% 060117 per Added documentation
% 060126 per Moved disp to end
% 090412 med Converted to tomSym
</source>

<pre>
Problem type appears to be: mip
Time for symbolic processing: 0.16276 seconds
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31
=====================================================================================
Problem: --- 1: College Time Table f_k 10.000000000000000000
f(x_0) 0.000000000000000000

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

FuncEv 67
CPU time: 0.015600 sec. Elapsed time: 0.006000 sec.

TIMETABLE FOR CLASS 1
--Mon--
1015-1215 English (Cheese )
1400-1600 Biology (Insulin )
--Tue--
1015-1215 Histo-Geo (Map )
1400-1600 Mathematics (Derivate )
1615-1815 Physics (Electron )
--Wed--
0800-1000 Mathematics (Derivate )
1015-1215 Physics (Electron )
1400-1600 Philosophy (Wise )
--Thu--
0800-1000 Biology (Insulin )
1015-1215 Mathematics (Derivate )
1400-1600 Sport (Muscle )
1615-1815 Physics (Electron )
--Fri--
0800-1000 Mathematics (Derivate )
1015-1215 Biology (Insulin )
1400-1600 Histo-Geo (Map )

TIMETABLE FOR CLASS 2
--Mon--
1015-1215 Biology (Insulin )
1400-1600 English (Cheese )
1615-1815 Mathematics (Effofecks)
--Tue--
0800-1000 Histo-Geo (Map )
1015-1215 Biology (Insulin )
1400-1600 Physics (Electron )
--Wed--
0800-1000 Histo-Geo (Map )
1015-1215 Mathematics (Effofecks)
1400-1600 Physics (Electron )
--Thu--
0800-1000 Mathematics (Effofecks)
1015-1215 Biology (Insulin )
1400-1600 Sport (Biceps )
--Fri--
0800-1000 Physics (Electron )
1015-1215 Mathematics (Effofecks)
1400-1600 Philosophy (Wise )

</pre>

TomSym Establishing a College Timetable - Revision history

Mbot at 13:33, 8 November 2011

Mbot at 21:24, 2 November 2011

Mbot: Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== Mr. Miller is in charge of establishing the weekly timetable for two classes of..."