$ontext
A Conference Scheduling Problem
Erwin Kalvelagen (c) 2009
Amsterdam Optimization Modeling Group LLC
From: GagoX
Date: Mar 3, 11:43 am
Subject: scheduling problem optimizing preferences
To: sci.math
Hi everyone,
this is a real life problem and I have no idea even how to start!
I need to organize a small conference:
Np=50 participants (P1 to P50) and Nt=13 talks (T1 to T13).
There are 5 time spots each with 5 rooms available.
T1 will be given 3 times, T2 to T7 will be given 2 times each and T8
to T13 will be given only once. Consequently there are 22 talks. The
constraint is that the repeated talks should not be scheduled in the
same time slot.
Each participant has given his preference to which talk to attend,
from 1st preference to 8th preference. And each participant should
attend 5 talks, one in each time slot.
Problem: What talks should be scheduled in each time slot so to
optimize the preferences?
The optimum solution would be to fulfill that each participand attend
their 5 first preferences.
How is this problem called and is it possible to solve...what should
be the strategy.Or even better, does someone know the solution?
I guess if I knew how to ennumerate each possibility (I do not know),
I could then quantify the fulfilling of the preferences and then take
the best one (brute force) (of course programming the whole
thing)...but I am afraid that there are too many possibilities!
Thaks a lot in advance!!!!
----------------------------------------------------------------------
Notes:
EK: I think there are 21 talks.
In addition require up to 15 attendees per room.
$offtext
set
p 'participants' /p1*p50/
t 'presenter' /t1*t13/
n 'talk number' /n1*n3/
s 'timeslot' /slot1*slot5/
;
set talk(t,n) 'each presenter can give several talks' /
t1.(n1,n2,n3)
(t2*t7).(n1,n2)
(t8*t13).n1
/;
scalar numtalk 'total number of talks';
numtalk=card(talk);
display talk,numtalk;
** actually the count is 21
** abort$(numtalk<>22) "oops, check your sets";
parameter ntalk(t) 'numbers of times a talk is given';
ntalk(t) = sum(talk(t,n),1);
display ntalk;
table preferences(p,t) 'preference = 0..8, 8 is highest preference'
t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13
p1 6 1 4 5 7 3 2 8
p2 4 6 7 8 1 5 3 2
p3 2 3 8 1 4 6 7 5
p4 1 3 5 2 6 8 7 4
p5 3 5 4 2 1 7 6 8 4
p6 4 7 1 8 5 2 3 6 6 3
p7 3 7 2 1 8 6 5 8
p8 7 1 2 4 8 5 4
p9 1 6 7 3 4 2 5 1 8
p10 2 5 3 1 7 6 8 4
p11 7 6 3 5 2 4 5 7
p12 7 1 5 8 2 6 3 8 7
p13 8 1 4 6 2 3 4
p14 2 1 5 3 4 6 4 6
p15 2 3 6 5 8 1 7 7 3 2
p16 5 7 1 3 8 2 8
p17 4 1 8 6 5 3 2
p18 3 1 2 5 7 6 4 2 7 3
p19 6 8 7 5 1 4 4 6 8
p20 5 1 6 8 4 2
p21 1 2 5 3 7 7 1 4
p22 4 1 8 5 3 6 7 3 8
p23 2 5 6 8 3 2 1
p24 1 4 5 7 6 2 3 8 5
p25 2 4 6 5 1 7 5 2
p26 3 5 7 8 4 6 7
p27 2 6 8 1 4 3 7 7
p28 4 1 3 6 7 8 3 8
p29 2 3 4 8 1 5 6 2 1
p30 4 1 3 8 2 6 5 3 7
p31 5 6 2 7 1 4 8 2 1
p32 6 3 4 5 7 8 5
p33 2 4 6 5 1 8 8 4
p34 7 4 3 6 5 8 7
p35 1 7 8 2 6 4 3 4 5
p36 2 5 3 6 1 7 3 6
p37 1 3 5 4 6 2 6
p38 7 3 8 6 2 1 8 1
p39 2 1 4 8 7 5 1 3
p40 5 1 4 8 7 2 3 8 4
p41 4 7 2 3 5 6 6 8 2
p42 2 8 7 5 4 6 6
p43 5 2 7 6 1 3 1 3
p44 4 7 1 3 5 6 4
p45 3 7 1 4 5 8 2 2 1 4
p46 2 5 6 8 4 7 6 4 7
p47 7 5 3 8 2 1 6 8
p48 5 7 8 6 3
p49 2 5 1 3 8
p50 2 5 1 3 4 7
;
variable z 'objective variable';
binary variables
x(t,p,s) 'assign talk/person/slot'
xts(t,s) 'assign talk/slot'
xtp(t,p) 'assign talk/person'
;
* we can relax xts and xtp
xts.prior(t,s) = INF;
xtp.prior(t,p) = INF;
equations
defxts1(t,s) 'calculate xts: all x=0 => xts = 0'
defxts2(t,p,s) 'calculate xts: any x=1 => xts = 1'
defxtp(t,p) 'calculate xtp'
talkcount(t) 'talk can be repeated ntalk times'
slotcount(s) 'up to 5 talks each period'
listen(p,s) 'p can visit only one talk in each time period'
capacity(t,s) 'handle room capacity'
zdef 'objective: maximize preferences'
;
* x(t,p,s)=0 for all p => xts(t,s) = 0
defxts1(t,s).. xts(t,s) =L= sum(p, x(t,p,s));
* any x(t,p,s)=1 => xts(t,s) = 1
defxts2(t,p,s).. xts(t,s) =G= x(t,p,s);
* p visits talk t in any s
defxtp(t,p).. xtp(t,p) =E= sum(s, x(t,p,s));
* each talk happens exactly ntalk times
talkcount(t).. sum(s, xts(t,s)) =E= ntalk(t);
* timeslot can only hold up to 5 talks
slotcount(s).. sum(t, xts(t,s)) =L= 5;
* p can only visit one talk in each time period
listen(p,s).. sum(t,x(t,p,s)) =E= 1;
* we don't allow here (t,p) combinations without preference
xtp.fx(t,p)$(preferences(p,t)=0) = 0;
* objective: maximize
zdef.. z =e= sum((t,p), preferences(p,t) * xtp(t,p));
scalar roomcap 'room capacity' /15/;
equation capacity(t,s) 'handle room capacity';
* room capacity
capacity(t,s).. sum(p, x(t,p,s)) =L= roomcap;
model scheduling /all/;
option mip=cplex;
scheduling.optfile=1;
scheduling.iterlim=10000000;
scheduling.optcr=0;
solve scheduling using mip maximizing z;
$onecho > cplex.opt
threads 4
$offecho