$ontext university course time tabling Reference: Edmund K. Burke , Jakub Marecek , Andrew J. Parkes , Hana Rudová Penalising Patterns in Timetables: Novel Integer Programming Formulations Operations Research Proceedings 2007 $offtext sets days /day1*day5/ periods /period1*period20/ rooms /room1*room12/ courses /course1*course52/ curricula /curriculum1*curriculum33/ teachers /teacher1*teacher49/ ; alias (rooms,r),(courses,c),(periods,p),(curricula,cu),(teachers,t),(days,d); parameters RoomHasCapacity(rooms) / room1 312, room2 216, room3 216, room4 216, room5 216 room6 312, room7 105, room8 30, room9 32, room10 50 room11 42, room12 42 / CourseHasStudents(courses) / course1 120, course2 120, course3 120, course4 120, course5 120 course6 120, course7 100, course8 100, course9 80, course10 30 course11 30, course12 30, course13 40, course14 30, course15 30, course16 30, course17 40, course18 30, course19 30, course20 30, course21 30, course22 100, course23 90, course24 90, course25 80, course26 80, course27 100, course28 100, course29 80, course30 80, course31 80, course32 80, course33 80, course34 100, course35 80, course36 80, course37 80, course38 70, course39 70, course40 20, course41 20, course42 20, course43 20, course44 20, course45 20, course46 20, course47 20, course48 20, course49 20, course50 30, course51 20, course52 20 / CourseHasEvents(courses) / course1 5, course2 5, course3 5, course4 5, course5 3, course6 3, course7 5, course8 5, course9 5, course10 5, course11 5, course12 5, course13 5, course14 5, course15 5, course16 5, course17 5, course18 5, course19 3, course20 2, course21 5, course22 5, course23 5, course24 5, course25 5, course26 5, course27 5, course28 5, course29 5, course30 5, course31 5, course32 5, course33 5, course34 5, course35 5, course36 5, course37 5, course38 5, course39 5, course40 3, course41 3, course42 3, course43 3, course44 3, course45 3, course46 3, course47 3, course48 2, course49 2, course50 5, course51 2, course52 2 / CourseHasMindays(courses) / course1 5, course2 5, course3 5, course4 5, course5 3, course6 3, course7 4, course8 4, course9 4, course10 4, course11 4, course12 4, course13 4, course14 4, course15 3, course16 4, course17 4, course18 4, course19 3, course20 1, course21 4, course22 4, course23 4, course24 4, course25 4, course26 4, course27 4, course28 4, course29 4, course30 4, course31 4, course32 4, course33 4, course34 4, course35 4, course36 4, course37 4, course38 4, course39 4, course40 3, course41 3, course42 3, course43 3, course44 2, course45 3, course46 3, course47 3, course48 1, course49 1, course50 4, course51 1, course52 1 / ; sets CourseHasDeprecatedPeriods(courses,periods) / course7 . (period17*period20), course8 . (period1, period17*period20), course9 . (period17*period20), course12 . (period1*period4), course15 . (period1*period4), course16 . (period1*period4), course17 . (period1, period4, period8, period11, period12, period16*period20), course19 . (period17*period20), course21 . (period17*period20), course22 . (period1*period4, period6, period9, period20), course23 . (period1, period17*period20), course25 . (period1, period17*period20), course27 . (period1*period4), course31 . (period17*period20), course34 . (period17*period20), course35 . (period1, period5, period9*period13, period17), course36 . (period9*period12), course38 . (period9, period10, period17*period20), course39 . (period17*period20), course40 . (period1*period8), course41 . (period1, period17*period20), course43 . (period1, period17*period20), course44 . (period1*period6, period17*period20), course45 . (period1*period8), course47 . (period1*period6, period17*period20), course50 . (period17*period20) / CurriculumHasCourses(curricula,courses) / curriculum1 . (course1, course5), curriculum2 . (course1, course5), curriculum3 . (course7, course8), curriculum4 . (course9, course35), curriculum5 . (course13, course15), curriculum6 . (course12, course13), curriculum7 . (course10, course13), curriculum8 . (course11, course13), curriculum9 . (course13, course14), curriculum10 . (course16, course17), curriculum11 . (course17, course21), curriculum12 . (course17, course19, course20), curriculum13 . (course17, course18), curriculum14 . (course2, course6), curriculum15 . (course22, course28), curriculum16 . (course23, course24), curriculum17 . (course25, course26), curriculum18 . (course3, course6), curriculum19 . (course3, course6), curriculum20 . (course27, course28), curriculum21 . (course29, course30), curriculum22 . (course31, course37), curriculum23 . (course32, course33, course45, course47), curriculum24 . (course32, course33), curriculum25 . (course4, course5), curriculum26 . (course7, course34), curriculum27 . (course35, course36), curriculum28 . (course31, course37), curriculum29 . (course38, course39), curriculum30 . (course9, course40, course41, course51), curriculum31 . (course11, course19, course42, course43, course51), curriculum32 . (course24, course44, course48, course51), curriculum33 . (course45, course46, course47, course49, course51) / TeacherHasCourses(teachers,courses) / teacher1 . course47, teacher2 . course5, teacher3 . course24, teacher4 . course31, teacher5 . (course19, course20), teacher6 . course22, teacher7 . course40, teacher8 . course46, teacher9 . (course48, course49), teacher10 . course51, teacher11 . course36, teacher12 . course16, teacher13 . course6, teacher14 . course45, teacher15 . course4, teacher16 . course9, teacher17 . course2, teacher18 . course32, teacher19 . course15, teacher20 . course44, teacher21 . course41, teacher22 . course17, teacher23 . course28, teacher24 . (course1, course3), teacher25 . course7, teacher26 . course33, teacher27 . course42, teacher28 . course18, teacher29 . course52, teacher30 . course26, teacher31 . course29, teacher32 . course39, teacher33 . course34, teacher34 . course35, teacher35 . course13, teacher36 . course38, teacher37 . course10, teacher38 . course12, teacher39 . course50, teacher40 . course21, teacher41 . course37, teacher42 . course11, teacher43 . course30, teacher44 . course27, teacher45 . course14, teacher46 . course43, teacher47 . course25, teacher48 . course23, teacher49 . course8 / HasPeriods(days,periods) / day1 . (period1*period4), day2 . (period5*period8), day3 . (period9*period12), day4 . (period13*period16), day5 . (period17*period20) / k /pat1*pat4/ ; parameter patterns(k,days,periods) 'to prevent patterns like 0-1-0'; patterns(k,HasPeriods(d,p))$(ord(p)=4*(ord(d)-1)+ord(k)-1) = -1; patterns(k,HasPeriods(d,p))$(ord(p)=4*(ord(d)-1)+ord(k)) = 1; patterns(k,HasPeriods(d,p))$(ord(p)=4*(ord(d)-1)+ord(k)+1) = -1; display patterns; binary variables Taught(periods,rooms,courses) CourseSchedule(courses,days) ; variable value; positive variables CourseMinDayViolations(courses) SingletonChecks(curricula,days,k) ; equations obj SessionAllocation(courses) SessionsDistinctRooms(periods,courses) RoomOccupancy(rooms,periods) CurriculumWithoutConflicts(periods,curricula) TeacherWithoutConflicts(periods,teachers) SurveyWorkingDays1(courses,days,periods) SurveyWorkingDays2(courses,days) CountWorkingDays(courses) PenalizePatterns(curricula,k,days) ; obj.. value =e= sum((p,r,c)$(CourseHasStudents(c) > RoomHasCapacity(r)), Taught(p,r,c) * (CourseHasStudents(c) - RoomHasCapacity(r))) + 2 * sum((cu,d,k), SingletonChecks(cu,d,k)) + 5 * sum(c, CourseMinDayViolations(c)); SessionAllocation(c).. sum((r,p), Taught(p,r,c)) =e= CourseHasEvents(c); SessionsDistinctRooms(p,c).. sum(r,Taught(p,r,c)) =l= 1; RoomOccupancy(r,p).. sum(c,Taught(p,r,c)) =l= 1; CurriculumWithoutConflicts(p,cu).. sum((r,CurriculumHasCourses(cu,c)), Taught(p,r,c)) =l= 1; TeacherWithoutConflicts(p,t).. sum((r,TeacherHasCourses(t,c)), Taught(p,r,c)) =l= 1; Taught.fx(p,r,c)$CourseHasDeprecatedPeriods(c,p) = 0; SurveyWorkingDays1(c,HasPeriods(d,p)).. sum(r,Taught(p,r,c)) =l= CourseSchedule(c,d); SurveyWorkingDays2(c,d).. sum((r,HasPeriods(d,p)),Taught(p,r,c)) =g= CourseSchedule(c,d); CountWorkingDays(c).. sum(d, CourseSchedule(c,d)) =g= CourseHasMindays(c) - CourseMinDayViolations(c); PenalizePatterns(cu,k,d).. sum((p,CurriculumHasCourses(cu,c),r), patterns(k,d,p)*Taught(p,r,c)) =l= SingletonChecks(cu,d,k); model m /all/; m.optcr=0; m.holdfixed=1; solve m using mip minimizing value; parameter CurriculumCheck(curricula); CurriculumCheck(cu) = sum((p,r,CurriculumHasCourses(cu,c)),Taught.l(p,r,c)) - sum(CurriculumHasCourses(cu,c),CourseHasEvents(c)); abort$sum(cu, abs(CurriculumCheck(cu))) "check failed: should be all zero",CurriculumCheck;