$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