Timetabling at Purdue University March 24, 2010 Part I: Classical Course Timetabling Course timetabling problems Coordinated decentralized timetabling for: a centrally timetabled large lecture problem almost 900 classes timetabled into 55 rooms with up to 474 seats individually timetabled departmental problems about 70 problems with 10 to 500 classes using departmental laboratory spaces and centrally managed classrooms allocated to departments based on expected class hours a centrally timetabled computer laboratory problem about 200 classes timetabled into 31 rooms with 20 to 45 seats Hana Rudová (FI MU): Timetabling at Purdue University 2/13 GUI with generated timetable Hana Rudová (FI MU): Timetabling at Purdue University 3/13 Problem Classes Meetingsperclass Hoursperclass Classespersubpart Students Classesperstudents Timetabledclassesper student Rooms Roomcapacity (min-max) Frequency(in%) (usedslots) Utilization(in%) Distribution constraintsperclass pu-spr07-llr 803 2.09 2.40 1.25 27881 3.15 0.00 55 40-474 67.77 62.54 0.69 pu-fal07-llr 891 2.07 2.32 1.26 30855 3.23 0.00 55 40-474 74.63 70.40 0.71 pu-spr07-ms 440 2.32 2.43 3.52 11992 1.11 3.13 25 24-51 84.43 76.18 2.74 pu-fal07-ms 525 2.35 2.40 4.45 14331 1.10 3.18 33 24-61 78.30 67.88 2.18 pu-spr07-cs 93 1.63 2.14 1.82 725 2.03 3.19 13 17-61 36.18 30.42 2.83 pu-fal07-cs 174 1.31 1.92 2.72 2002 1.57 4.00 13 22-61 52.19 44.93 2.49 pu-spr07-cfs 214 1.44 2.91 2.21 1610 1.94 2.94 29 10-71 41.52 26.70 1.79 pu-fal07-cfs 201 1.38 2.90 2.14 1936 1.75 3.17 28 10-71 39.73 23.14 3.28 pu-spr07-vpa 249 1.71 3.24 1.64 1836 2.17 2.47 47 10-45 34.34 28.80 2.06 pu-fal07-vpa 290 1.59 2.92 1.72 1747 2.22 2.42 41 10-45 40.39 32.81 1.26 pu-spr07-lab 443 1.25 1.97 4.82 8421 1.14 4.20 36 20-45 52.57 43.27 2.05 pu-fal07-lab 200 1.20 1.81 3.70 4835 1.08 4.49 31 20-45 27.19 23.21 3.29 pu-spr07-c8 2418 1.81 2.45 1.95 29514 4.16 0.00 213 10-474 55.27 56.35 1.76 pu-fal07-c8 2457 1.85 2.40 1.90 32399 4.10 0.00 208 10-474 56.83 61.29 1.74 Hana Rudová (FI MU): Timetabling at Purdue University 4/13 Basic set of constraints Hard Soft constraint constraint Times for class Time pattern x Individual times x x Rooms for class Individual buildings/rooms x x Individual room equipment x x Resource Room x constraints Instructor x Students Conflicts between two classes x Time between classes x x Distribution Time precedences between classes x x constraints Classes placed in similar times x x between classes Same or different meeting days/times/rooms for classes x x Hana Rudová (FI MU): Timetabling at Purdue University 5/13 Model of course structure Instructional Introduction to Actuarial Science MATH 170 Offering STAT 170 Configuration Traditional Computer-Assisted Subpart Lecture Lecture Parent Recitation Recitation Child Laboratory Class Lec1 Lec3 Parent Rec1 Rec2 Rec5 Rec6 Child Lab1 Lab2 Lec2 Lec4 Rec3 Rec4 Rec7 Rec8 Lab3 Lab4 Hana Rudová (FI MU): Timetabling at Purdue University 6/13 Course structure with classes as displayed in user interface Hana Rudová (FI MU): Timetabling at Purdue University 7/13 Weighted constraint satisfaction problem P = (V , D, C, wc, w) set of variables V set of finite domains D each v V takes a value from Dv such that Dv D set of hard and soft constraints C = Ch Cs constraint weight wc as a function associating each soft constraint c Cs with its weight wc (c) assignment weight as a function w associating the value d of each variable v with its weight w(v/d) An assignment for a weighted CSP (V , D, C, wc, w) is a set of pairs v/d such that v V , d Dv , Dv D and each v appears at most once in . assignment complete if each v V appears in , otherwise is called a partial assignment Hana Rudová (FI MU): Timetabling at Purdue University 8/13 Solution of weighted CSP Consider a constraint c C defined on variables X V and denote nc = X and scope(c) = X. Assignment satisfies the constraint c iff xi /di exists in for all variables xi scope(c) and (d1, . . . dnc ) c holds (written c). An assignment is consistent if it satisfies all of the hard constraints c Ch whose scopes have no unassigned variables. A complete assignment which satisfies all hard constraints is called a solution (alternatively a solution is a complete consistent assignment). Hana Rudová (FI MU): Timetabling at Purdue University 9/13 Initial problem Fs = cCs c wc(c) + v/d w(v/d) Fwcsp = ( , Fs) Fwcsp wcsp Fwcsp (( > ) (( = ) (Fs Fs))) An optimal solution of the initial problem is a solution with the minimal Fwcsp. Consider a consistent assignment with Fwcsp = ( , Fs) and a new assignment v/d such that v is not present in . Such an assignment may increase the violation of soft constraints by the value Fs(, v/d) = w(v/d) + cCs vscope(c) c ({v/d}) c wc(c) Hana Rudová (FI MU): Timetabling at Purdue University 10/13 Domain variable Each class is specified by a domain variable representing the desired values for meeting times (weeks and patterns of days the class should meet during the term, start times and duration of all meetings) and rooms. Domain variables will be denoted v = (vw , vp, vs, vd , vr ) and their particular values d = (dw , dp, ds, dd , dr ). Example: Value d = (11110000, MW, 7:30 am, 50, WTHR 200) Domain variable v = (vw , vp, vs, vd , vr ) with (vw , vp, vs, vd ) {(11111111, MWF, 7:30 am, 50), (11111111,MWF, 8:30 am, 50), (11111111, MWF, 9:30 am, 50), (11111111, TTh, 7:30 am, 75), (11111111, TTh, 9:00 am, 75)} and vr {WTHR 200, CL50 224, EE 129, LILY 1105} Hana Rudová (FI MU): Timetabling at Purdue University 11/13 Hard constraints No constraint propagation Consistency of the constraint detected when the last variable is assigned Weak for non-binary constraints However, non-binary constraints can be translated to simpler contraints to check their consistency Example: resource constraint a set of binary constraints prohibiting the placement of each pair of classes into overlapping time periods implementation: array of assigned classes over time Hana Rudová (FI MU): Timetabling at Purdue University 12/13 Soft constraints Soft unary constraints w(v/d) = wtimew((vw , vp, vs, vd )/(dw , dp, ds, dd ))+wroomw(vr /dr ) Student conflicts: soft constraint c between each two classes v1 and v2 with the weight wc(c) = s which is satisfied when the classes v1 and v2 do not overlap Soft distribution constraints with a weight wc(c) Hana Rudová (FI MU): Timetabling at Purdue University 13/13