Science, Irving K. Barber Faculty of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Hamilton, Stephanie
Master of Science - MSc
University of British Columbia
Educational timetabling consists of various scheduling problems, one of which is the examination scheduling problem. This problem requires assigning exams to rooms and timeslots in such a way that no students are required to write two exams at one time. In addition, other restrictions can be imposed so as to improve the quality of the schedule for the participants (i.e., students and faculty). We introduce a new general formulation of a student hardship, which, when minimized, constrains the maximum number of exams students write within a specified length of time. This definition of hardship is incorporated into a two-phase constraint programming model which has a timeslot assignment phase and a room assignment phase. Within the timeslot assignment model, a set of cuts are added to the model to assist in generating solutions that will lead to feasible room assignments by restricting the sizes of exams scheduled in a timeslot. The set of cuts is shown to be a necessary condition for a timeslot assignment solution to have a corresponding room assignment such that the exams can be assigned rooms based on size. If rooms are limited to only hosting one exam in a timeslot, then this set of cuts is shown to be sufficient. The room assignment model then uses such a solution to generate a complete exam schedule. We also provide a unified approach which combines the timeslot and room assignment models. The combined model ensures that a feasible solution is generated, but at a cost of the size and performance. The models presented in this thesis were used to generate the exam schedules for the University of British Columbia’s Okanagan campus in the 2021/2022 academic year. The optimized schedules were well received and exhibited historically low numbers of student hardships. We use these datasets in the experiments of this thesis, as well as international benchmark datasets, to illustrate the effectiveness of the cuts approach versus the unified approach and to position this model in the context of the work done by other researchers in this field.
Constraint Programming Models ForReal-World Examination SchedulingbyStephanie HamiltonB.Sc. Hons., The University of British Columbia, 2020A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)August 2022© Stephanie Hamilton, 2022The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Constraint Programming Models For Real-World Examina-tion Schedulingsubmitted by Stephanie Hamilton in partial fulfilment of the require-ments of the degree of Master of ScienceDr. Donovan Hare, I. K. Barber Faculty of ScienceSupervisorDr. Yong Gao, I. K. Barber Faculty of ScienceSupervisory Committee MemberDr. Shawn Wang, I. K. Barber Faculty of ScienceSupervisory Committee MemberDr. Amir Ardestani-Jaafari, Faculty of ManagementExternal ExamineriiAbstractEducational timetabling consists of various scheduling problems, one ofwhich is the examination scheduling problem. This problem requires as-signing exams to rooms and timeslots in such a way that no students arerequired to write two exams at one time. In addition, other restrictionscan be imposed so as to improve the quality of the schedule for the partici-pants (i.e., students and faculty). We introduce a new general formulationof a student hardship, which, when minimized, constrains the maximumnumber of exams students write within a specified length of time. This defi-nition of hardship is incorporated into a two-phase constraint programmingmodel which has a timeslot assignment phase and a room assignment phase.Within the timeslot assignment model, a set of cuts are added to the modelto assist in generating solutions that will lead to feasible room assignmentsby restricting the sizes of exams scheduled in a timeslot. The set of cutsis shown to be a necessary condition for a timeslot assignment solution tohave a corresponding room assignment such that the exams can be assignedrooms based on size. If rooms are limited to only hosting one exam in atimeslot, then this set of cuts is shown to be sufficient. The room assign-ment model then uses such a solution to generate a complete exam schedule.We also provide a unified approach which combines the timeslot and roomassignment models. The combined model ensures that a feasible solution isgenerated, but at a cost of the size and performance.The models presented in this thesis were used to generate the examschedules for the University of British Columbia’s Okanagan campus inthe 2021/2022 academic year. The optimized schedules were well receivedand exhibited historically low numbers of student hardships. We use thesedatasets in the experiments of this thesis, as well as international bench-mark datasets, to illustrate the effectiveness of the cuts approach versus theunified approach and to position this model in the context of the work doneby other researchers in this field.iiiLay SummaryThe scheduling of exams in rooms and timeslots is an administrativetask required by most universities. The need for a quality schedule im-pacts various university stakeholders, such as students and faculty. Due tothe complexity of this scheduling problem, producing good schedules is atask well-suited for experts in mathematics and computer science. In thisthesis, we propose a constraint programming model to solve the examina-tion scheduling problem that incorporates a student hardship rule, a rulethat limits the number of exams students are scheduled to write within aspecified number of timeslots. We also introduce a partitioned model thatreduces the complexity and provides higher quality solutions under certainscenarios. The work presented in this thesis was used to provide the examschedules for the University of British Columbia (UBCO) in the 2021/2022academic year. These models were also tested using data from UBCO andinternational benchmark datasets.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiGlossary of Notation . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Background . . . . . . . . . . . . . . . . . . . . . . . 42.1 Combinatorial Optimization Techniques . . . . . . . . . . . . 42.1.1 Graph-based Techniques . . . . . . . . . . . . . . . . . 42.1.2 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . 52.1.3 Mathematical Programming . . . . . . . . . . . . . . . 72.1.4 Constraint Programming . . . . . . . . . . . . . . . . 72.2 Comparing Techniques . . . . . . . . . . . . . . . . . . . . . . 132.3 Literature Review of the Exam Scheduling Problem . . . . . 142.4 Global Constraint Definitions . . . . . . . . . . . . . . . . . . 172.5 CP Optimizer . . . . . . . . . . . . . . . . . . . . . . . . . . . 18Chapter 3: Research Project . . . . . . . . . . . . . . . . . . . . 213.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3 Software Components . . . . . . . . . . . . . . . . . . . . . . 22vTABLE OF CONTENTSChapter 4: The General Exam Scheduling Problem . . . . . . 244.1 Elementary Requirements . . . . . . . . . . . . . . . . . . . . 244.2 Requirement Extensions . . . . . . . . . . . . . . . . . . . . . 264.2.1 Measuring Hardships . . . . . . . . . . . . . . . . . . . 29Chapter 5: CP Specification of the General Exam SchedulingProblem . . . . . . . . . . . . . . . . . . . . . . . . . 335.1 Timeslot Assignment Subproblem . . . . . . . . . . . . . . . . 345.1.1 Primary Decision Variables . . . . . . . . . . . . . . . 345.1.2 CP of Elementary Requirements . . . . . . . . . . . . 345.1.3 CP of Extended Requirements . . . . . . . . . . . . . 405.1.4 CP of Multitasking Room Cuts . . . . . . . . . . . . . 425.1.5 CP of Hardship Requirements . . . . . . . . . . . . . . 495.2 Room Assignment Subproblem . . . . . . . . . . . . . . . . . 535.2.1 Primary Decision Variables . . . . . . . . . . . . . . . 545.2.2 CP of Elementary Requirements . . . . . . . . . . . . 545.2.3 CP of Extended Requirements . . . . . . . . . . . . . 545.3 Extending the Timeslot Assignment Subproblem . . . . . . . 575.4 Remarks on Usage of Implementations . . . . . . . . . . . . . 595.5 Search Phases . . . . . . . . . . . . . . . . . . . . . . . . . . . 61Chapter 6: Experiments and Results . . . . . . . . . . . . . . . 636.1 UBCO 2021/2022 Exam Schedules . . . . . . . . . . . . . . . 636.2 Performance Profiles . . . . . . . . . . . . . . . . . . . . . . . 656.3 Room-Cuts versus Room-Packings . . . . . . . . . . . . . . . 676.3.1 UBCO . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.3.2 ITC 2007 . . . . . . . . . . . . . . . . . . . . . . . . . 766.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90Chapter 7: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 96Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106Appendix A: Tables . . . . . . . . . . . . . . . . . . . . . . . . . . 106viList of TablesTable 4.1 Example timeslot sets of B54 for 3-in-27-hours hardships. 31Table 5.1 Exam and room sizes used in Example 5.1. . . . . . . 35Table 5.2 Values and CP variables used for implementing Con-straints 3–4 for Example 5.2. . . . . . . . . . . . . . . 37Table 5.3 Possible schedule of the exams, rooms and timeslotsfrom Example 5.1. . . . . . . . . . . . . . . . . . . . . 38Table 5.4 Summary of the partial assignment of CP variablesused in Example 5.4. . . . . . . . . . . . . . . . . . . 48Table 5.5 Implementation metrics of model options for concur-rent exams. . . . . . . . . . . . . . . . . . . . . . . . . 60Table 6.1 UBCO exam schedule metrics for the 2021/2022 aca-demic year. . . . . . . . . . . . . . . . . . . . . . . . . 65Table 6.2 List of constraints included in the timeslot assignmentmodel for the experiments with the UBCO 2021/2022datasets. . . . . . . . . . . . . . . . . . . . . . . . . . . 69Table 6.3 List of constraints included in the room assignmentmodel for the experiments with the UBCO 2021/2022datasets. . . . . . . . . . . . . . . . . . . . . . . . . . . 70Table 6.4 Implementation metrics of model options for UBCO2021/2022. . . . . . . . . . . . . . . . . . . . . . . . . . 71Table 6.5 UBCO 2021/2022 datasets evaluations. . . . . . . . . . 72Table 6.6 List of constraints included in the timeslot assignmentmodel for the experiments with the ITC 2007 datasets. 78Table 6.7 List of constraints included in the room assignmentmodel for the experiments with the ITC 2007 datasets. 79Table 6.8 Implementation metrics of model options for ITC 2007. 80Table 6.9 ITC 2007 datasets evaluations. . . . . . . . . . . . . . 81Table 6.10 Accumulating room slack example. . . . . . . . . . . . 93Table A.1 Data properties for the UBCO 2021/2022 data sets. . 107Table A.2 Data properties for the ITC 2007 benchmark datasets. 108viiList of FiguresFigure 2.1 GCC filtering algorithm network. . . . . . . . . . . . 11Figure 4.1 An example of the 3-in-27-hours rule. . . . . . . . . . 32Figure 6.1 Performance profile on the UBCO 2021/2022 Term 1Version 1 dataset. . . . . . . . . . . . . . . . . . . . . 74Figure 6.2 Performance profile on the UBCO 2021/2022 Term 1Version 2 dataset. . . . . . . . . . . . . . . . . . . . . 74Figure 6.3 Performance profile on the UBCO 2021/2022 Term 2Version 1 dataset. . . . . . . . . . . . . . . . . . . . . 75Figure 6.4 Performance Profile on the UBCO 2021/2022 Term 2Version 2 dataset. . . . . . . . . . . . . . . . . . . . . 75Figure 6.5 Performance profile on ITC 2007 Dataset 3. . . . . . 83Figure 6.6 Performance profile on ITC 2007 Dataset 4. . . . . . 83Figure 6.7 Performance profile on ITC 2007 Dataset 5. . . . . . 84Figure 6.8 Performance profile on ITC 2007 Dataset 6. . . . . . 84Figure 6.9 Performance profile on ITC 2007 Dataset 7. . . . . . 85Figure 6.10 Performance profile on ITC 2007 Dataset 8. . . . . . 85Figure 6.11 Performance profile on ITC 2007 Dataset 9. . . . . . 86Figure 6.12 Performance profile on ITC 2007 Dataset 10. . . . . . 86Figure 6.13 Performance profile on ITC 2007 Dataset 11. . . . . . 87Figure 6.14 Performance profile on ITC 2007 Dataset 1. . . . . . 89Figure 6.15 Performance profile on ITC 2007 Dataset 2. . . . . . 89Figure 6.16 Performance profile on ITC 2007 Dataset 12. . . . . . 90viiiGlossary of NotationZ+ the set of nonnegative integers. 24Z++ the set of positive integers. 24[k1, k2] the integer interval {k1, . . . , k2}. 24[k2] the integer interval {1, . . . , k2}. 24ℓ([a, b]) b − a, the length of an integer interval [a, b].24r(i, j] the integer interval [ri +1, rj ] for 0 ≤ i < j ≤q, where r0, . . . , rq is a finite monotonicallyincreasing sequence of integers. 24T the finite set of pairwise disjoint integer inter-vals {[s1, f1], . . . , [sm, fm]}. 24m the number of timeslots, |T |. 24P the set of persons writing exams. 24E the set of exams, which are subsets of P . 24ε the function ε : E → Z++ representing theexam sizes. 24δ the function δ : E → Z++ representing theexam durations. 24R the set of rooms. 24σ the function σ : T×R→ Z+, representing thetemporal room sizes. 24τ the function τ : E → T representing thetimeslot assignment of an exam. This defini-tion only applies until the end of Chapter 5.The symbol is then reused to define perfor-mance profiles. 24ρ the function ρ : E→ R representing the roomassignment of an exam. This definition onlyapplies until the end of Chapter 5. The sym-bol is then reused to define performance pro-files. 24ixGlossary of Notationσk(R) the temporal room size of room R for timeslotk. 25T (R) {[sk, fk] ∈ T : σk(R) > 0}, the effective times-lots of room R. 25E(p) {E ∈ E : p ∈ E}, p ∈ P , the intersectingsubset of exams that p writes. 25B∗ the maximal interseting subsets of timeslots.25CR,k {E ∈ E : ρ(E) = R, τ(E) = [sk, fk]}, the con-current exams in room R during timeslot k.27γk(R) the maximum number of concurrent exams al-lowed to be scheduled in roomR during times-lot k. 27∆k(R) {δ(E) : τ(E) = [sk, fk], ρ(E) = R}, the setof durations of exams scheduled in room Rduring timeslot k. If no room is specified, thisis the set of all durations of exams assignedto any room during timeslot k. 28E>c {E ∈ E : ε(E) > c}, the set of exams of sizelarger than c. 28E>c,k {E ∈ E>c : τ(E) = [sk, fk]}, the set of exams ofsize larger than c assigned to timeslot [sk, fk].28Ek {E ∈ E : τ(E) = [sk, fk]}, the set of examsassigned to timeslot [sk, fk]. 29Bd the subsets of timeslots of T that are withind time units of each other as measured by thedifference of the latest finish time with theearliest start time of its members. 29Wp,B {E ∈ E(p) : τ(E) ∈ B}, the exams written byperson p during a time period B ∈ Bd. 29Hw,d {(p,B) : p ∈ P,B ∈ Bd, |Wp,B| ≥ w}, the setof (w, d)-hardships (of τ). 29tE a CP integer-valued decision variable whosedomain is the set of indices of the timeslots,[m] = {1, . . . ,m}, where if tE is bound to k,then τ(E) = [sk, fk]. 34xGlossary of NotationTD {tE : E ∈ D} the set of constraint program-ming integer-valued decision variables for ex-ams in D. 34R>c,k {R ∈ R : σk(R) > c}, the number of roomslarger than c during timeslot k. 36qk the number of distinct room sizes for times-lot k. 36ri a room size in the (non-multi-)set of roomsizes {σk(R) : R ∈ R>0,k} = {r1, . . . , rq} wherethe ri’s are labeled so that they are strictlyincreasing and r0 = 0. 36γ>j,k the maximum number of concurrent exams ofsize greater than rj that can be scheduled dur-ing timeslot [sk, fk]. 43E=u {E ∈ E : ε(E) = u}, the set of exams of sizeu. 43U {ε(E) : E ∈ E}, the set of exam sizes. 43πk(ri, u) the maximum number of exams of size u thatcan be concurrent in rooms of size ri duringthe timeslot k. 44u▽i the minimum size of the exams of E>ri−1 \ E>ri .45u△i the maximum size of the exams of E>ri−1 \E>ri .49hD,d the CP variable that equals | ∩ D| if theseexams are scheduled within d time units ofeach other, where D ⊆ E. 50hw,d a CP variable representing |Hw,d|. 50dd a CP variable representing the total numberof day d-hardships. 53v the number of rooms. 54rE a CP integer-valued decision variable whosedomain is the set of indicies of the rooms, [v],such that if rE is bound to i, then ρk(E) = Ri.54RD {rE : E ∈ D}, where D ⊆ Ek is any subset ofexams. 54v∗ The unique virtual room index used in theextended timeslot assignment subproblem. 57xiGlossary of Notationρs(τ) a performance profile, that is, for a perfor-mance metric r, the cumulative distributionfunction fiven by 1nI |{i ∈ I : ri,s ≤ τ}|. 66xiiAcknowledgementsFirst and foremost I would like to thank my supervisor, Dr. DonovanHare, for being my mentor throughout my years at UBCO. Your enthusiasm,expertise, and humour have made this a one-of-a-kind experience. I willforever be grateful for the knowledge you passed down to me, including thedad jokes.Second, thank you to my committee members, Dr. Amir Ardestani-Jaafari, Dr. Yong Gao, and Dr. Shawn Wang, for their feedback and guid-ance. As well, thank you Dr. Michael Treschow for chairing my defense.I would also like to send my sincere thanks to Dr. Ananya MukherjeeReed, who provided endless support to the DOPT Team during our researchproject. The project’s success would not have been possible without you.Lastly, I am grateful to UBCO and NSERC for funding my studies.xiiiChapter 1IntroductionTimetabling was once a manual process, but the efficient timetabling ofactivities and events has become an increasingly complicated matter due togrowth in many sectors of day-to-day life, such as universities, sports leagues,and hospitals. Several factors can affect the quality of a timetable, includingthe proximity of locations and the frequency of events. Considering allfactors is too much for an individual, or even a team of schedulers, to handlewithout the help of computers. However, while computation has improvedand scheduling can now be done with the aid of a computer, timetabling isstill a difficult task even for experts in computer science and mathematicsbecause of the size and complexity of these timetables and the underlyingtheoretical challenges.The focus of this thesis is the examination scheduling problem (ESP).This problem is concerned with the assignment of exams to timeslots androoms with the primary requirement that no student is to write multipleexams at a given time, along with several other restrictions that can beincluded (e.g., exams must be scheduled in a room of large enough capacityto seat all examinees). In general, this problem can be considered a resourceallocation problem, where the timeslots and rooms are the resources, and theexams are the entities requiring resources. The ESP is NP-complete, that is,there is no known way to find a solution in polynomial time (i.e., a reasonableamount of time), though a solution can be quickly verified.1 To get an ideaof why this is the case, imagine scheduling 500 exams in 50 timeslots and50 rooms. This example is reasonably small for today’s universities, andwould still lead to 502·500 possible combinations of assignments of exams totimeslots and rooms. Thus, the manual scheduling of exams is an extremelydifficult task for administrators, especially if they are trying to improve thequality of a schedule instead of merely producing a feasible one.The complexity of this problem has attracted researchers’ attention fordecades. Today, the most popular techniques used to tackle this probleminclude metaheuristics, mathematical programming (e.g., mixed integer pro-1Other NP-complete timetabling problems include sports scheduling and nurse roster-ing.1gramming), and constraint-based methods (e.g., constraint programming).There exist several benchmark datasets for examination scheduling, includ-ing the Toronto datasets (which do not include room assignments), the Uni-versity of Nottingham datasets, and the International Timetabling Compe-tition (ITC) 2007 datasets.2 In this work we will consider new real-worlddata and the ITC 2007 datasets, which are the most recent benchmarks thatare publicly available.The University of British Columbia’s Okanagan Campus (UBCO) hasparticular scheduling requirements that are not encapsulated by the modelsalready presented in the literature. Furthermore, there have been recentchanges to the UBCO Senate policies on examinations, which required achange to the current examination scheduling practices used by the univer-sity. Thus, a research project was conducted to produce a system comprisedof a constraint programming model and a timetable viewer to schedule theexaminations for the most recent academic year, 2021/2022. This thesisserves to explain the constraint programming model used in the researchproject.Constraint programming (CP), a paradigm for solving combinatorialoptimization problems, incorporates various mathematical techniques, in-cluding algorithms based on graph theory and network flow theory. Thisparadigm is especially useful for scheduling problems that are highly struc-tured because they can take advantage of the strengths of constraint pro-gramming. We use the IBM ILOG CP Optimizer software library and CPengine to build our model and find solutions.The first significant contribution of this thesis is a new formulation of astudent hardship requirement and the corresponding CP implementation. Astudent hardship is an undesirable feature in an examination schedule. Com-mon examples include a student having to write two exams consecutively oron the same day. We generalize this notion to include other occurrences ofstudents having to write multiple exams within a specified length of time(e.g., three exams in 27 hours).The second important contribution is a partitioning of the exam schedul-ing problem into two components: a timeslot assignment subproblem and aroom assignment subproblem. While splitting the exam scheduling probleminto phases has been explored by other researchers [9, 34], we propose a newmethod. To do so, we provide a set of cuts, called room-cuts, that are addedto the timeslot assignment subproblem. The room-cuts provide necessary(and under certain scenarios, sufficient) conditions for the timeslot assign-2See [1] for information on the first two datasets.2ment subproblem to generate solutions where each exam can be assigned aroom of appropriate size (i.e., where the room capacity is not exceeded bythe number of examinees scheduled in that room). The room assignmentsubproblem, in contrast, is rather simple in comparison since the problemsize is much smaller than the timeslot assignment subproblem. Thus, oncea timeslot assignment is provided, finding a valid room assignment for eachtimeslot is often trivial. We also introduce a coupled model, where thetimeslot and room subproblems are fused into one. This unified approachremoves the need for the room-cuts by extending the timeslot assignmentsubproblem, but in doing so, increases the complexity of the problem. Theprimary analysis of this work will explore comparing these two approaches.These two model options provide schedulers flexibility to tune the modelbased on the datasets in question. Furthermore, they serve to show thatCP is an efficient method for solving the ESP, especially for larger datasetswith simple room assignments, which is where the two-phase model withroom-cuts excels.In Chapter 2, we provide background information on several combinato-rial optimization techniques to provide more context for the literature reviewof the ESP that follows. In doing so, we provide a detailed explanation ofCP, the modeling paradigm of choice for this thesis. In Chapter 3, we willdiscuss the exam scheduling research project. In Chapter 4, we provide ageneric specification of the ESP to serve as a foundation for the constraintprogramming implementations of the ESP, which are explained in Chap-ter 5.3 Chapter 5 will also discuss the extended version of the timeslotassignment subproblem that allows for the model to be unified and solvedin a single phase. Chapter 6 will detail the results from our experimentstesting the decoupled and the coupled approaches, as well as the productionschedule used at UBCO in the 2021/2022 academic year. Lastly, Chapter 7will provide a conclusion.3These two chapters are comprised of an expanded version of our paper that wasaccepted for publication in the Proceedings of the 13th International Conference on thePractice and Theory of Automated Timetabling [44].3Chapter 2BackgroundIn this chapter we will provide background on techniques used in combi-natorial optimization, a literature review of the methods used in examinationscheduling, and a thorough overview of constraint programming, includingdefinitions of global constraints.2.1 Combinatorial Optimization TechniquesThe ESP, like other combinatorial optimization problems, can be ap-proached in a variety of ways. The techniques used to solve the ESP differin terms of the underlying structure used to express the constraints andthe search strategies used to explore the solution space. The solution spacerefers to the set of all feasible solutions, where a solution is comprised ofassignments to all decision variables and an objective function value that isused to measure the quality of the solution.The most common approaches used to solve the ESP can be dividedinto four main categories: graph-based methods, metaheuristics, mathemat-ical programming, and constraint-based methods. We will provide a briefoverview of the first three approaches for comparison purposes. For the lastapproach, we will specifically focus on constraint programming since that isthe method used in this thesis.Note that there are many other methods that do not necessarily fallinto the above categories, such as hyper-heuristics, multi-criteria techniques,decomposition/clustering techniques, etc. These strategies and their successsolving the ESP are explained more thoroughly in a review by Qu et al.[62].2.1.1 Graph-based TechniquesConsider a graph G with a set of vertices, V , representing the exams,and a set of weighted edges, E, such that if two exams have students incommon, the corresponding vertices will be connected by an edge, wherethe weight of the edge is the number of students writing both exams. Acolouring of G then represents an assignment of exams to timeslots, where42.1. COMBINATORIAL OPTIMIZATION TECHNIQUESthe colour of the vertex represents the timeslot assigned to the exam. Ifthe colouring is valid, then any adjacent vertices will have different colours,meaning the corresponding exams will be assigned distinct timeslots, andthus no students will be writing two exams simultaneously.Graph-based timetabling techniques are constructive and use a varietyof ordering strategies to decide which exams to schedule first [62]. Thesetechniques played an important role in the early timetabling literature dueto their straightforward implementations and the relatively small amountof time required to find a good solution [20].4 However, these approachescan only model simple ESPs because a colouring only corresponds to a con-flict free schedule. Therefore these models lack the flexibility to incorporatemore complicated constraints. Thus, graph-based techniques are now pri-marily used in conjunction with more advanced methods like mathematicalprogramming or metaheuristics, which will be discussed in Section 2.3.2.1.2 MetaheuristicsA metaheuristic is a framework used to guide subordinate heuristicsby intelligently exploiting the solution space. Metaheuristics are problem-independent, that is, they are not reliant on the decision variables or con-straints used to express the problem [36]. Therefore they can be applied toa large variety of combinatorial optimization problems.The underlying algorithms in a metaheuristic navigate the solution spaceby either manipulating a current solution or a current set of solutions. Con-sequently, metaheuristics are approximate methods, meaning they are notguaranteed to find the optimal solution. However, they are designed so thatgood solutions are found quickly, making them a common method used tosolve complex optimization problems that need good, but not necessarilyoptimal, solutions in a short amount of time.The types of metaheuristics are diverse, but for our purposes they can beclassified into two categories: single-solution-based and population-based.Single-solution-based Single-solution-based metaheuristics start from aninitial solution and a set of candidate (neighbouring) solutions, which is pro-4Note that the graph-colouring problem is NP-hard. However, there is evidence thatgraphs representing timetabling problems have a much simpler structure than that ofthe general case, and therefore may be easier to colour. Furthermore, for timetablingproblems, it is not necessary to find the chromatic number of the graph, and the numberof periods could be larger than this chromatic number, which makes it easier to find avalid colouring.52.1. COMBINATORIAL OPTIMIZATION TECHNIQUESduced in a generation phase. Then in a replacement phase one solution fromthe set of candidates is chosen to replace the initial solution. This processcontinues until the current solution is deemed good enough. The neigh-bourhood of solutions consists of those which are within a specified numberof “movement” operations (e.g., swapping the assignment of two variables)from the current solution.Metaheuristics that fall into this category include Tabu Search and Sim-ulated Annealing [6, 46]. In Tabu Search, short term memory is used toremember not to revisit previous solutions. Furthermore the neighbourhoodis searched deterministically, and non-improving solutions are accepted toescape local optima. In Simulated Annealing, a random neighbour (i.e., so-lution) is selected and the cost of selecting that neighbour is computed. Ifthe cost is below the current objective, then the solution is adopted, other-wise a probability measure is used to determine if the new (worse) solutionwill be taken. As in Tabu Search, this helps the solver escape local optima.A cooling parameter is used so that as the search goes on, the solver will beless likely to adopt bad solutions, essentially merging to one local optima.Population-based As indicated by the name, population-based meta-heuristics work from an initial population (i.e., set) of solutions rather thana single solution. The solution population is then manipulated iterativelyto produce a new population of solutions. In a replacement phase, the nextsolution population is chosen to be either the generated solution populationor the current solution population. This process continues until stoppingcriteria are met.These algorithms are often modeled after processes in nature. Some ex-amples include Genetic and Memetic Algorithms [54]. Genetic Algorithmsare based on the theory of evolution. Each solution is called a “chromosome”and each decision variable is called a “gene”. From the current population,a selection criterion is applied to choose parent solutions who will generatea set of offspring, which form the next generation of solutions. The selectioncriterion is based on the fitness (i.e., objective function value) correspondingto each parent. Memetic Algorithms are a hybrid approach, usually inte-grating a population-based metaheuristic, such as the Genetic Algorithm,and a local search procedure (e.g., hill-climbing) [36].62.1. COMBINATORIAL OPTIMIZATION TECHNIQUES2.1.3 Mathematical ProgrammingMathematical programming uses mathematical processes to find a bestsolution and is an exact5 technique. Linear Programming (LP) and MixedInteger Programming (MIP) fall into this category. A MIP is similar to anLP in that there are decision variables subject to linear constraints, whichare expressed either with equalities or inequalities, and a linear objectivefunction. The difference is in the type of decision variables used. In an LP,the decision variables are all real-valued, while in a MIP, the decision vari-ables are also allowed to be integer-valued. This results in a discrete ratherthan a continuous solution space, making MIPs non-convex. Additionally,MIPs are classified as NP-complete, unlike LPs. Modeling using MIPs re-mains a popular method for solving combinatorial optimization problems,and scheduling problems in particular [8, 10, 22, 32, 49].2.1.4 Constraint ProgrammingConstraint programming is another paradigm for solving combinatorialoptimization problems, specifically Constraint Satisfaction Problems (CSPs)or Constraint Satisfaction Optimization Problems (CSOPs). A finite CSPP = (X ,D, C) is a set of decision variables X = {x1,x2, . . . ,xn}, a set offinite domains D = {D1, D2, . . . , Dn}, where Di is the domain of variablexi, 1 ≤ i ≤ n, and a set of constraints C acting on the variables in X . ACSOP has an additional expression involving variables in X , which is tobe maximized or minimized. A solution to P is an assignment of valuesfrom each Di to xi such that the constraints in C are satisfied. A commonexample of a CSP is the problem of assigning tasks to a group of people,whereas a common example of a CSOP involves scheduling jobs where thespan of the timeline is minimized.CSPs, in general, are known to be NP-complete problems [27]. Due tothe prevalence and difficulty of CSP problems, researchers began to takean interest in constraint satisfaction and propagation in the 1960’s, thoughthe ideas underlying these problems predate this period. As explained byFreuder and Mackworth, the investigation into constraint satisfaction bythe computer science, artificial intelligence, and operations research com-munities developed in two streams: the language stream and the algorithmstream [33]. In the language stream, practitioners and researchers tried toarticulate applications of CSPs using computer languages. On the other5Exact techniques are guaranteed to find the optimal solution if given enough comput-ing time.72.1. COMBINATORIAL OPTIMIZATION TECHNIQUEShand, researchers in the algorithm stream developed methods for searchand constraint propagation to improve the process of finding solutions forCSPs. After 30 years, in the early 1990’s these two streams were fused intothe modern day field of constraint programming. At this time the Interna-tional Conference on the Principle and Practices of Constraint Programmingwas founded and the journal Constraints was established. The goal of theconference and journal is to provide a common avenue where the diversecommunity interested in constraint programming theory and applicationscan exchange ideas. Since then, CP has grown in popularity due to develop-ments in constraint structure, search algorithms, and modeling and solvingsystems (see Section 2.5). CP has been used in many applications suchas machine scheduling, the traveling salesman problem and its variations,hospital scheduling, and job shop scheduling [24, 38, 41, 45].In [48], John Hooker describes a high level framework to solve optimiza-tion problems using CP . He explains that the key to solving these problemsis efficiently using the structure of the problem to motivate the search for theoptimal solution. To do so there are three main strategies: search, inferenceand relaxation. Search involves the enumeration of all possible solutions. In-ference is the process of adding constraints and learning from the structureof the problem in order to direct the search towards the optimal solution.Relaxation includes the exploitation of a simpler problem to deduce boundson the objective function of the original problem, since the solution spaceof the simpler problem will encompass that of the original. Thus searchexplores the solution space, and inference and relaxation are the techniquesused to strategically navigate this space to quickly find good, and optimal,solutions. We will now explain these strategies in detail, as described byHooker, and how they may be implemented in CP.Search The solution space for optimization problems consists of a vastcombination of assignments. If a problem cannot be initially solved throughinference techniques, then a search tree is explored to find feasible and op-timal solutions. At each node in the search tree a procedure is applied todirect the search towards nodes that are more likely to contain the optimalsolution.In CP, backtracking is the common method for navigating the searchtree. At each node of the tree, a variable xi ∈ X and a value vi ∈ Diare chosen and two branches are created. One branch has the restrictionxi = vi imposed on the current state of the problem, while the other branchhas the restriction xi ̸= vi. Domain reduction and constraint propagation82.1. COMBINATORIAL OPTIMIZATION TECHNIQUESoccur (the inference techniques), triggering the filtering algorithms of theconstraints. If a solution is not found (i.e., not all variables are assigned fea-sible values), then this process continues, branching and adding restrictionson the domains of variables, while keeping the previously added restrictionsfrom nodes earlier in the tree. This continues until either a solution is found(i.e., all variables are bound to a single value), or the problem of the currentbranch is deemed infeasible.If the domain of a variable becomes empty, then an infeasibility is foundand the search moves backwards (i.e., backtracks) to an earlier node wherethere is an unsearched branch. If the infeasibility was found without allvariables being assigned values, then this can result in the search tree beingpruned. Pruning occurs when there is no solution with the combinations ofassignments from the nodes of the current branch in the tree, and thereforethere is no longer a need to continue searching along this branch. Theearlier in a branch that this occurs, the better, because then less time willbe dedicated to searching a branch that will not lead to a feasible solution.Hooker describes the above method as branch-directed search, where ateach node a restriction is added to the problem by restricting the domain ofa particular variable. Another type of search is the more general constraint-directed search, where at each node a nogood constraint is added to theproblem, which can be found using the solutions of an inference dual of therestricted problem. This nogood is then used to direct the search. Logic-based Benders decomposition is an example of this search method, which ispopularly used in MIPs (e.g., classical Benders decomposition), but can begeneralized to apply to CP as well.There are various ways to select nodes to search on in the search tree,such as depth-first search and breadth-first search. Additionally, the orderof choosing which variables and which values to restrict at each branch canhave a large effect on the size of the search tree. This can be controlledusing search phases which can be specified within a CP solver. Search typesand search phases will be discussed in more detail in Sections 2.5 and 5.5,respectively.Inference Inference techniques are used to reduce the size of a search treeby finding implicit constraints and reducing the domains of variables. In CP,inference takes the form of domain reduction and constraint propagation.The goal of domain reduction is to achieve domain consistency [48, p. 226](e.g., arc-consistency for binary constraints, and path-consistency for themore general situation), that is, to remove all values from a variable’s domain92.1. COMBINATORIAL OPTIMIZATION TECHNIQUESwhere there is no feasible solution assigning any of those values to thatvariable. In other words, we derive a new problem P ′ from P by reducingeachDi ∈ D to only include the values that are consistent with the constraintset (i.e., that exist in a feasible solution to P). As a simple example, if thereis a constraint stating that x1 ≤ 10, then all values greater than 10 can beremoved from D1. The new domain, D′1, would then be consistent with thisconstraint. Note that solutions to P ′ are still solutions to P.A global constraint is one in which there is an implicit structure andrelationship between the variables involved in the constraint. Some exam-ples include All Different, Global Cardinality Constraint (GCC), and binpacking (see Section 2.4 for definitions). Each global constraint in CP hasa filtering algorithm associated with it. When the domain of a variable inthe constraint changes, the filtering algorithm is triggered and the domainsof the variables are further reduced to try to achieve domain consistency.This leads to constraint propagation by triggering other constraints involv-ing these variables to apply their filtering algorithms (also called constraintpropagators). Note that for some constraints, such as bin packing, the prob-lem of achieving domain consistency is NP-hard. Example 2.1 summarizesthe filtering algorithm used for the Global Cardinality Constraint (GCC).Example 2.1 (Filtering Algorithm of Global Cardinality Constraint).The GCC is a generalization of the All Different constraint. Given aset of variables and a set of values, the GCC counts the cardinality of theassignments of each value, that is, the number of variables assigned thevalue. The cardinality of a value is itself a CP variable since it is a functionof a CP variable, and therefore it can be used in other constraints.A filtering algorithm for the GCC, described in what follows, is basedon finding the maximum flow in a directed network [29, 43, 65].We construct a network flow problem using a directed graph G. LetX be the set of vertices in G that represent the variables involved in theconstraint, and Y be the set of vertices in G that represent the possiblevalues of these variables. Let s and t be the source and sink vertices of G,respectively. There is one directed arc from s to each vertex in Y and therestrictions on the cardinality of the values indicate the upper and lowerbounds on the arc capacities.6 There is also one directed arc from eachvertex in X to t and each of these arcs capacities has a lower bound of 0and an upper bound of 1. Lastly, for each x ∈ X, if y ∈ Y is in the domainof the variable corresponding to x, then there is an arc (y, x) with capacitybetween 0 and 1.6The capacity of the arc restricts how much flow can be sent along the arc.102.1. COMBINATORIAL OPTIMIZATION TECHNIQUESA maximum (feasible) flow that saturates all of the vertices in X cor-responds to an assignment of values to variables where the cardinalities ofeach value are met (because of the restrictions on each arc (s, v)). Thus, ifthere is no possible maximum (s, t)-flow where flow is sent from a particularvariable to a particular value, then there is no assignment that satisfies theGCC where that value is assigned to that variable. Therefore the value canbe removed from the variable’s domain and the corresponding arc can beremoved from G.Figure 2.1 shows an example where there are four variables, x1 to x4,and four possible values that can be assigned to these variables. The greenarrows represent the arcs having positive flow. This is a maximum feasibleflow since all arcs into t have flow and capacity of 1. The flow correspondsto a possible assignment of values to variables (x1 and x4 are assigned to 3,and x2 and x3 are assigned to 2). Figure 2.1: An example of a network used for the Global CardinalityConstraint’s filtering algorithm. The labels on each arc (i, j) correspondto the lower and upper capacity of the arc, (li,j , ui,j), and the flow, f(i, j),along the arc.At each node in the search tree, restricting a variable’s domain trig-gers the constraints’ filtering algorithms, reducing the domains of variables,leading to more constraint propagation and filtering. CP efficiency can begreatly improved through the use of global constraints because their filter-ing algorithms can result in greater domain reduction by exploiting structurebetween groups of variables. In contrast, a collection of logically equivalentsimple or binary constraints may result in no domain reduction at all, leav-ing more work for the search. On the other hand, effective global constraints112.1. COMBINATORIAL OPTIMIZATION TECHNIQUEShave domain filtering with strong “propagative power” built upon combina-torial optimization underpinnings. This is what makes CP a good choice formany combinatorial optimization problems.When modeling a CSP or CSOP using CP, there are various ways tochange the amount of inference being performed by constraint propagators(i.e., the filtering algorithms associated with global constraints). There is atrade-off when making this decision between search time and propagationtime that needs to be considered. To demonstrate this complex dynamic,Derval et al. explore three filtering algorithms for the bin packing with car-dinality constraint7 [29, 42], each of which vary in terms of filtering time.Generally, when a constraint’s propagator has more filtering time, at eachiteration of the propagator’s filtering algorithm, more values can potentiallybe removed from the variables’ domains. This leads to more pruning of thesearch tree which results in the propagator being called fewer times. Hencethe overall size of the search tree will be smaller. On the other hand, ifa domain filtering algorithm is computationally heavy, the time taken toreduce each variable’s domain will be greater, consequently leading to moretime being required to find a solution. Hence, a smaller search tree does notnecessarily correspond to a more efficient overall process of finding a feasiblesolution since at each node of the search tree there could be many opera-tions performed. In Derval et al.’s case, the algorithm that performed bestin terms of domain reduction would likely not be used in practice becauseit took more overall time to solve the problem instances. Thus, discoveringeffective filtering algorithms is still an important area in research.Relaxation CP is best known for its effective inference techniques, whereasMIP excels in the strategy of relaxation. Relaxation is the process of relax-ing, or simplifying, constraints to allow for a larger solution space to beexplored. Since all solutions to the original problem are contained in thesolution space of the relaxed problem, the solutions to the relaxed problemserve as a bound to the original: if the solution to the less restricted prob-lem is optimal, then the solution to the original can be no better than thesolution to the relaxation.As mentioned earlier, MIPs have a natural relaxation by simply removingthe integer restrictions on the decision variables to get an LP. The relaxedproblem can then be solved using LP techniques to provide a bound on7The bin packing with cardinality constraint combines the bin packing constraint andthe GCC so that the number of items being assigned to each bin can be restricted. Sec-tion 2.4 will provide definitions for the CP versions of both of these constraints.122.2. COMPARING TECHNIQUESthe objective function of the MIP. This strategy is used in the branch-and-bound procedure, where at each node of the search tree a linear constraint(i.e., a bound on a fractional decision variable) is added to the model todivide the search space. The result is two relaxed problems that can thenbe solved, each of which are more restricted than the previous. If a solutionto either of the two LPs is still fractional, then the search along that branchwill continue, otherwise a solution to the MIP has been found. Because ofthe added bounds on the variables, solutions found at later nodes of thesearch tree branch cannot be better than the solutions at earlier nodes ofthe branch. Thus, if at some point the relaxed problem’s objective functionis worse than the best solution found for the original problem, then thesearch does not need to continue further along the branch since no bettersolution will be found on that branch. It is in this way that relaxation inthe branch-and-bound procedure helps to prune the search tree, reducingthe overall size of the search space.Though less common, there are also ways to use relaxation techniquesin CP. For example, when using interval variables and resource allocation,temporal linear relaxation is used in the IBM ILOG CP Optimizer solver[50]. Additionally, MDD (multi-decision diagrams) have been used to softenglobal constraints and provide discrete relaxations (rather than the contin-uous relaxations employed in branch-and-bound for MIPs) [14].2.2 Comparing TechniquesGiven the variety of paradigms available to model and solve combina-torial optimization problems, how do researchers and practitioners choosean appropriate method? First of all, though metaheuristics, MIP, and CPall incorporate the three strategies mentioned in the previous section, eachparadigm has its own set of strengths: metaheuristics excel in search, MIPexcels in relaxation, and CP excels in inference. Thus if a problem has alarge search space but relatively simple constraints, perhaps metaheuristicswould perform best, especially if trying to obtain a good solution in a shortamount of time. On the other hand, if the problem has complicated (and/ornonlinear) constraints and establishing feasibility is difficult, then CP couldbe more suitable. Lastly, if the constraints are primarily linear and findingthe optimal solution rather than a good solution is of great value, then MIPcould be a better option.All three methods have been shown to excel for certain applications.Many studies have been performed comparing MIP to CP, and the results132.3. LITERATURE REVIEW OF THE EXAM SCHEDULING PROBLEMabout which technique to choose is problem dependent and not clear-cut[31, 35, 40, 53, 57, 68, 69]. Fewer research has compared mathematicalprogramming and/or CP to metaheuristics [7, 25, 64]. The conclusionsof some of these studies are that the techniques should be hybridized infuture work. Hence, the hybridization of multiple paradigms to exploit eachone’s particular strengths has increased in popularity [26, 67, 70]. Thus, thechoice between the methods remains an open question in the optimizationcommunity.One reason for this uncertainty is that each method’s performance is sub-ject to the expertise of the modelers. These methods are most commonlyapplied to NP-complete problems, and there still does not exist (and maynever exist) a polynomial time algorithm to solve problems of this com-plexity. Thus, a method is only as good as it’s programmed to be. Forexample, in CP there are many ways to model a problem (e.g., using globalconstraints versus simple constraints) and there are multitudes of solvers,each of which can differ in how variables are represented or which constraintpropagation techniques are used. Additionally, in each paradigm, variousstructures can be implemented to simplify the problem. For example, Holmet al. used graph structures to drastically reduce the number of decisionvariables required in their MIP model of the University Course Timetablingproblem at the International Timetabling Competition in 2021, which ledto their model finishing in first place [47]. Thus, if the strengths and bestmodeling practices of a method are not used and applied appropriately, thenthe results of a comparison of techniques may be misleading. Ultimately,advancements continue to be made in all three paradigms and the questionas to which method to use depends greatly on the individuals who will beusing that method and the resources available to them.2.3 Literature Review of the Exam SchedulingProblemEducational timetabling consists of three main branches: high schoolcourses, university courses, and university examinations. These branchescan also be split into capacitated and uncapacitated, as well as curriculum-based versus post-enrollment. Uncapacitated timetables do not considerroom limitations, whereas capacitated timetables make assignments to roomsand restrict the number of students scheduled in a room (i.e., respect theroom’s capacity). Curriculum-based (also called pre-enrollment) refers towhen the students register in classes after the schedule is produced and142.3. LITERATURE REVIEW OF THE EXAM SCHEDULING PROBLEMtherefore the students have full knowledge of the schedule before registra-tion, whereas post-enrollment refers to when the schedule is created afterstudents enroll in courses. For our purposes the focus of the review willbe concerned with the capacitated, pre-enrollment examination schedulingproblem, as this is the problem modeled in this thesis. For a more extensivereview of the examination scheduling literature we refer the reader to thesurvey conducted by Qu et al. [62].Research into computational timetabling of educational schedules be-gan in the 1960’s (roughly the same time period as the beginning of CPresearch) at a time when computer power was limited but enrollment ineducation institutions was rising [15, 23]. Over the course of 60 years theneed for quality educational timetables has been in continuous demand sinceuniversities have grown in numbers of students and courses, and manuallyproducing schedules is no longer a viable option.As of 2022, there have been four international competitions centeredaround educational timetabling [4]. The second competition, which tookplace in 2007 (ITC 2007), consisted of two university course timetablingtracks and an examination timetabling track [56]. For this competition,several examination benchmark datasets were provided that were based onanonymized real-world instances. These datasets are still commonly usedfor comparing algorithms and will be explored in this work in Section 6.3.2.The winner of the examination timetabling track and one of the coursetimetabling tracks produced a university timetabling software, UniTime,which has been used by several institutions [59–61]. In this work Mu¨lleruses a constraint-based solver. First, a solution is found using an iterativeforward search algorithm with conflict-based statistics. Then this complete,feasible, solution is improved in an optimizing phase, first using a Hill-Climbing algorithm, then a Great-Deluge algorithm, followed by a SimulatedAnnealing algorithm. Once the Simulated Annealing process fixates on asolution, the process cycles again through the optimizing phase. The thirdcompetition only consisted of a university course timetabling track. The firstand second place finishers both used MIP-based approaches that focusedon reducing the problem size to arrive at solutions [47, 63]. The first placefinisher took a graph-based MIP approach, whereas the second place finisherused local search on the reduced MIP to improve the search for the optimalsolution. While CP has not been the most popular technique applied to theESP (and in some cases proves less effective [11]), it has shown success whenapplied to the high school timetabling and university course timetablingproblems, both of which are similar to the ESP [19, 28].After ITC 2007, there have been several advancements in the research152.3. LITERATURE REVIEW OF THE EXAM SCHEDULING PROBLEMin examination timetabling. The ITC 2007 datasets continue to serve asthe common benchmark for testing and comparing models for this problem.As of December 2021, the best solutions for multiple benchmark instanceshave been attributed by Burke and Bykov [3]. In 2016, they used an Adap-tive Flex-Deluge method (an extension to the popular Great Deluge meta-heuristic where the acceptance condition is flexible) [16], and in 2017, theyused the Late Acceptance Hill Climbing local search method [17]. Other ap-proaches, that have produced comparable results to the competition winnersin 2007, include: an evolutionary metaheuristic called Scatter Search witha Simulated Annealing stage, a Shaking stage, and a Path Relinking stage[37] (though not all competition rules were followed), a single-parameterlocal search heuristic named Step Counting Hill Climbing algorithm [18],variations of Simulated Annealing algorithms [12, 52], a Cellular Memeticalgorithm [51], and a modified Great Deluge algorithm with a partial graphheuristic ordering [55].8Outside of these competition rules, researchers also continue to buildmodels for specific institutions. A hybrid approach combining CP, Simu-lated Annealing and Hill-Climbing was developed by Merlot et al. for theUniversity of Melbourne [58]. Cataldo et al. present a model consisting ofthree phases of MIPs that are solved sequentially to produce curriculum-based examination schedules for the Universidad Diego Portales in Santiagoof Chile [21]. Al-Hawari et al. also present a three-phase MIP model togenerate examination schedules for German Jordanian University [9]. Gencand O’Sullivan use a two-phase CP to produce examination timetables forUniversity Cork College, where the first phase assigns exams to timeslotsand the second phase assigns exams to rooms [34]. This work is similar tothat presented in this thesis, however the requirements at University CorkCollege differ from UBCO in that exams can be split across rooms and allrooms can host multiple exams (as long as the room capacity is respected),thus Genc and O’Sullivan are faced with the bin packing with fragmentableitems problem, which is NP-hard.Altogether, there is a vast amount of literature pertaining to the ESP.Many researchers focus on improving the current best known solutions forthe ITC 2007 benchmark datasets, while others are tasked with modelinga specific institution’s ESP whose particular requirements cannot be en-compassed by general models. This demonstrates the continuous need forexam scheduling models that can accommodate both benchmark datasets8The ITC benchmark datasets are available for download from [3], where one can alsofind updates on the current best solutions.162.4. GLOBAL CONSTRAINT DEFINITIONSand provide solutions for present-day, real-world universities.2.4 Global Constraint DefinitionsThe CP models described in this thesis use various global constraints,which are defined in what follows. We will use the definitions from the GlobalConstraint Catalog by Beldiceanu, Carlsson and Rampon [13]. In thesedefinitions, all CP variables are constraint programming integer decisionvariables.Definition 2.2 (All Different Constraint). For a collection of CP variablesX, alldifferent(X) enforces all CP variables inX to take distinct values.Also called alldiff, alldistinct [13, p. 434].Definition 2.3 (Among Constraint). For a CP variable n, a collection ofCP variablesX, and a collection of integer values V , among low up(n,X, V )enforces that n variables in the X collection are assigned to a value in theV collection [13, p. 478].Definition 2.4 (Bin Packing Constraint). Let I be a finite set of bin IDs,and for each b ∈ I, let cb ∈ Z++ be the capacity of the bin. Then B ={(b, cb) : b ∈ I} is a collection of pairs where each item contains a bin IDb and a capacity cb. Let J be a finite set of indices for the CP variables ina set X. For each j ∈ J , let wj ∈ Z++ be the weight of CP variable xj .Lastly, let F = {(xj , wj) : j ∈ J} be the collection of tuples of CP variablesand their respective weights. Then bin packing capa(B,F ) enforces thateach item xj ∈ X is assigned a bin ID from I so that for each bin b, thesum of weights of the items assigned to b does not exceed the capacity cb[13, p. 600].Definition 2.5 (Element Constraint). Let I be a finite set of indices. Fora CP variable i with domain I, a collection of CP variables (or integers) Tindexed by I, and a CP variable v, element(i,T ,v) ensures that v is equalto the ith item of T . In other words, Ti = v [13, p. 958].Definition 2.6 (Global Cardinality Constraint). Let V be a finite set ofvalues, and for each v ∈ V , let cv be the CP variable reserved to countthe number of occurrences of the value v. Let F = {(v, cv) : v ∈ V } be thecollection of tuples of values and value cardinalities and letX be a collectionof CP variables. Then global cardinality(X, F ) enforces that for eachpair (v, cv), exactly cv variables in X take value v. Also called distribute,distribution, gcc, cardvargcc, egcc [13, p. 1034].172.5. CP OPTIMIZERDefinition 2.7 (Global Cardinality Constraint with Bounds). Let V be aset of values, such that for each v ∈ V , lv and uv are the lower and upperbounds, respectively, for the number of variables being assigned to value v.Let X be a collection of CP variables, and let F = {(v, lv, uv) : v ∈ V }be a collection of triples of values and the values’ lower and upper bounds.Then the constraint global cardinality low up(X, F ) enforces that foreach value triple (v, lv, uv), the number of variables fromX that are assignedthe value v is between lv and uv [13, p. 1040].Definition 2.8 (In Relation Constraint). For a tuple of CP variables, X =(x1,x2, . . . ,xn), and a collection of tuples of values, V , where each tuplehas size n, in relation(X, V ) ensures that X takes its value from the setV . The value of a collection of variables (x1,x2, . . . ,xn) is a collection ofvalues (v1, v2, . . . , vn) if and only if x1 = v1, x2 = v2, . . . , and xn = vn. Alsocalled AllowedAssignments [13, p. 1120].Definition 2.9 (Maximum Constraint). For a CP variablem and a collec-tion of CP variables X, maximum(m,X) ensures that m will be the maxi-mum value of the CP variables in X [13, p. 1348].Definition 2.10 (Minimum Constraint). For a CP variablem and a collec-tion of CP variablesX, minimum(m,X) ensures thatm will be the minimumvalue of the CP variables in X [13, p. 1378].2.5 CP OptimizerThe solver system used in this thesis is IBM ILOG CP Optimizer 22.1.0.CP Optimizer is a software library with a CP engine intended to modeland solve combinatorial optimization problems and constraint satisfactionproblems. This software was built with the intention that non-CP expertscould use the system. Therefore, a thorough understanding of CP is notnecessary, though it can help to effectively use the strengths of the CPengine. This section provides a short description of the solver. The fulldocumentation can be found here [2].CP Optimizer allows users to control the search type. The optionsinclude depth-first search, multi-point search, iterative-diving search, andrestart search. Multi-point search uses a set of solutions and combinesthese solutions to produce new, better solutions (similar to population-basedmetaheuristics). Iterative-diving search can only be used for classic finitecapacity scheduling models that use interval variables. Our model does notinclude variables of this type, so this search was not used. Both depth-first182.5. CP OPTIMIZERsearch and multi-point search were tested over the course of this work, butwe found the most success when using restart search.A restart search performs a depth-first search that restarts after an in-put specified number of failures (CP Optimizer has a default value of 100).During a stage of this search process, either the problem is found to be infea-sible, a feasible solution is found, or the fail limit is reached. If infeasibilityhas been determined by the search, then the process stops. The infeasibilitycould be because of a bound on the objective function discovered in a previ-ous stage. Otherwise, a feasible solution, if found, provides a bound for thenext stage. On the other hand, if the fail limit is reached, then the depth-first search is restarted, using already discovered bounds on the objectivefunction, but with a randomized action to perturb the search order. Thisaction is usually the choice of the initial variables that are branched on, orthe choice of their values. To ensure completeness of the restart search pro-cess, a growth factor for the restart fail limit can be specified (CP Optimizerhas a default value of 1.05) so that the fail limit will grow between stages.For CP Optimizer, the randomization is not described to the user, but theuser can produce different searches by providing a seed as input. For moreinformation regarding restart search methods, see [39].Another aspect of the search that can be controlled by the user is theuse of search phases. A search phase is a tuning object that passes a groupof variables and key information about these variables to the search. Thekey information about the variables can include the mechanism of how tochoose the variables, such as choose those variables of the smallest index orvariables with the smallest domain, and the mechanism of how to choosethe values, such as choose the smallest value first or choose a random value.The user also has the ability to create their own variable and value selectorsusing criteria of their choice. The search phases used in this thesis will bedescribed in Section 5.5.Similar to search phases, in certain Application Programming Interfaces(APIs) of CP Optimizer, users can create goals, which provide a way forthe user to customize the branch-and-bound procedure. If using goals, theuser must completely define how to choose variables to branch on and whichvalues in the variable’s domain to bind the variable to. This gives theuser complete control of the search and allows for more flexibility. Usinggoals effectively requires advanced knowledge of the problem structure andconstraint programming in CP Optimizer, and therefore goals are not easilyimplemented by general users. We explored goals instead of search phases,but none of our customized searches performed better than the search phasesoffered by CP Optimizer.192.5. CP OPTIMIZERAnother advanced technique available to CP Optimizer users is the con-struction of CP constraints. This allows users to control the underlyingfiltering algorithms of the constraints. For example, outside of this thesiswork, we explored implementing the GCC filtering algorithm described inExample 2.1 [43].Other aspects of the solver that can be tuned include the inference levelof the constraints, which is the level of how extensive a global CP constraint’sfiltering algorithm is used (e.g., extended versus basic for the All Differentconstraint), and the number of threads/workers.Lastly, we provide a correspondence between the global constraints inthe CP Optimizer C++ API and those used in the catalog of [13]:− alldifferent = IloAllDiff,− among low up = IloCount,− bin packing capa = IloPack,− element = IloElement,− global cardinality = IloDistribute,− global cardinality low up = IloDistribute,− in relation = IloAllowedAssignments,− maximum = IloMax, and− minimum = IloMin.20Chapter 3Research ProjectIn the Summer of 2021, the DOPT (Discrete Optimization) Team, froma request of the Provost of UBCO, put forth a proposal to conduct a researchproject to create software to automate exam scheduling for the university.This proposal was accepted and the project was conducted from September2021 through to August 2022. This thesis describes the software and themathematical model of the research project. The results from this researchproject will be discussed in Section 6.1.3.1 BackgroundUBCO, like most universities, continues to grow in terms of the num-ber of students enrolled and courses offered. This has added stress on theadministration to produce quality exam schedules that meet students’ andinstructors’ needs within the confines of time and space. In addition to theincrease in student volume, this year the UBCO Senate passed a modifi-cation to the student hardship rule. In the past, a student hardship wasdefined as a student having to write three exams within a consecutive 24-hour window during the examination period. If a student is scheduled tohave a hardship, they are allowed to request an out-of-time exam and theexam instructor must accommodate the student’s request by providing anadditional time outside of the scheduled time for the student to write theexam. This accommodation adds extra work for the instructor as they haveto ensure exam security, provide more time for exam invigilation, and createan equivalent new exam. Therefore student hardships are not desirable fromboth the student and instructor perspective. To complicate this further, thetime window in the definition of hardships was lengthened by three hoursand is now defined as follows.Definition 3.1 (3-in-27-hours hardship). If a student at UBCO writes threeexams that span at most 27 hours from the start of the first exam to theend of the last exam, then a 3-in-27-hours hardship occurs.213.2. DATAThe software previously used by the administration did not have theability to include this modification, requiring UBCO to seek out a new examscheduling system.In addition to the adjusted student hardship rule, the examination periodwas recently shortened from a 3-timeslot-per-day 14-day period, excludingSundays (16 days and 42 timeslots total), to a 4-timeslot-per-day 12-dayperiod, including Sundays (12 days and 44 timeslots total). This changecreates additional challenges in producing a quality exam schedule sincestudents are being forced to write exams in a more compact overall lengthof time.3.2 DataFor this project we received data in the form of Excel files. This dataincludes student enrollment, location features and capacities, and exam re-quests submitted by instructors. Exam requests may include time and lo-cation specific information, groups of exams that should be affiliated andscheduled together, and instructor lists.The data was fluid in that enrollment data changed up until and evenafter the publication date of the schedule. This was due to changes in examdelivery (online versus in-person) and an extension to the date for students toadd or drop courses in response to COVID-19. These late data modificationswere easily accommodated because the software is flexible and allows forselect exams to shift in a previously determined schedule. In addition, thesoftware can highlight the minimum adjustments to a schedule that areneeded to eliminate student hardships which may have arisen because of achange in data.3.3 Software ComponentsThere are two components which contribute to the making of this flex-ible and dynamic software: a constraint programming model and an examscheduling viewer.Constraint Programming Model The engine behind this software iscomposed of the CP model described in Section 5. The CP model allowsfor the software to be customizable for UBCO, including, for example, theeasy accommodation of changes in hardship rules and examination periodstructure. This program also enables users to make changes to a previously223.3. SOFTWARE COMPONENTSproduced schedule, or minimize the number of changes required to a make anew schedule feasible (and/or optimal). Furthermore, hypothetical scenarioscan be tested in the model to aid in planning.Exam Scheduling Viewer The exam scheduling viewer, provided byBitmotek Optimization Ltd., was an important tool used to analyze thesolutions produced by the CP model. The main functionalities of the toolinclude:− Analysis of metrics. The tool calculates key metrics of an exam sched-ule, including: room usage, hardships, and students or instructorshaving back-to-back exams.− Solution checking. Users can easily check the feasibility of the sched-ules produced by the CP model. For example, one can ensure thatexams are not being scheduled in the same room as other exams atthe same time, that exams are scheduled in timeslots meeting instruc-tor needs (e.g., day-time exams versus evening exams), and that examsare scheduled in rooms with the requested features (e.g., electrical out-lets), among many other requirements and requests from faculty.− Visualization of schedule quality. The viewer allows users to look forless desirable features in the exam schedule. These include groups ofexams commonly taken by students being scheduled within a shorttimeline, and an abundance of exams being scheduled in the eveningor on the last few days.23Chapter 4The General ExamScheduling Problem4.1 Elementary RequirementsLet Z+ denote the set of nonnegative integers and Z++ = Z+ \ {0}.All intervals throughout will be subsets of Z+ and for k1, k2 ∈ Z+, k1 ≤ k2,denote the (integer) interval [k1, k2] = {k1, . . . , k2}, and define [k2] = [1, k2].9For an interval [a, b], define the length of [a, b] to be ℓ([a, b]) = b−a if b > a,and ℓ ([a, b]) = ℓ(∅) = 0 otherwise. Moreover, for a finite monotonicallyincreasing sequence of integers r0, . . . , rq, define r(i, j] to be the interval[ri + 1, rj ] for 0 ≤ i < j ≤ q.The Exam Scheduling Problem (ESP) is defined as the following: given afinite set of pairwise disjoint10 integer intervals T = {[s1, f1], . . . , [sm, fm]}called the timeslots, a set P called the persons, a set E of subsets of Pcalled the exams, a function ε : E → Z++ called the exam sizes, a functionδ : E → Z++ called the exam durations, a set R called the rooms, and afunction σ : T ×R→ Z+ called the temporal room sizes, find an assignmentτ : E → T called the timeslot assignment, and an assignment ρ : E → Rcalled the room assignment, such that for all E,E′ ∈ E, E ̸= E′, the followingfour requirements are satisfied.11Requirement 1. (Person Single-Tasking) τ(E) ̸= τ(E′) if E ∩ E′ ̸= ∅.Requirement 2. (Exam Duration) δ(E) ≤ ℓ(τ(E)).Requirement 3. (Room Single-Tasking) ρ(E) ̸= ρ(E′) if τ(E) = τ(E′).Requirement 4. (Room Size) ε(E) ≤ σ (τ(E), ρ(E)).9Note that only integer-valued intervals will be used in this thesis, so this notationshould not cause confusion with that typically used for real-valued intervals.10The pairwise disjoint restriction is relaxed in Requirement 6. Moreover, there is noloss of generality in assuming that time can be discretized for exam scheduling.11These definitions for τ and ρ will be used until the end of Chapter 5. In Chapter 6,these symbols will be redefined to match the standard notation for performance profiles.244.1. ELEMENTARY REQUIREMENTSRequirement 1 ensures that no person (including the invigilator) has twoexams assigned to the same timeslot (see Requirement 6 for an extensionof this requirement for the case of overlapping timeslots). Requirement 2restricts the duration of an exam to not exceed the length of its assignedtimeslot. Moreover, Requirement 3 ensures that no room is assigned twodifferent exams during a timeslot (see Requirement 10 for a relaxation ofthis requirement). Finally, Requirement 4 ensures that the room assignedto an exam during the assigned timeslot can accommodate the exam’s sizerequirement12 (see Requirement 11 for a relaxation of this requirement).In this specification, the set of persons does not distinguish betweenstudents and instructors as they both are present during their exam. In thecase of hardships, however, the students and instructors are separated asnecessary (see Section 4.2.1). Moreover, for each person p ∈ P and examE ∈ E, if p ∈ E, then we say p writes E, or E is written by p, even thoughp may be an instructor.We will refer to [sk, fk] ∈ T as timeslot k. For notational convenience, letσk(R) = σ([sk, fk], R) for each timeslot k. The temporal room sizes functionallows one to ensure that a room R does not use a timeslot k by specifyingσk(R) = 0. This may be necessary if a room is closed during the timeslot, orto limit timeslots that overlap for the room (see Requirements 10 and 11).Moreover, for each room R ∈ R, let T (R) = {[sk, fk] ∈ T : σk(R) > 0} becalled the effective timeslots of room R.A nonempty collection A of subsets of a set A is called intersecting iffor all A1, A2 ∈ A, A1 ∩ A2 ̸= ∅. Using the maximal intersecting subsetsof exams for Requirement 1 is desired but finding them is computationallyimpractical (i.e., NP-hard). Instead, there are some natural intersectingsubsets that can be used. For each person p ∈ P , let the intersecting subsetof exams that p writes be denoted:E(p) = {E ∈ E : p ∈ E}.Moreover, the maximal intersecting subsets of timeslots – we will call thiscollection B∗ – is the set of maximal cliques of the corresponding intervalgraph which can be found in linear time.12Typically, for every exam E, ε(E) = |E| − 1, since the instructor does not need aproper examination seat.254.2. REQUIREMENT EXTENSIONS4.2 Requirement ExtensionsThe ESP can be extended to include a variety of other constraints fromreal-world contexts. We will assume that τ and ρ are fixed for the definitionsthat follow.The first of these extensions further limits τ and ρ for particular situa-tions.Requirement 5. (Time and Room Specific) An exam E ∈ E can be forcedto be assigned a timeslot from a subset B of timeslots by the additionalrequirement τ(E) ∈ B. Moreover, the exam can be forced to be assigned aroom from a subset Q of rooms by the additional requirement ρ(E) ∈ Q.An example of when Requirement 5 is needed is if an instructor requirestheir exam to be scheduled during the day, or the exam requires rooms whichhave a projector or power outlets.In certain cases of modeling the ESP, it may be necessary to allow thetimeslots of the problem to overlap (i.e., not be pairwise disjoint). This oc-curs most commonly when modeling exams that are allowed varying lengths.Requirement 6. (Overlapping Timeslots) If the timeslots are allowed tooverlap, then Requirement 1 is replaced with:τ(E) ∩ τ(E′) = ∅ if E ∩ E′ ̸= ∅.Moreover, Requirement 3 is replaced with:ρ(E) ̸= ρ(E′) if τ(E) ∩ τ(E′) ̸= ∅.Note that Requirement 6 generalizes Requirement 1 as non-overlappingtimeslots satisfy τ(E) ∩ τ(E′) = ∅ if and only if τ(E) ̸= τ(E′). The practi-cality of Requirement 6 will be discussed in Section 5.1.3.Requirement 7. (Temporal Precedence) To require an exam E to beafter another exam E′, then if τ(E) = [sk, fk] and τ(E′) = [sj , fj ], requirej < k.Requirement 8. (Coupled Exams) To require two exams E and E′ to bewritten1. during the same timeslot, then require τ(E) = τ(E′), or2. in the same room, then require ρ(E) = ρ(E′).264.2. REQUIREMENT EXTENSIONSRequirement 9. (Separated Exams) To require two exams E and E′ tobe written1. during different timeslots, then require τ(E) ̸= τ(E′), or2. in different rooms, then require ρ(E) ̸= ρ(E′).Note that Requirements 8.2 and 9.2 only make sense if we have Require-ments 10 and 11, which will be described in what follows.These next extensions allow for the use of a large room, such as a gym,to host several exams at once. For each R ∈ R and timeslot k, letCR,k = {E ∈ E : ρ(E) = R, τ(E) = [sk, fk]}be called the concurrent exams in room R during timeslot k. In other words,|CR,k| counts the number of exams scheduled in room R during timeslotk. Let γk(R) be the maximum number of concurrent exams allowed to bescheduled in room R during timeslot k.If more than one exam is allowed in a room during a given time, thenRequirement 3 is either removed entirely or it is replaced with the followingrequirement to limit the number of concurrent exams assigned to the room.Requirement 10. (Room Task Limit) During a timeslot k and for a roomR ∈ R, to limit R to be assigned at most γk(R) concurrent exams, thefollowing is required:|CR,k| ≤ γk(R).With more than one exam allowed in a room at a given time, Require-ment 4 is replaced with the following requirement.Requirement 11. (Room Multitasking Size) For a room R ∈ R to hostconcurrent exams, for every timeslot k,∑E∈CR,kε(E) ≤ σk(R).The left hand side of the inequality in Requirement 11 counts the numberof persons in the exams assigned to room R during timeslot k, and the righthand side is the effective room size for room R during timeslot k.Concurrent exams pose logistical challenges if timeslots overlap. In prac-tice, concurrent exams assigned to a room can start at the same time butmay finish at different times. These exams would be assigned different over-lapping timeslots where one timeslot is contained in the other. Such a sit-uation can be handled by using the larger timeslot for both exams. This is274.2. REQUIREMENT EXTENSIONSsufficient since it is not the case, in practice, that an exam would start in themiddle of a timeslot of another exam in the same room and, say, end later,since this would lead to disturbances while students are writing. Thus, inorder to simplify the model without losing applicability, we can effectivelymodel concurrent exams for rooms that allow multiple tasks by limitingthese rooms to have non-overlapping timeslots when they multi-task. Moreformally, this limitation is for all R ∈ R and all [sk, fk], [sk′ , fk′ ] ∈ T (R) withk′ ̸= k, if γk(R) > 1 and γk′(R) > 1, [sk, fk] ∩ [sk′ , fk′ ] = ∅. If γk(R) = 1,then other timeslots can intersect [sk, fk].The requirements included above can be classified as hard, meaning theymust be met in order for an exam schedule to be feasible. The remainingrequirements are soft, meaning they do not necessarily need to be satisfied,but can be added to improve the quality of an exam schedule.As with the overlapping case, if exams of varying durations are sched-uled in the same room at the same time, then this may lead to distur-bances for students writing the exams. With this motivation in mind, let∆k(R) = {δ(E) : τ(E) = [sk, fk], ρ(E) = R} be the set of durations of examsscheduled in room R during timeslot k. We want to only penalize the usageof a room if that room has exams of different durations. Thus, we need anexpression where for a room R and a timeslot k, if |∆k(R)| = 0 (i.e., theroom is empty during timeslot k) or |∆k(R)| = 1 (i.e., the room containsexams of the same duration during timeslot k), the expression evaluatesto 0. Thus, the requirement to reduce multiple durations of exams beingscheduled in the same room at the same time can be stated as follows.Requirement 12. (Mixed Duration) To reduce the number of exams ofdifferent durations scheduled in room R during timeslot k, minimizemax (1, |∆k(R)|)− 1.The next requirement allows institutions to specify if they want largerexams to be earlier in the examination period, which may be desirable, forexample, to allow more time for marking. For c ∈ Z+, let E>c = {E ∈ E :ε(E) > c} be the set of exams of size larger than c. Moreover, for c ∈ Z+and k ∈ [m], let E>c,k = {E ∈ E : ε(E) > c, τ(E) = [sk, fk]} be the set ofexams of size larger than c that are assigned to timeslot k.Requirement 13. (Frontload Large Exams) To reduce the number ofexams of size larger than c being scheduled after a fixed timeslot j, minimize∑[sk,fk]∈Tk>j|E>c,k|.284.2. REQUIREMENT EXTENSIONSFurthermore, an institution may want to reduce the number of examsscheduled during undesirable timeslots (e.g., weekends) or in special rooms(e.g., theaters). Define Ek = τ−1([sk, fk]) to be the set of exams assigned totimeslot k.Requirement 14. (Penalties)1. For a subset of timeslots B ⊆ T , where exams should avoid beingassigned to any [sk, fk] ∈ B according to the penalty ωk, minimize∑[sk,fk]∈Bωk · |Ek|,that is, the number of exams assigned to the penalized timeslots,weighted by the timeslot penalties.2. For a subset of rooms Q ⊆ R whose usage should be avoided accordingto penalty ωR for each R ∈ Q, minimize∑[sk,fk]∈T∑R∈QωR · |CR,k|,that is, the number of exams assigned to the penalized rooms duringany timeslot, weighted by the room penalties.4.2.1 Measuring HardshipsWe focus here on measuring, and later minimizing, the number of timespersons have a certain number of examinations assigned to timeslots thatare within a certain amount of time.Let d ∈ Z+ represent a length of time. For a fixed timeslot k ∈ [m],the subset of timeslots of T that start and finish in the range [sk, sk + d] isdefined byBk,d = {[sj , fj ] ∈ T : sj ≥ sk and fj ≤ sk + d} .Collecting all these subsets produces the set Bd = {B1,d, . . . , Bm,d} of allsubsets of timeslots that are within d time units of each other.For a given person p ∈ P , the exams written by person p during a B ∈ Bdis given byWp,B = {E ∈ E(p) : τ(E) ∈ B}.For a given positive integer w, representing a minimum number of writes,the set of (w, d)-hardships (of τ) is defined to beHw,d = {(p,B) : p ∈ P,B ∈ Bd, |Wp,B| ≥ w}.294.2. REQUIREMENT EXTENSIONSThus |Hw,d| is the number of times persons are in at least w exams that areassigned by τ to be within any d time units of the schedule.13Example 4.1 (3-in-27-hours Hardships).UBCO’s examination period spans 12 days and there are four times-lots per day: 8:30 a.m., 12:00 p.m., 3:30 p.m., and 7:00 p.m. However aSunday only has two timeslots: 12:00 p.m., and 3:30 p.m.. Each exam isassumed to be two and a half hours long. Discretizing time so that 8:30a.m. on the first day is at time 17 = 8.5 × 2, and is a Monday, the set oftimeslots T have first week time intervals Monday: [17, 22], [24, 29], [31, 36],[38, 43]; Tuesday: [65, 70], . . . ; Sunday: [312, 317], [319, 324]; along with sec-ond week time intervals [353, 358], . . . , [566, 571]. To measure those studentshaving a 3-in-27-hours hardship, the required timeslot sets are representedby B54 (half hour increments). See Table 4.1 for some examples. Note thatthis hardship corresponds to students having 3 exams within 5 consecutivetimeslots.Figure 4.1 illustrates the concept of a (3, 54)-hardship. Consider twostudents, p1 and p2, and four courses, E1, E2, E3, and E4. Let E(p1) ={E1, E2, E3} and E(p2) = {E1, E2, E4} (these exams correspond to PHYS122 001, SOCI 111 002, STAT 121 001 and CHEM 211 001, respectively).Suppose τ(E1) = [17, 22], τ(E2) = [31, 36], τ(E3) = [65, 70], and τ(E4) =[72, 77]. Then, considering the first two subsets of timeslots in B54 onthe first Monday, B1 = {[17, 22], [24, 29], [31, 36], [38, 43], [65, 70]} and B2 ={[24, 29], [31, 36], [38, 43], [65, 70], [72, 77]}, we have Wp1,B1 = {E1, E2, E3},Wp1,B2 = {E2, E3}, Wp2,B1 = {E1, E2}, and Wp2,B2 = {E2, E4}. Thus(p1, B1) ∈ H3,54, that is, a (3, 54)-hardship occurs for person p1 on Monday.To minimize the number of persons having a 3-in-27-hours hardship, τis chosen so as to minimize |H3,54|. Alternatively, one could forbid suchhardships by restricting |H3,54| to be zero.Requirement 15. (Hardships) For a positive integer w, representing a num-ber of writes, and nonnegative integer d, representing a length of time, toensure that no persons have w examinations assigned to timeslots that arewithin d time units (i.e., no (w, d)-hardships), then require:|Hw,d| = 0.To ensure that these type of hardships are minimized, then include |Hw,d|as a term in the minimizing objective function of the model.13The set of persons P can be reduced here to just include students or instructorsdepending on the application of the hardship.304.2. REQUIREMENT EXTENSIONSTable 4.1: Example timeslot sets of B54 for 3-in-27-hours hardships.Day Timeslot Sets Involving DayFirst Monday {[17, 22], [24, 29], [31, 36], [38, 43], [65, 70]},{[24, 29], [31, 36], [38, 43], [65, 70], [72, 77]},{[31, 36], [38, 43], [65, 70], [72, 77], [79, 84]},{[38, 43], [65, 70], [72, 77], [79, 84], [86, 91]}First Sunday {[264, 269], [271, 276], [278, 283], [312, 317]},{[271, 276], [278, 283], [312, 317], [319, 324]},{[278, 283], [312, 317], [319, 324]},{[312, 317], [319, 324], [353, 358]},{[319, 324], [353, 358], [360, 365], [367, 372]}Last Friday {[497, 502], [504, 509], [511, 516], [518, 523], [545, 550]},{[504, 509], [511, 516], [518, 523], [545, 550], [552, 557]}{[511, 516], [518, 523], [545, 550], [552, 557], [559, 564]}{[518, 523], [545, 550], [552, 557], [559, 564], [566, 571]}Other special classes of hardships include 2-in-1s and back-to-backs. A2-in-1-day hardship occurs when a person writes two exams on the same day,while a back-to-back hardship occurs when a student writes two consecutiveexams on the same day. Using the timeslots from Example 4.1, the 2-in-1-day and back-to-back hardships are represented by H2,26 and H2,12,respectively. Given the regular nature of the timeslots of the example, amore efficient implementation is outlined at the end of the section entitledCP of Requirement 15.314.2. REQUIREMENT EXTENSIONS(a) Student p1’s exams, which span 27hours and therefore classify as a (3, 54)-hardship.(b) Student p2’s exams, which spanmore than 27 hours and therefore donot classify as a (3, 54)-hardship.Figure 4.1: An example of the 3-in-27-hours rule.32Chapter 5CP Specification of theGeneral Exam SchedulingProblemIn what follows, we partition our CP implementation of the ESP into atimeslot assignment subproblem and into one room assignment subproblemfor each timeslot. The timeslot assignment subproblem is solved first andthe result τ is used as input for each of the room assignment subproblems.The room assignment subproblem for timeslot k assigns rooms to only thoseexams assigned to timeslot k by τ . We say τ is room-assignable if, solelybased on sizes and task requirements, the assignment has a feasible roomassignment subproblem solution for each timeslot. This definition purposelydoes not consider other room-related requirements such as exams needingto be scheduled in a particular type of room.The timeslot assignment subproblem contains constraints that are nec-essary and, in all but one scenario, are also sufficient (see Theorem 5.3) toensure that all of its feasible solutions are also room-assignable. The scenariothat cannot guarantee sufficiency occurs when Requirements 10 and 11 arespecified, that is, when multiple exams can be scheduled in the same room atthe same time. In this case, the timeslot assignment subproblem constraintsare only necessary, although in practice do well in finding room-assignablesolutions. An extension to the CP implementation of the timeslot assign-ment subproblem that ensures all feasible solutions are room-assignable evenwhen Requirements 10 and 11 are used is described in Section 5.3. However,it may not be possible to use this extension in practice, depending on thesize of the input, as discussed in Section 5.4. In order to highlight theseperformance considerations in the discussion, the sizes are calculated in thischapter for some of the relevant implementation options. Section 5.4 willalso explain more limitations of the timeslot assignment model and its abilityto produce a τ that has a room assignment ρ which satisfies all room-relatedrequirements, not just those pertaining to size and room task limits.335.1. TIMESLOT ASSIGNMENT SUBPROBLEMTo facilitate the description of the implementation, the names of CPvariables will use a bold typeface. Refer to Section 2.4 for the definitions ofthe global constraints used in this chapter.5.1 Timeslot Assignment SubproblemThe timeslot assignment subproblem finds a timeslot assignment τ thatensures the implicit existence of a feasible room assignment ρ without actu-ally determining ρ. In this section, we describe a CP implementation of thegeneric specification by first defining the decision variables and then definingthe constraints for each of the requirements.5.1.1 Primary Decision VariablesIn order to find a τ satisfying the requirements, for each E ∈ E, we definea CP integer-valued decision variable tE whose domain is the set of indicesof the timeslots, [m] = {1, . . . ,m}, with the understanding (to be encodedby the constraints) that if tE is bound to k, then τ(E) = [sk, fk]. For anysubset D of exams, we let TD = {tE : E ∈ D} be the corresponding set ofdecision variables.5.1.2 CP of Elementary RequirementsThere are four requirements that are standard across institutions andare included in most models of the ESP. In what follows we will describeCP implementations of these requirements.CP of Requirement 1 (Person Single-Tasking).Requirement 1 can be restated that each intersecting subset of exams of sizetwo must have the timeslot assignments of the exams different from eachother. When this requirement is applied to any intersecting subset I ⊆ E ofexams, the timeslot assignments of any pair of exams from Imust be differentfrom each other, and so all of the timeslot assignments of exams from Imust be different from each other. Thus we impose the global constraintalldifferent(TI) (see Definition 2.2) to implement Requirement 1 for allpairs of exams in I.The larger the size of the intersecting subset of exams, the greater thepossible propagation power of the alldifferent constraint. That beingsaid, using the maximal intersecting subsets of exams would be ideal butit can be computationally too expensive to find such subsets. If such sets345.1. TIMESLOT ASSIGNMENT SUBPROBLEMare not known, then it can be effective to use E(p) for each person p ∈ P .The key is that for all exams E,E′ ∈ E, E ̸= E′, if {E,E′} is intersecting,then{E,E′} is a subset of at least one of the maximal intersecting subsetsof exams.CP of Requirement 2 (Exam Duration).The duration requirement for an E ∈ E is implemented by restricting theinitial domain of tE directly by removing each k such that δ(E) > ℓ ([sk, fk])(or indirectly and equivalently, by using the constraint tE ̸= k).To motivate the CP formulation of Requirements 3 and 4, consider thefollowing example.Example 5.1 (Simple Room Single-Tasking).Let E = {E1, E2, ..., E7}, R = {R1, R2, R3, R4}, and T = {[s1, f1], [s2, f2]},where both timeslots have the same duration and all exams can be scheduledin both timeslots. Table 5.1 lists the sizes of the exams and rooms.Table 5.1: Exam and room sizes used in Example 5.1.(a) Exam sizesExam E1 E2 E3 E4 E5 E6 E7Exam Size (ε(Ei)) 25 25 50 75 100 125 150(b) Room sizesRoom R1 R2 R3 R4Room Size (σ(Ri)) 25 50 100 150We can see that E6 and E7 must be scheduled in the largest room, R4,due to their size. Therefore these exams must be assigned different timeslots.This can be ensured by implementing the CP of Requirements 3 and 4, whichwill be discussed in more detail in Example 5.2.355.1. TIMESLOT ASSIGNMENT SUBPROBLEMCP of Requirements 3 – 4 (Room Single-Tasking) and (Room Size).In order to ensure that τ is chosen to be room-assignable, that is, it implic-itly satisfies Requirements 3 and 4, we consider a sequence of constraintsthat are parameterized by a positive integer, c, which will ensure the nec-essary but not sufficient statement that the number of exams of size largerthan c assigned to a timeslot is at most the number of rooms of size largerthan c during the timeslot.14To implement this idea, recall that E>c = {E ∈ E : ε(E) > c} is the set ofexams of size larger than c. For k ∈ [m], define the number of rooms largerthan c during timeslot k to be R>c,k = {R ∈ R : σk(R) > c}. The formatof the restrictions are provided by the set of triples Fc = {(k, 0, |R>c,k|) :k ∈ [m]} for the global constraint global cardinality low up(TE>c , Fc)(see Definition 2.7). Here k refers to the timeslot that the decision variablestE ∈ TE>c are assigned, and 0 and |R>c,k| are the lower and upper bounds,respectively, on the number of decision variables from TE>c that can be as-signed to k. Therefore, this constraint ensures that, for each k, the numberof decision variables tE , where E ∈ E>c , that are bound to k is between 0and |R>c,k|. In other words, the number of exams E with ε(E) > c that areassigned by τ to timeslot k is at most the number of rooms that have sizelarger than c throughout the timeslot.A timeslot assignment τ satisfying the global cardinality low up con-straint for a fixed minimum size c does not guarantee that there is a feasibleroom assignment ρ. But a sequence of these global cardinality low upconstraints does. Let k be a fixed timeslot. For this timeslot, we nowconsider the number of distinct room sizes and let q = qk denote thisnumber. Define r0 = 0 and consider the (non-multi-)set of room sizes{σk(R) : R ∈ R>0,k} = {r1, . . . , rq} where the ri’s are labeled so that they arestrictly increasing. Note that for an ESP to be feasible, no exams can havemore students than the number of seats in the largest room, thus E>rq = ∅.The CP constraints for Requirements 3–4 are thenglobal cardinality low up(TE>ri, Fri) for i ∈ [0, q − 1].(Constraints 3–4)To demonstrate this sequence of constraints, we will apply them to theprevious example.14Theorem 5.3 will show that the collection of these constraints is both necessary andsufficient for ensuring that a timeslot assignment solution is room-assignable.365.1. TIMESLOT ASSIGNMENT SUBPROBLEMExample 5.2 (Constraints for Simple Room Single-Tasking).Continuing Example 5.1, the number of distinct room sizes for eachtimeslot is 4, that is, q = q1 = q2 = 4 and r1 = 25, r2 = 50, r3 = 100,and r4 = 150. Since room sizes are the same for each timeslot, there issymmetry between the timeslots, and therefore we can consider a generaltimeslot k ∈ {1, 2}. We will now formulate Constraints 3–4 for i ∈ [0, q− 1],starting with q − 1 and continuing in a decreasing fashion.The first constraint, where i = q − 1 = 3, has TE>r3 = {tE6 , tE7}, sincer3 = σ(R3) = 100 and ε(E6) = 125 > r3 and ε(E7) = 150 > r3 (i.e., E6 andE7 are larger than the second largest room). We also have R>r3,k= {R4}(i.e., R4 is the only largest room). Thus, Fr3 = {(k, 0, 1) : k ∈ [m]}, soglobal cardinality low up(TE>r3, Fr3) simply restricts at most one examfrom TE>r3to be scheduled in each timeslot. Therefore the two largest examswill not be scheduled at the same time, as we noted earlier.The second constraint, where i = q−2 = 2, has TE>r2 = {tE4 , tE5 , tE6 , tE7},since r2 = σ(R2) = 50 and ε(E4) = 75 > r2, ε(E5) = 100 > r2, ε(E6) =125 > r2 and ε(E7) = 150 > r2. We also have R>r2,k= {R3, R4}. Thenglobal cardinality low up(TE>r2, Fr2) restricts at most two exams fromTE>r2to be scheduled in each timeslot. Note that by itself this constraintcould lead to a timeslot assignment that is not room-assignable, since bothof the largest exams could be assigned the same timeslot. However, whenpaired with the first constraint, this potential assignment would be regardedas infeasible.Table 5.2: Values and CP variables used for implementing Constraints 3–4for Example 5.2.i ri R>ri,kTE>riFri3 100 {R4} {tE6 , tE7} {(k, 0, 1) : k ∈ [m]}2 50 {R3, R4} {tE4 , tE5 , tE6 , tE7} {(k, 0, 2) : k ∈ [m]}1 25 {R2, R3, R4} {tE3 , tE4 , tE5 , ..... tE6 , tE7}{(k, 0, 3) : k ∈ [m]}0 0 {R1, R2, R3, R4} {tE1 , tE2 , tE3 , tE4 ,. tE5 , tE6 , tE7}{(k, 0, 4) : k ∈ [m]}375.1. TIMESLOT ASSIGNMENT SUBPROBLEMContinuing in this manner we get four global constraints, whose param-eters are summarized in Table 5.2.Table 5.3 illustrates a possible assignment of these exams to timeslotsthat would satisfy Constraints 3–4, as well as a possible room assignment.Note that the exams and rooms are labeled according to size for ease ofreading.Table 5.3: Possible schedule of the exams, rooms and timeslots from Exam-ple 5.1. The rooms and exams are labeled by their sizes.Room Size Exam SizeTimeslot 1 Timeslot 2150 125 150100 75 10050 50 -25 25 25Observe that if multi-tasking is allowed, including these constraints inthe model would remove potential solutions. For example, consider theassignment of Table 5.3 but modified so that both exams of size 25 areassigned the first timeslot. This assignment is not feasible when single-tasking is required, but if each room was allowed multiple exams, then thesecond exam of size 25 could be placed in either of the two largest roomsduring the first timeslot.As described above, Constraints 3–4 must be necessarily satisfied by anyfeasible solution of the room assignment problem for timeslot k (when onlyconsidering size and room task requirements). The next theorem shows thatthey are also sufficient.Theorem 5.3. A feasible solution of the timeslot assignment problem withRequirements 3–4 is room-assignable if and only if the solution satisfies Con-straints 3–4.Proof. Any feasible solution of the timeslot assignment problem with Re-quirements 3–4 that is room-assignable must satisfy Constraints 3–4 giventhe definition of the constraints described above.On the other hand, consider a feasible solution τ to the timeslot as-signment problem with 3–4 satisfied. We show that this solution is room-assignable for an arbitrary but fixed timeslot [sk, fk]. Let q = qk, the number385.1. TIMESLOT ASSIGNMENT SUBPROBLEMof distinct room sizes of the timeslot. For each i ∈ {0, ..., q − 1}, let S(i) bethe statement that all exams assigned to [sk, fk] by τ that have size largerthan ri can be assigned rooms in timeslot [sk, fk]. Note that all of the roomsassigned for these exams must have size larger than ri.Fix k ∈ [m] and for i ∈ {0, ..., q − 1}, let Ki = E>ri,k = {E ∈ E : ε(E) >ri, τ(E) = [sk, fk]}, that is, the set of exams of size larger than ri assignedto timeslot [sk, fk]. With i > 0 note that Ki ⊆ Ki−1 and that Ki−1 \Ki isprecisely the set of those exams that are assigned to the timeslot with sizein the range r(i− 1, i] (i.e., size larger than ri−1 but at most ri). Moreover,|Ki| = |{tE ∈ TE>ri : tE is bound to k}|,since E ∈ Ki if and only if E ∈ E>ri and τ(E) = [sk, fk], if and only if decisionvariable tE ∈ TE>ri is bound to k.Rephrased, S(i) is the statement that the exams of Ki can be assignedto rooms in the timeslot. The following proves that S(0) is true by showingS(q − 1) is true and then inducting backwards to zero by proving that S(i)implies S(i− 1) for all i ∈ [q − 1].S(q−1) is true. The constraint global cardinality low up(TE>rq−1 , Frq−1)ensures that |{tE ∈ TE>rq−1 : tE is bound to k}| ≤ |R>rq−1,k|. Thus |Kq−1| ≤|R>rq−1,k| and hence there are enough rooms of size more than rq−1, that isthose of size rq, so that each of the |Kq−1| exams can be assigned to a roomof size at most rq, one exam to a room, during the timeslot.S(i) implies S(i−1). Suppose, for some i ∈ [q−1], S(i) is true. Thus theexams in Ki can be assigned to rooms during the timeslot. None of these ex-ams can be assigned to rooms whose sizes are in the range r(i−1, i] since theyall have size larger than ri. Assign each of these exams to their own room.There are then |R>ri−1,k| − |Ki| remaining rooms without assigned exams forthe timeslot that have size larger than ri−1. The set of remaining examsto be assigned for the timeslot that have size larger than ri−1 is Ki−1 \Ki.Moreover, the constraint global cardinality low up(TE>ri−1, Fri−1) ensuresthat |Ki−1| ≤ |R>ri−1,k| which in turn implies|Ki−1 \Ki| = |Ki−1| − |Ki| ≤ |R>ri−1,k| − |Ki|.Thus there are enough unassigned rooms of size larger than ri−1 (and hencesize at least ri) so the exams with sizes in (ri−1, ri] in Ki−1 can be assignedto their own room. Thus S(i− 1) is true.395.1. TIMESLOT ASSIGNMENT SUBPROBLEMBy induction, we have that S(0) is true and hence all of the examsassigned to the timeslot by τ have been assigned a room during the timeslot.From a given timeslot assignment τ satisfying these constraints, a greedyalgorithm can then be used to assign rooms of a given timeslot (assumingthere are no other room restrictions). This is done by first ordering therooms from largest to smallest in a list as well as ordering the exams largestto smallest in a separate list. Then repeat the following: assign the largestroom to the largest exam, and delete each from their respective lists.Typically, the number of rooms of a small size is much larger than thenumber of rooms of a larger size (e.g., in most universities there is only onegym). Moreover, many small size rooms do not get assigned an exam for agiven timeslot. For these reasons, the room assignment problem is typicallydifficult for the larger sized exams. Thus in practice, not all minimum sizesneed be considered above to ensure a feasible room assignment.5.1.3 CP of Extended RequirementsTo expand upon the simple ESP, the following CP implementations ofthe extended requirements can be included.CP of Requirement 5 (Time and Room Specific).Requirement 5 is straightforward to implement. For the timeslot assignmentpart, if E ∈ E and B ⊆ T , the requirement τ(E) ∈ B is implemented byreducing the domain of tE to be {k : [sk, fk] ∈ B} using not equal constraintsor other CP primitives.CP of Requirement 6 (Overlapping Timeslots).In order to extend Requirement 1 for overlapping timeslots, the among low upglobal constraint is used (see Definition 2.3). Recall thatB∗ is the set of max-imal intersecting timeslots. For each B ∈ B∗, let VB = {k : [sk, fk] ∈ B}.Using an intersecting subset I ⊆ E of exams, the among low up(0, 1,TI, VB)constraint (see Definition 2.3) is used to require that at most one variablefrom TI can take a value from VB. This will force that at most one timeslotfrom any two timeslots that overlap be chosen for each pair of exams fromI. See Requirement 1 for the discussion regarding which intersecting sets ofexams to use.Note that when the timeslots are pairwise disjoint, |B| = 1, and therefore|VB| = 1. In this case, for an intersecting subset I of exams, there is a logical405.1. TIMESLOT ASSIGNMENT SUBPROBLEMequivalence between among low up(0, 1,TI, VB) and alldifferent(TI). Onthe other hand, with overlapping timeslots, alldifferent(TI) is weaker log-ically than among low up(0, 1,TI, VB). Thus the alldifferent constraintsneed not be removed and it is possible that its implementation could stillprovide some extra propagative usefulness.The room assignment restriction for Requirement 6 is discussed in Sec-tion 5.2.CP of Requirement 7 (Temporal Precedence).To implement the requirement that exam E be scheduled after exam E′,include the constrainttE′ < tE .CP of Requirement 8 (Coupled Exams).For Requirement 8.1, to require exams E and E′ to have the same times-lot (τ(E) = τ(E′)), a CP equality constraint for their corresponding decisionvariables tE and tE′ is specified. The independent Requirement 8.2, requiresthat E and E′ have the same room (ρ(E) = ρ(E′)). As there is no corre-sponding decision variable in the timeslot assignment model for the roomassignments, it is possible that if Requirement 8.1 is not also specified, thenthe timeslot assignment found may not allow for a feasible room assignment.On the other hand, a more usual requirement would be that both Require-ment 8.1 and 8.2 are specified for the given pair of exams. In this case, theexams themselves could be considered as a single exam before the problemis specified (i.e., E ∪E′ replaces E and E′). Requirement 10 may then needto be adjusted as the two exams are now counted as one.CP of Requirement 9.1 (Separated Exams).For Requirement 9.1, to require the pair of exams E and E′ to be sched-uled during different timeslots (τ(E) ̸= τ(E′)), use a not equal constraintfor the corresponding decision variables (i.e., tE ̸= tE′).If provided a group of exams I ⊆ E rather than a pair, then impose theglobal constraint alldifferent(TI) (as with Requirement 1).Requirements 10 and 11 require more elaborate CP implementationsthan those already discussed, thus they will be described in detail in Sec-tion 5.1.4. Additionally, Requirements 9.2 and 12 are omitted from the415.1. TIMESLOT ASSIGNMENT SUBPROBLEMtimeslot assignment subproblem and will be covered in the room assign-ment subproblem in Section 5.2. Thus, we will skip to the two remainingrequirements that have straightforward CP implementations.CP of Requirement 13 (Frontload Large Exams).Implementing Requirement 13 involves counting the number of exams ofsize larger than c, that is all E ∈ E>c which are being scheduled in a timeslotlater than some [sk, fk] ∈ T .To implement this requirement, for each exam E ∈ E>c , let the CP in-dicator variable zE be used to indicate whether E is assigned to a timeslotlater than k, that is, whether the logical statementk < tEis true. The sum of the zE variables can then be minimized in an objectivefunction or constrained using inequalities.This constraint can be generalized for any set of exams of interest suchas exams from courses of a specific year of study.CP of Requirement 14.1 (Penalties).Let the penalties of the timeslots be collected in...ω = (ω1, . . . , ωm).Then for each exam E ∈ E, we define a new CP variable ωE using theglobal constraint element(tE ,...ω ,ωE) (see Definition 2.5). This constraintensures that ωE is bound to ωk if and only if tE is bound to k. Thus the sumof all ωE variables counts the total penalties contributed by each exam thatis assigned a penalized timeslot, which can then be added to a minimizingobjective function.5.1.4 CP of Multitasking Room CutsEnsuring that the timeslot assignment is room-assignable is non-trivialwhen there are multiple exams allowed in rooms. For the single-tasking case,we provided a necessary and sufficient constraint that guarantees a room-assignable timeslot assignment. However, when multi-tasking is in place,this condition may be too restrictive, as we mentioned in Example 5.1.Hence, we now seek a way to modify these requirements so that feasiblesolutions are not unnecessarily removed from the solution space. In whatfollows we introduce modifications that provide necessary (but not sufficient)425.1. TIMESLOT ASSIGNMENT SUBPROBLEMconditions to produce timeslot assignments that are room-assignable whenroom multi-tasking is allowed.CP of Requirement 10 (Room Task Limit).We treat Requirement 10 in a similar way as we have for Requirements 3and 4. In fact, Requirement 10 is a generalization of those requirements.Let k ∈ [m], q = qk, and j ∈ [0, q− 1]. The maximum number of concurrentexams of size greater than rj that can be scheduled during timeslot k isgiven byγ>j,k =∑R∈R>rj,kγk(R).Note if Requirements 3 and 4 are in force, then γk(R) = 1 for all R ∈ R>rj ,k,and hence γ>j,k =∣∣∣R>rj ,k∣∣∣.For a positive integer u, let E=u = {E ∈ E : ε(E) = u} be the set of examsof size u. Consider the (non-multi)-set of exam sizes U = {ε(E) : E ∈ E}.For each exam size u ∈ U and each k ∈ [m], introduce a CP variable nu,kthat is constrained to count the number of exams of size u assigned totimeslot k. By defining F ′u = {(k,nu,k) : k ∈ [m]}, the CP global constraintglobal cardinality(TE=u , F′u) (see Definition 2.6) ensures nu,k will equalthe desired count.Like Requirements 3 and 4, we need to use a sequence of constraints inorder that a timeslot assignment with this requirement is room-assignable.For each i ∈ [q] and each k ∈ [m], use the standard global constraint repre-senting the following sum of integer CP linear terms that counts the numberof exams of sizes in r(i− 1, i] that are assigned to timeslot k:n∗i,k =∑u∈Uu∈r(i−1,i]nu,k.Moreover, for j ∈ [0, q − 1],n>j,k =q∑i=j+1n∗i,kcounts the number of exams of sizes larger than rj that are assigned to thetimeslot. Note that n∗q,k = n>q−1,k and if i < q, then n∗i,k = n>i−1,k − n>i,k.The CP constraints for Requirement 10 are then,n>j,k ≤ γ>j,k for j ∈ [0, q − 1] and k ∈ [m]. (Constraints 10)435.1. TIMESLOT ASSIGNMENT SUBPROBLEMConstraints 10 must be necessarily satisfied by any feasible solution of theroom assignment problem for timeslot k. They need to be combined withthe constraints of Requirement 11 in order that a room with concurrentexams has enough space for the examinees of the exams.For future complexity calculations, note that for each u ∈ U and k ∈ [m]we introduced one new nu,k variable, thus resulting in m|U | new CP vari-ables. Each of these variables requires a defining global constraint, resultingin m|U | new global constraints. Altogether, if we ignore the intermediateCP variables, n∗i,k and n>i,k, that are simply sums of the nu,k CP variables,implementing Constraints 10 requires adding mq new constraints.CP of Requirement 11 (Room Multitasking Size).Let timeslot k be fixed and q = qk in the following discussion. Continuingwith the description of the CP implementation of Requirement 10, for a givenroom size ri, a necessary (linear) constraint for feasibility when concurrentexams are allowed is: ∑u∈Uu>riunu,k ≤∑R∈R>ri,kσk(R). (5.1)The left hand side represents the sum of the sizes of those exams of size largerthan ri scheduled in the timeslot, whereas the right hand side representsthe sum of the sizes of the rooms larger than ri. This constraint is notsufficient as it is possible that a collection of exams satisfies the constraintby collectively having enough room space but without a way to partitionthe rooms for the exams. For example, four exams of size 60 cannot fitinto three rooms of size 80 even though the constraint is satisfied. To beprecise, for each potential room size ri and exam size u, let πk(ri, u) be themaximum number of exams of size u that can be concurrent in rooms of sizeri during the timeslot:πk(ri, u) =∑R∈Rσk(R)=ri⌊riu⌋.The previous example provides the constraint that at most πk(80, 60) = 3exams of size 60 can be hosted by rooms of size 80. Note that πk(ri, 1) is justthe sum of the sizes of rooms of size ri that can be assigned exams duringthe timeslot.445.1. TIMESLOT ASSIGNMENT SUBPROBLEMLet u▽q be the minimum size of the exams of E>rq−1 .15 The first necessarycondition of Requirement 11 for a feasible solution of the timeslot assignmentproblem to be feasible for the room assignment problem requires that thenumber of exams assigned to the timeslot that are forced to be assigned tothe largest size rooms must not exceed the rooms’ collective capacity:n∗q,k ≤ πk(rq, u▽q ).Continuing now with smaller sized rooms, without any assumption ofroom assignments for exams, one can at least represent the cumulative re-maining space (residual capacity) of the size of rooms of a given minimumroom and exam size for use in other necessary conditions. This cumulativeremaining space is the difference between the sum of the sizes of rooms largerthan ri−1 during timeslot k and the sum of the number of persons in examsof size larger than ri−1 assigned to timeslot k. To this end, for i ∈ [q], wedefine the CP variable ci,k as:ci,k =∑R∈R>ri−1,kσk(R)−∑u∈Uu>ri−1unu,k.Consider all the exams of E>rq−2 \ E>rq−1 = {E ∈ E : ε(E) ∈ (rq−2, rq−1]}and u▽q−1 to be the minimum size of these exams. Exams from this setmust be assigned to rooms of size rq−1 or of size rq. None of the examsof size larger than rq−1 can be assigned to rooms of size rq−1 so they mustbe assigned to rooms of size rq. There are thus at most πk(rq−1, u▽q−1) ofthese exams assigned to rooms of size rq−1. The residual capacity for examsof size larger than rq−1 in rooms of size rq is given by cq,k. Thus theserooms can be assigned to at most⌊cq,ku▽q−1⌋of exams of size at most rq−1.Therefore, a necessary condition for the number of exams of size in the ranger(q − 2, q − 1] assigned to the timeslot is:n∗q−1,k ≤ πk(rq−1, u▽q−1) +⌊cq,ku▽q−1⌋.For i ∈ [q − 2], let u▽i be the minimum size of the exams of E>ri−1 \ E>ri .Now for such a fixed i, the exams from E>ri−1 \ E>ri must be assigned torooms whose sizes are from ri, . . . , rq. No exams of size larger than ri can15We may suppose that E>rq−1 is nonempty since otherwise we will just skip this stepand not produce a constraint for i = q− 1. This is also true for the remaining discussion.455.1. TIMESLOT ASSIGNMENT SUBPROBLEMbe assigned in rooms of size at most ri. Using the same reasoning as inthe last paragraph, rooms of size ri and of size rq can be assigned at mostπk(ri, u▽i ) +⌊cq,ku▽i⌋of these exams. For j = [i + 2, q − 1], we wish todetermine the residual capacity of the rooms of size rj for exams whosesizes are in the range r(j − 1, j]. Unfortunately, this number depends on afeasible room assignment. We will thus determine an upper bound, definedby c′j,k in the next paragraph, of the residual capacity of rooms of size rjfrom assigning exams of sizes in the range r(j − 1, j] for any feasible roomassignment. Given this upper bound, the rooms of size rj can be assignedat most⌊c′j,ku▽i⌋exams during the timeslot. Thus the number of exams ofsizes in the range r(i− 1, i] assigned to the timeslot must satisfy:n∗i,k ≤ πk(ri, u▽i ) +q∑j=i+1⌊c′j,ku▽i⌋. (5.2)We now turn to determining an expression for c′j,k. Since exams of sizesin the range (rq−1, rq] must be assigned to rooms of size rq, c′q,k = cq,k. Forj ∈ [q − 1], we determine c′j,k by first considering an upper bound, n′j,k, ofthe maximum number of exams whose sizes are in the range r(j − 1, j] thatcan be assigned to rooms of sizes larger than rj . Definen′j,k = minimum{n∗j,k,⌊cj+1,ku▽j⌋}(see Definition 2.10). There are only n∗j,k exams whose sizes are in the ranger(j − 1, j] and assigned to the timeslot, and so those assigned to rooms largerthan rj cannot exceed this number. On the other hand, the term⌊cj+1,ku▽j⌋is an upper bound for the maximum number of exams of sizes in the ranger(j − 1, j] that can be assigned to rooms of sizes larger than rj consideringthe residual capacity of the exams of size larger than rj that are assigned tothe timeslot. Thus n′j,k is an upper bound to the stated maximum.Define now n′′j,k = n∗j,k −n′j,k. Then n′′j,k is a lower bound on the fewestnumber of exams of sizes in the range r(j − 1, j] assigned to rooms of sizerj . Thus the remaining capacity of rooms of size rj from exams of sizes inthe range r(j − 1, j] is at most c′j,k = πk(rj , 1)− u▽j n′′j,k.For i ∈ [q], and k ∈ [m], the constraint given in (5.2) can be consideredthe most general form of a constraint of the CP implementation of Require-465.1. TIMESLOT ASSIGNMENT SUBPROBLEMment 11 if we allow the empty summand to be disregarded when i = q (i.e.,set the summand to 0). As well, if for any i, E>ri \ E>ri+1 = ∅, then the con-straint is disregarded altogether for all k ∈ [m]. We label the entire collectionof these constraints that includes the constraint given in (5.2) for each i andeach k as Constraints 11. Observe that for each j ∈ [q] and k ∈ [m] thereis one n′j,k CP variable and one cj,k CP variable. All other variables can beconsidered intermediary variables that simply store expressions. Thus ourimplementation of the mq constraints of Constraints 11 requires 2mq newCP variables along with their defining 2mq constraints16.Constraints 11 provide necessary constraints for a feasible solution of thetimeslot assignment problem to be room-assignable, however they may notbe sufficient. One of the issues that makes the constraints insufficient is thatthe terms c′i,k depend on terms ci,k that represent the residual capacity ofthe rooms of size at least ri, and are thus cumulative. It is possible (as inthe example provided) that they cannot be partitioned into the number ofparts provided by the constraints in a way that ensures exams of the sizebeing considered can be assigned to these rooms. Another issue is that thesize of the parts for each constraint, u▽i , does not guarantee there is enoughspace for the exams in E>ri−1 \ E>ri with sizes larger than u▽i . This secondissue will be demonstrated in the following example.Example 5.4 (Insufficiency of Room Multi-Tasking Constraints).Consider a set of exam sizes, {60, 90, 90, 150, 260, 260}, and a set of roomsizes, {100, 200, 600}. Suppose at most three exams can be scheduled in thelargest room, and only one exam can be scheduled in each of the smallerrooms. Fix k ∈ [m], and suppose we have a partial assignment where fortimeslot k, both exams of size 260 are being scheduled in the room of size600 and the exam of size 150 is being scheduled in the room of size 200.This partial assignment will bound the CP variables n∗i,k, ci,k, and c′i,kfor i ∈ {q − 1, q}, as well as n′q−1,k and n′′q−1,k.For the largest room size, rq = 600, we have two exams being assignedto timeslot k that need to be assigned to this room, thus n∗q,k = 2 andcq,k = 600− (260 + 260) = 80 = c′q,k.For the second largest room size, rq−1 = 200, there is one exam beingassigned to timeslot k that needs to be assigned to this room, therefore,n∗q−1,k = 1,cq−1,k =∑R∈R>rq−2,kσk(R)−∑u∈Uu>rq−2unu,k16It may be possible to optimize this further.475.1. TIMESLOT ASSIGNMENT SUBPROBLEM= (600 + 200)− (260 · 2 + 150) = 130,n′q−1,k = min{n∗q−1,k,⌊cq,k/u▽q−1⌋}= min{1, ⌊80/150⌋} = 0,n′′q−1,k = n∗q−1,k − n′q−1,k = 1− 0 = 1,c′q−1,k = πk(rq−1, 1)− u▽q−1n′′q−1,k = 200− 150 · 1 = 50.These calculations are summarized in Table 5.4.Table 5.4: Summary of the partial assignment of CP variables used in Ex-ample 5.4.i ri ExamSizesn∗i,k ci,k n′i,k n′′i,k c′i,kq 600 260,2602 80 - - 80q−1 200 150 1 130 0 1 50With these partial assignments, we will derive Constraints 11 for timeslotk and the next room size, when i = q−2 and rq−2 = 100. Since this is the lastroom size, the three remaining exam sizes, {60, 90, 90}, will be considered.Equations 5.1 and 5.2 become:∑u∈Uu>rq−3unu,k ≤∑R∈R>rq−3,kσk(R)60n60,k + 90n90,k + 150nu,k + 260nu,k ≤ 100 + 200 + 60060n60,k + 90n90,k + 150(1) + 260(2) ≤ 90060n60,k + 90n90,k ≤ 230andn∗q−2,k ≤ πk(rq−2, u▽q−2) +q∑j=(q−2)+1⌊c′j,ku▽q−2⌋= πk(100, 60) +(⌊5060⌋+⌊8060⌋)= 1 + (0 + 1)= 2.485.1. TIMESLOT ASSIGNMENT SUBPROBLEMBoth cuts allow for two of the three exams to be scheduled in timeslot k.However, if the two exams of size 90 are scheduled in this timeslot together,there will not be enough space in the 600 seat room (there are only 80 openseats), and only one of these exams can fit in the 100 seat room. Thus, theroom-cuts are not sufficient, specifically because of the value for u▽q−2.To fix these issues that lead to the room-cuts being insufficient, onecan tighten the constraints but in doing so risk infeasibility of the times-lot assignment problem or, at best, risk removing feasible solutions to bothproblems. The first issue mentioned is nontrivial to fix and was not, infact, an issue for our target problems. The second issue, illustrated in Ex-ample 5.4, can be fixed by replacing u▽i in the expressions with u△i , themaximum size of the exams of E>ri−1 \ E>ri . However, note that if u△q−2 = 90was used in Example 5.4, then the second cut would only allow for one examto be chosen, and thus would eliminate the possibility of the 60 person examand one of the 90 person exams being scheduled in the timeslot, which isactually a feasible solution. Therefore choosing this more restrictive valuefor the representative size of the exams of E>ri−1 \ E>ri could lead to infeasi-bilities. If an infeasibility is encountered, any number between u▽i and u△icould be used (e.g., the average of the size of the exams). In practice, weused u▽i and achieved feasible timeslot assignment solutions that were alsoroom-assignable.We refer to Constraints 10–11 as the room-cuts as they use the roomsizes to provide redundant constraints on the number of exams of each sizein any solution to an ESP.The timeslot assignment model does not incorporate Requirements 9.2,12 and 14.2, as this would require determining the room assignments of theexams. Their potential inclusion is discussed further in Section 5.3.5.1.5 CP of Hardship RequirementsThe CP implementations that measure and constrain (and/or minimize)the 3-in-27-hours, back-to-back, and 2-in-1-day hardships are significant con-tributions of this work. These implementations are described in what fol-lows.CP of Requirement 15 (Hardships).Given a subset D of exams, we wish to measure the spread of the timeslotassignments of exams from D. Let the start and finish times of the timeslotsbe collected in...s = (s1, . . . , sm) and...f = (f1, . . . , fm), respectively. For495.1. TIMESLOT ASSIGNMENT SUBPROBLEMeach exam E ∈ E, we define a new CP variable sE via the global constraintelement(tE ,...s , sE) which ensures that sE is bound to sk if and only iftE is bound to k (i.e., sE is stE ). Moreover, for each exam E ∈ E, usingelement(tE ,...f ,fE) defines fE so that fE is bound to fk if and only if tEis bound to k (i.e., fE is ftE ).A new CP decision variable s▽D is defined via the global constraintminimum(s▽D, {sE : E ∈ D})that represents the minimum start time of theintervals indexed by the variables assigned to exams from D. A simi-lar new CP decision variable f△D is defined through the global constraintmaximum(f△D , {fE : E ∈ D})(see Definition 2.9) that represents the max-imum finishing time of the intervals indexed by the variables assigned toexams from D. The CP variable lD, representing the length of the spreadof the timeslot assignments of exams from D , is thus the difference of deci-sion variables f△D − s▽D. Moreover, when a solution τ is found from bindingdecision variables t, f , s, f△D , s▽D and lD, the variable lD will be bound toℓ([s▽D,f△D ]).In order to measure the number of times persons are in at least w examsthat are assigned by τ to be within any d time units of the schedule (i.e.,|Hw,d|), we consider a subset of exams D such that |D| = w and such that∩D ̸= ∅. The number of persons writing all of the w exams in D is | ∩D|.Thus if lD ≤ d, then these w exams will be written within d time units andhence will contribute | ∩D| to |Hw,d|, but 0 otherwise.Since time is discretized, we define d+ to be the next time unit afterd. We use a combination of global constraints to map the decision variablelD to d if lD ≤ d, and to d+ otherwise. The CP variable iD,d defined bymaximum{d, minimum{lD, d+}} encodes this understanding since if lD ≤ d,then minimum{lD, d+} will have the value of lD and hence maximum{d, lD}will be d. On the other hand, if lD > d, then lD ≥ d+, so minimum{lD, d+}will be d+ and hence maximum{d, d+} will also be d+. Let ...d be a (d + 1)-tuple with the first d values as | ∩D| and the last value as 0. The new CPvariable hD,d defined by the global constraint element(iD,d,...d , hD,d)willbe equal to | ∩D| if lD ≤ d, and 0 otherwise.Finally, |Hw,d| is represented by the CP variable hw,d that is defined bythe standard global constraint representing the sum of integer CP variables:∑D⊆E|D|=whD,d.Note that this sum need only be taken over those D ⊆ E with |D| = w thathave ∩D ̸= ∅ since hD,d is zero otherwise.505.1. TIMESLOT ASSIGNMENT SUBPROBLEMNote also that this sum could have an exponential number of terms ifw ≈ 12 |E|. This, however, does not happen in practice since for a subset ofexams D of size w to have non-empty intersection means that some personis taking w exams and so typically this number is at most seven. Moreover,w is usually three, as in Example 4.1, and restricting the number of thistype for a variety of d’s will also restrict the hardships with w > 3 for largertime widths. Thus there are usually less than |E|3 terms in the sum. Aswell, the number of d’s used is conventionally small given the small numberof exams possible in a day and the fact that “hardship” loses its meaningwith larger d’s.Adding a CP constraint that sets hw,d to 0 for some w and d will en-sure that no (w, d)-hardships of τ will occur in a feasible solution. On theother hand, the variables hw,d can be weighted and added to a minimizingobjective function if hardships are necessary for a feasible solution to befound.Example 5.5 (Constraints for 3-in-27-hours Hardships).Recall Example 4.1 from Section 4.2.1, where student p1 had a 3-in-27-hours hardship. We will apply the CP of Requirement 15 to find thespread of the timeslot assignments for p1’s exams, which are being assignedto timeslots in B1 = {[17, 22], [24, 29], [31, 36], [38, 43], [65, 70]}.Let D = {E1, E2, E3} and suppose | ∩ D| = 1 (p1 is the only studentwriting all three exams). We have...s = (17, 24, 31, 38, 65, . . . , 566) and...f =(22, 29, 36, 43, 70, . . . , 571). Furthermore, tE1 = 1, tE2 = 3, and tE3 = 5.Thus the constraint element(tE1 ,...s , sE1) binds sE1 to the first element in...s , which is 17. Similarly the other element constraints bind the otherstart and finish time CP variables so that sE2 = 31, sE3 = 65, fE1 = 22,fE2 = 36, and fE3 = 70. Then the earliest start time and latest finishingtime ares▽D = minimum(s▽D, {sE : E ∈ D})= minimum{17, 31, 65} = 17andf△D = maximum(f△D , {fE : E ∈ D})= maximum{22, 36, 70} = 70.Thus the spread of the timeslot assignments for p1’s exams islD = ℓ([s▽D,f△D ]) = f△D − s▽D = 70− 17 = 53.515.1. TIMESLOT ASSIGNMENT SUBPROBLEMWe are concerned with 3-in-27-hours hardships, or equivalently, (3, 54)-hardships. Therefore, d = 54 and d+ = 55, hence,iD,d = maximum{d, minimum{lD, d+}}= maximum{54, minimum{lD, 55}}= maximum{54, 53}= 54.We have...d = (1, 1, . . . , 1, 0), which has 55 entries, so element(iD,d,...d , hD,d)assigns hD,d to the 54th element in...d , which is 1.Lastly, we can find hw,d, where w = |D| = 3, by counting the hardshipsfor all sets D, where D are the exams taken by a single student.Many ESPs have hardship constraints that involve each day of the sched-ule. Two common examples are back-to-back exam hardships and 2-in-1-dayexam hardships. When such constraints are required and the timeslots ofthe problem have a simple and regular structure, these hardships can be im-plemented in a more straightforward way than the above, as the followingexample illustrates. By adding timeslots so that the number of timeslotsper day is constant across all days (for UBCO this equates to adding the8:30 a.m. and 7:00 p.m. timeslots to Sunday) and setting the temporal roomsizes to zero for these timeslots, the index of a timeslot in Example 4.1 canbe used to determine the day index of the timeslot. Suppose there are stu-dents writing both E1, E2 ∈ E, that is E1 ∩ E2 ̸= ∅. Let D = {E1, E2} anddefine the boolean CP decision variable h′D,d to represent the truth value ofthe following logical expression that uses the exams’ corresponding timeslotvariables:(tE1 − 1)/4 = (tE2 − 1)/4 and |tE1 − tE2 | ≤ d.The expression uses the integer division and absolute value arithmetic func-tions of CP variables that are found in most CP solvers as well as the use ofthe truth value of a constraint arithmetically17. Since there are four times-lots per day, h′D,d indicates if E1 and E2 are assigned the same day indexand if they are within d timeslots from each other. Thus a back-to-back17If the number of timeslots per day is not constant then the integer division constraintis not accurate. One can handle this by adding the missing timeslots, as mentioned, oras another alternative the element constraint could be used where the input includes theCP variable tE and an array that maps each timeslot to its day. This constraint wouldthen produce the day of the timeslot being bound to tE .525.2. ROOM ASSIGNMENT SUBPROBLEMhardship occurs when h′D,1 is true, while a 2-in-1-day hardship occurs whenh′D,3 is true.For d at least one and less than the number of timeslots in a day, ifh′D,d is true, then we say a day d-hardship has occurred. Given p ∈ P , thenumber of day d-hardships occurring for person p can be represented by aCP variable dp,d defined by:dp,d =∑D⊆E(p)|D|=2h′D,d.The total number of day d-hardships is thus dd =∑p∈Pdp,d which can beminimized or constrained. It may be of interest as well to minimize orconstrain so as to load balance the day d-hardships between all exam writers.Example 5.6 (Constraints for Back-to-back and 2-in-1-day Hardships).Again, we will build this example from Example 4.1 in Section 4.2.1. Inthis case, both students p1 and p2 had a 2-in-1-day hardship. Taking d = 3and looking at D = {E1, E2}, a subset of the exams written by p1, usinginteger division (i.e., dividing and taking the floor of the result) we have,(tE1 − 1)/4 = (1− 1)/4 = 0 = (3− 1)/4 = (tE2 − 1)/4and|tE1 − tE2 | = |1− 3| = 2 < 3 = d.Thus h′D,3 = 1 since the above expressions are both true. Therefore themodel measures that this student has a 2-in-1-day hardship. Note that ifd = 1, then the second boolean expression above is false (2 ≰ 1). Thush′D,1 = 0, so the model does not count this student as having a back-to-backhardship.5.2 Room Assignment SubproblemThe room assignment subproblem is relatively straightforward comparedto the timeslot assignment subproblem. This is especially the case when thetimeslots are not allowed to overlap, and we will make this assumption inwhat follows. The necessary modifications will be discussed in the sectionCP of Requirement 6 if timeslots are allowed to overlap.For each of the timeslots [sk, fk], k ∈ [m], the room assignment subprob-lem finds room assignment ρk using the exams assigned to [sk, fk] by τ from535.2. ROOM ASSIGNMENT SUBPROBLEMa feasible solution of the timeslot assignment subproblem. In what follows,a timeslot [sk, fk] will be considered fixed and recall that Ek = τ−1([sk, fk])is the set of exams assigned to the timeslot. Moreover, let the rooms of R>0,kbe labeled R1, . . . , Rv.5.2.1 Primary Decision VariablesFor each E ∈ Ek, we define a CP integer-valued decision variable rEwhose domain is the set of indicies of the rooms, [v], with the understandingthat if rE is bound to i, then ρk(E) = Ri. For any subset D ⊆ Ek of exams,we let RD = {rE : E ∈ D} be the corresponding set of decision variables.5.2.2 CP of Elementary RequirementsRequirements 1–2 are satisfied by a feasible τ and thus have no corre-sponding constraints in this section. We now focus on the remaining ones.CP of Requirement 3 (Room Single-Tasking).Requirement 3 forces every exam to be assigned its own room. This can beachieved by imposing the global constraint alldifferent(REk , [v]).CP of Requirement 4 (Room Size).Requirement 4 ensures that the room assigned to an exam E ∈ Ek is theappropriate size. This is achieved by setting the domain of E equal to{i ∈ [v] : Ri ∈ R>ε(E)−1,k}.The constraint of this requirement may need to be relaxed if it is in-feasible given the input Ek. For i ∈ [v], let ...σ k = (σk(R1), . . . , σk(Rv)).For each E ∈ Ek, define a new CP variable σE via the global constraintelement(rE ,...σ k,σE) that enforces σE is bound to σk(Ri) if and only if rEis bound to i. In other words, σE is the size of the room which exam E isassigned to by ρ. Another CP decision variable xE is defined to capture theexcess in the assigned room via the constraint ε(E) ≤ σE +xE . The excessvariables can then be put in a weighted sum expression that is added to aminimized objective function.5.2.3 CP of Extended RequirementsRequirements 7, 13 and 15 are all fulfilled by a feasible τ , therefore weagain only focus on the remaining requirements.545.2. ROOM ASSIGNMENT SUBPROBLEMCP of Requirement 5 (Time and Room Specific).Requirement 5 is also straightforward to implement for the room assignmentpart. If E ∈ Ek and Q ⊆ R, the requirement ρ(E) ∈ Q is implemented byreducing the domain of rE to be {i : Ri ∈ Q} by requiring the CP variableto be not equal to each value in {i : Ri ∈ R \ Q}, or by other constraintprogramming domain reducing primitives.CP of Requirement 6 (Overlapping Timeslots).If timeslots are allowed to overlap, then the replacement of Requirement 3with this requirement for the room assignment problem ensures that a roomcannot be assigned to an exam from each of two overlapping distinct times-lots. In order to model this, several room assignment models have to besolved as a single model, or the extension to the timeslot assignment im-plementation should be used (see Section 5.3). To simplify the discus-sion, we will assume that the single model consists of all rE for all examsE ∈ E1∪· · ·∪Em = E. The constraints of this requirement then are rE ̸= rE′ ,for E ∈ Ek and E′ ∈ Ek′ of all k, k′ ∈ [m], k < k′, with [sk, fk]∩ [sk′ , fk′ ] ̸= ∅.CP of Requirement 8 (Coupled Exams).Requirement 8.1 is completely satisfied by a feasible solution to the timeslotassignment problem. Requirement 8.2 can be modeled for exams E, E′,using the constraint rE = rE′ .CP of Requirement 10 (Room Task Limit).The requirement is encoded in the set of triples Gk = {(i, 0, γk(Ri)) : i ∈[v]} for the global constraint global cardinality low up(REk , Gk). Thisconstraint ensures that, for each i ∈ [v], the number of decision variablesrE with E ∈ Ek that are bound to i is between 0 and γk(Ri). In otherwords, the number of exams assigned to room Ri is at most γk(Ri) duringthe timeslot. Note that Requirement 10 has the limitation that no othertimeslots overlap with [sk, fk], and therefore no exams assigned to othertimeslots will be assigned to rooms during [sk, fk].CP of Requirement 11 (Room Multitasking Size).For each E ∈ Ek and i ∈ [v], let bE,i be a CP decision variable that is oneif the constraint rE = i is true and zero otherwise. Thus bE,i indicates ifexam E is assigned to room Ri. This requirement can then be modeled by555.2. ROOM ASSIGNMENT SUBPROBLEMthe following constraints:∑E∈Ekε(E)bE,i ≤ σk(Ri) for each i ∈ [v].Alternatively we could use the bin packing capa global constraint tocount and constrain the number of students in exams being assigned roomRi.18CP of Requirement 12 (Mixed Duration).Let ∆k be the set of distinct exam durations for the exams assigned totimeslot k. For i ∈ [v] and d ∈ ∆k, we want to define yd,i to be the numberof exams with duration d assigned to room Ri during timeslot k. For eachduration d ∈ ∆k, we collect the exams of duration d in the set Dd and theCP variables representing the room assignments of the exams of durationd in the set RD . Let Md = {(i,yd,i) : i ∈ [v]}. The global constraintglobal cardinality(RDd ,Md) then ensures yd,i equals the desired count.For each i ∈ [v], the CP variableYi =∑d∈∆kminimum(1,yd,i)counts the number of different durations of exams being assigned to roomRi. Then adding ∑i∈[v](maximum(1,Yi)− 1) (5.3)to a minimizing objective function will penalize having multiple exams ofdifferent durations scheduled in one room.Initially it may seem unnecessary to use the maximum function in thesecond summation because the simpler term∑i∈[v] Yi counts the numberof different durations of exams being scheduled in each room. While thisexpression accurately counts the sum of the true number of different du-rations of exams in each room (the other expression does not count roomshaving only exams of the same duration), if this summation was used, thenthe solver may try to assign multiple exams to a single room in an at-tempt to empty another exam room. However, this is not the purpose ofthe constraint since we want the solver to treat empty rooms the same way18The room model is computationally inexpensive so adapting this modeling prac-tice was not deemed necessary. Furthermore, some solvers do not include thebin packing capa global constraint. Therefore, if using those solvers, the implementa-tion explained here would be necessary.565.3. EXTENDING THE TIMESLOT ASSIGNMENT SUBPROBLEMit treats rooms with only exams of the same duration. Using the expres-sion in (5.3) solves this problem. For example, if a room Rj ∈ R>0,k hasno exams being scheduled in it, then for all d ∈ ∆k, yd,j = 0, and henceYj = 0. Then maximum(1,Yj) − 1 = maximum(1, 0) − 1 = 0. Therefore 0will be added to the minimizing objective function. On the other hand, ifa room Rj′ ∈ R>0,k only hosts exams of a single duration, d′ ∈ ∆k, thenyd′,j′ = 1 and for all other d ∈ ∆k, yd,j′ = 0. Thus Yj′ = 1, and thereforemaximum(1,Yj′) − 1 = maximum(1, 1) − 1 = 0. Hence, again 0 will be addedto the minimizing objective function. Altogether, Rj and Rj′ will have thesame impact on the objective function.CP of Requirement 14.2 (Penalties).For each room Ri with a positive penalty ωi, where i ∈ [v], the followingsum counts the total penalties contributed by exams in timeslot k beingassigned to room Ri: ∑E∈Ekωi · bE,i.Room penalties can then be minimized by summing this expression for allrooms and including the sum in the minimizing objective function.Note that this constraint could also be modeled like the version for thetimeslot penalties in Section 5.1.3 using the element constraint.5.3 Extending the Timeslot AssignmentSubproblemDepending on the size of the input data (i.e., the sizes of the sets T , Eand R), it may be possible to solve the timeslot assignment subproblem andall of the room assignment subproblems simultaneously through the use ofthe global constraint bin packing capa (see Definition 2.4). A bin packingconstraint requires items to be packed (i.e., assigned) into bins so that allitems get a bin and the sum of the weights of the items of a bin does notexceed the capacity of the bin. The correspondence between the ESP and abin packing constraint has the exams as items, the rooms as bins, and thenumber of examinees as the weight of an item. Since the assignment of anexam to a room depends on a timeslot, this unified model specifies a binpacking constraint for each of the timeslots. To get around the requirementof the bin packing constraint that each item must be packed into a bin, avirtual room is added to each of the constraint’s bins with a new uniquevalue, v∗, for the virtual room’s index. Additional constraints will ensure575.3. EXTENDING THE TIMESLOT ASSIGNMENT SUBPROBLEMthat an exam that is scheduled in timeslot k is not scheduled in the virtualroom in timeslot k, and vice versa. The virtual room has unlimited capacityin all timeslots so as to allow any combination of exams to be packed into itin any particular timeslot, thereby not restricting the exams to use actualrooms if they are not assigned to the timeslot.To be more precise, the model includes, for each exam E ∈ E, the previ-ously described timeslot assignment primary decision variable tE , as well asroom assignment primary decision variables rE,k, where k ∈ [m] and rE,kis a modified room assignment primary decision variable rE for timeslot k.Each rE,k has its domain extended to include v∗, the index of the virtualroom.If an exam E is assigned timeslot k, then the exam is not assigned thevirtual room in timeslot k, and vice versa. This is modeled through the setof constraintstE = k if and only if rE,k ̸= v∗, for all k ∈ [m], (5.4)which are easily expressed in CP solvers. We store each pair of the index ofa bin (i.e., room) along with its capacity (i.e., room size) in the setβk ={(1, σk(R1)), . . . ,(v, σk(Rv))} ∪ {(v∗,∞)}.Moreover, each pair of a bin (i.e., room) assignment decision variable foritem (i.e., exam) E at timeslot k along with the item’s weight (i.e., numberof examinees of E) is stored in the set ιk = {(rE,k, ε(E)) : E ∈ E}. Fork ∈ [m], the constraint bin packing capa(βk, ιk) then ensures that all theexams get assigned to rooms in timeslot k without exceeding any room’ssize. Combined with (5.4), an exam gets assigned to an actual room intimeslot k if and only if the exam is assigned to timeslot k.The collection of all of these m global constraints along with the m|E|constraints from (5.4) thus implement Requirement 11.The rE,k variables can be reused to implement Requirement 10 in theglobal constraint of its CP implementation in Section 5.2. Each of the mtimeslots requires a single global constraint and has at most |R| new CPcounter variables.We refer to this CP implementation of Requirement 10–11 as the room-packings constraints.Note that for our purposes we did not include Requirements 12 and14.2 in the room-packings version of the timeslot assignment model to allowfor fair comparisons between the room-cuts and room-packings implemen-tations. We did however implement CP constraints for Requirements 5 and585.4. REMARKS ON USAGE OF IMPLEMENTATIONS8.2. These requirements have similar implementations as described in Sec-tion 5.2 but use the rE,k CP variables.5.4 Remarks on Usage of ImplementationsIn this section, we discuss several possible scenarios regarding the use ofthe CP implementations of the requirements of the ESP. A few factors gointo deciding which scenario to use.First, if a university has many room-related requirements, such as Re-quirements 5, 9.2, 12, and 14.2, then even if the room-cuts implementa-tion is able to assign exams to timeslots so that each exam will have anappropriately-sized room available (i.e., τ is room-assignable), the times-lot assignment solution still may not lead to a feasible room assignment(e.g., two exams requesting the same room may be scheduled at the sametime). However, some of these requirements could be handled through pre-processing. For example, in the UBCO datasets there are groups of ex-ams needing computer labs. To ensure that the room-cuts implementationwould produce solutions that have feasible room assignments, we imposedadditional Separate Exam requirements (Requirement 9.1) on the examsneeding computer labs so that these exams would not be assigned the sametimeslot. This ensured that each exam could be scheduled in a computerlab.Pre-processing may not be able to handle other room-related restrictionsthough. In this case the requirements would need to be included during thetimeslot assignment phase and the room-packings implementation wouldneed to be used. However, we did not encounter this issue with the ITC2007 datasets nor the UBCO datasets. Additionally, many of the room-related constraints (e.g., room penalties) are soft and are considered lessimportant than the timeslot assignment soft constraints (e.g., back-to-backhardships). Note that Requirement 8 (Coupled Exams) may also seem topresent a potential problem, but it can be handled by amalgamating theexams before the variables in the timeslot assignment model are created,which we did for the UBCO datasets.Assuming these requirements can all be satisfied easily (which is whatwe will assume for the remainder of this section), then the next consider-ation is whether rooms are prohibited from hosting concurrent exams (Re-quirement 3–4) or not (Requirements 10–11). If the rooms are prohibitedfrom hosting concurrent exams and only the CP implementation of Require-ments 3–4 are included, then Theorem 5.3 ensures that any feasible solution595.4. REMARKS ON USAGE OF IMPLEMENTATIONSTable 5.5: Implementation metrics of model options for concurrent exams.Model OptionTimeslot Assignment Implementation# Variables # Non-Global # Globalroom-cuts (|U |+ 2q)m (3q)m |U |mroom-packings (|E|+ |R|)m |E|m 2mfrom the timeslot assignment model will be room-assignable. Thus room-packings are not required.When rooms are allowed to host concurrent exams, that is, Require-ments 10–11 are included, room-cuts or room-packings must be specifiedin the timeslot assignment implementation. An analysis of the sizes of theinputs to the problem might be required to determine whether to use room-cuts, room-packings or both. The sizes of the inputs include the numberof:1. timeslots, m,2. exams, |E|,3. different sizes of exams, |U |,4. rooms, |R|, and5. maximum different sizes of rooms, q = maxk∈[m]qk.Table 5.5 lists the number of variables, non-global constraints, and globalconstraints required by each implementation option. The other constraintsof the timeslot assignment implementation are not considered.To compare different cells of Table 5.5, observe that |U | ≤ |E| and q ≤|R|. If room-cuts are used alone, then the room assignment implementationmust be run for each timeslot. Also, the room-cuts are necessary but notsufficient for a feasible solution of the timeslot assignment implementation,without the room-packings, to be room-assignable. The real-world data setswe have encountered (i.e., the UBCO datasets, see Section 6.3.1), however,have shown to always provide room-assignable solutions. Moreover, if there605.5. SEARCH PHASESare many rooms of small sizes to choose from, only larger rooms need be usedin the room-cuts so that the number of distinct room sizes can be reducedto be much smaller than 12 |R| and 13 |E|.5.5 Search PhasesAs mentioned in Section 2.5, CP Optimizer allows users to control var-ious parameters used in the branch-and-bound search tree. In addition tocontrolling the type of search (e.g., depth-first search or restart search),users can specify which variables and values to search on first through searchphases.Over the course of this thesis and research project many search phaseswere tested. The first search phase we created simply included the CPvariables representing the timeslot assignment of each exam E, that is, tE .Using this search phase, CP Optimizer branches on these variables beforeany others in the search process. This search phase worked well for findingfeasible solutions within an acceptable amount of time. In fact, withoutusing this search phase, CP Optimizer was unable to find an initial feasiblesolution (within a significant time limit).We also explored other search strategies, such as branching on the tEvariables corresponding to exams with the most students, or correspondingto the exams involved in the most potential student conflicts (i.e., examswith many students in common with other exams). Both of these effortsproved to be less effective than the first search phase mentioned. Lastly,in an attempt to quickly reduce the number of back-to-back hardships, wecreated a specific order for choosing the values in the tE variables’ domainsto branch on first. To do so, for each pair of exams E and E′, we found thenumber of students in common between the two exams, |E ∩E′|, and storedthis information. If |E ∩ E′| > 0, then E and E′ were called neighbouringexams. For each exam E and each timeslot k in tE ’s domain, a weight fork was determined based on whether any of E’s neighbouring exams werebound to timeslots adjacent to k (i.e., k + 1 and k − 1). At each branchin the search tree, CP Optimizer would then choose the timeslots with thesmallest weights. Our hope was that CP Optimizer would bound the tEvariables to the values that would later lead to the fewest number of back-to-backs. This search could have been optimized further, but upon initialinvestigation the first search phase strategy still performed better.When including the room-packings constraints in the timeslot assign-ment model, we also tried using CP Optimizer’s default search phase with615.5. SEARCH PHASESthe room packing variables of each exam, rE,i, as a secondary search phase.Once again however, the first search phase specified still yielded better so-lutions.Altogether, there are many search parameters to vary in CP Optimizerand different structured search phases are an area that could be exploredin more detail in future work. Furthermore, other search parameters couldalso be investigated in more depth, such as specifying the inference level ofthe global CP constraints, and changing the search type.62Chapter 6Experiments and ResultsThe results of this work fall into two categories. First, we discuss thedetails of the final exam schedules we produced for UBCO for the 2021/2022academic year in Section 6.1. Second, we compare and contrast two con-figurations of the timeslot assignment model: the room-cuts model and theroom-packings model. The room-cuts model uses the CP implementation ofRequirements 10–11 for the timeslot assignment model as explained in Sec-tion 5.1.4 (the room-cuts). The room-packings model implements Require-ments 10–11 in the timeslot assignment model as described in Section 5.3(the room-packings constraints). We test these models on real-world UBCOdata and benchmark datasets commonly used in the exam scheduling aca-demic community. When evaluating a large number of data sets, comparingsolvers and techniques becomes complicated. The data obtained by evalu-ating each algorithm’s solve time, memory usage, or evaluation function canbe overwhelming when there is a large numbers of instances, such as thoseproduced through randomization in our experiments. A standard approachto focus the analysis of this data is to produce performance profiles, whichwe do here. In Section 6.2, we will provide a description of performanceprofiles in preparation for the experiments conducted in Section 6.3.6.1 UBCO 2021/2022 Exam SchedulesAs part of the research project, the DOPT Team produced the examschedules for both terms in the 2021/2022 academic year. The ESP atUBCO includes a few exceptional scenarios that require special handling, aslisted below.Cross-listed and Common Exams: A course that has different titlesbecause it is shared between different programs is called cross-listed. Cross-listed courses are required to have their exams scheduled at the same timeand location. For such courses, the data of their exams are merged during apre-processing stage so that the merged exam is the union of the cross-listed636.1. UBCO 2021/2022 EXAM SCHEDULESexams. The merged exam is treated as a single exam both in the timeslotand room assignment models. Though this scenario could be handled by im-plementing Requirement 8 (Coupled Exams), we chose to merge the examsso that when implementing Requirements 10 and 11 (Room Task Limit andRoom Multitasking Size) in the timeslot assignment model, the cumulativesize of the grouped exams is accounted for.A course with multiple sections but a common exam is treated similarly.In this case, all the exams of the sections must be scheduled in the sameroom at the same time.Double-Seating Requirement: Every room’s effective size is half of itstrue capacity, excluding the gym. We call this the double-seating require-ment. The requirement is implemented through appropriate σ input data.Gym: The gym is a special room. First of all, it is the only room thatdoes not require double-seating – its effective size is the true capacity ofthe room. Furthermore, while most rooms require single-tasking, the gymuses multi-tasking, allowing at most three exams to take place concurrently.The use of the gym is also minimized, since it is a large room and it is notdesirable to have multiple exams take place in the same location.These scenarios were all handled when generating the schedules. Char-acteristics of the datasets used to create the exam schedules can be foundin Appendix A (these datasets will also be used in the experiments in Sec-tion 6.3.1).Table 6.1 summarizes the important features of the exam schedules weproduced.19 Some qualities to highlight include:− zero student hardships (3-in-27-hours hardships) for both terms,20− lower numbers of students having back-to-back exams and two examsin one day compared to previous years, and− no instances of exams being scheduled in rooms that did not allow for“double-seating” (twice as many seats as students), unless otherwiserequested.19Some of the metrics in the table may have slightly altered after the first publicationof the schedule due to changes in exam delivery, late requests, and changes in studentenrollment.20As mentioned in Section 3, this is one of the main priorities for an exam schedule atUBCO.646.2. PERFORMANCE PROFILESTable 6.1: UBCO exam schedule metrics for the 2021/2022 academic year.Number of: Term 1 Term 2Students with 3-in-27-hours hardships 0 0Students with back-to-back hardships 28 19Students with multiple back-to-back hardships 0 0Students with 2-in-1-day hardships 693 589Students with multiple 2-in-1-day hardships 7 0Exams scheduled in the gym 19 38Additionally, for the first time, the exam schedule was structured in sucha way that the use of the gym for exams was limited. For the second term ofWinter 2021, the gym was only used for 23 timeslots, allowing for more than25 timeslots where the gym could be used by students for physical activity.Furthermore, using results from our CP model, we were able to show thatreducing the use of the gym would not affect the number of exams beingscheduled towards the end of the exam period.6.2 Performance ProfilesIn this section, we will redefine the following symbols to match the stan-dard literature on performance profiles: ρ and τ . These new definitions willbe used throughout this chapter.A performance profile for a solver is the cumulative distribution func-tion of a performance metric [30]. A plot of the performance profiles revealsimportant characteristics of the performance of the solvers in question, suchas the percentage of instances solved, and a comparison of the quality of theperformance of various solvers. In this section, we will describe how to con-struct a cumulative distribution function based on an evaluation function.The performance metric that we are concerned with in our experiments isthe objective function’s value.Let I be the set of problem instances and S be the set of solvers (orimplementations of a single solver). Let nI = |I| be the number of probleminstances and nS = |S| be the number of solvers. For each instance i ∈ I andeach solver s ∈ S, letei,s = evaluation function value from instance i using solver s,656.2. PERFORMANCE PROFILESbe the performance metric of interest.21 The performance ratiori,s =ei,smin{ei,t : t ∈ S}compares the performance of solver s on instance i with the best performanceof any solver on this instance. We choose a parameter rM ≥ ri,s for all i ∈ I,s ∈ S, where ri,s = rM if and only if solver s does not solve instance i.Note that Dolan and More´ show that the choice for rM does not impact theperformance evaluation.We are concerned with an overall assessment of how solver s performsacross all instances. To do so, defineρs(τ) =1nI|{i ∈ I : ri,s ≤ τ}|,which is the probability for solver s that a performance ratio ri,s is withina factor of τ ∈ R of the best possible ratio. Thus ρs(τ) is the cumulativedistribution function for the performance ratio (i.e., the performance profilefor solver s).One value of interest in a performance profile is ρs(1). This value revealsthe probability that solver s will have the best performance metric for aninstance compared to all other solvers (i.e., the probability that solver sis within a factor of 1 of the best solver). Thus, if we are only concernedwith which solver wins overall, then this value will be the most important.Generally, with a large problem set that accurately represents most probleminstances, solvers with a large probability ρs(τ) for smaller values of τ aredesired.It is valuable to know the probability that solver s solves a problem,which is given byρ∗s = limτ→r−Mρs(τ).Note that ρs(rM ) = 1 for all solvers because of the choice of rM , hence whywe use the left limit in determining ρ∗s. Thus, if we are concerned with areliable solver that will have the greatest chances of finding a solution, ρ∗s isthe value to consider.For more details on performance profiles and their characteristics, referto [30].21The performance metric can vary depending on the problem at hand. For instance, itis common to use the solving time instead of an evaluation function value.666.3. ROOM-CUTS VERSUS ROOM-PACKINGS6.3 Room-Cuts versus Room-PackingsThe room-cuts and room-packings models are distinguishing contribu-tions of this thesis. We now compare these two approaches.In CP Optimizer, the solver used in our experiments, randomization isapplied in some search strategies. Thus, changing the seed parameter of thesolver will alter the search procedure and lead to different results betweendifferent seeds. Hence, providing various seeds for a particular dataset pro-duces multiple problem instances.22 Furthermore, each implementation’sperformance varies based on characteristics of the input data. Therefore,to gain insight on when to choose each implementation, we will separatelyevaluate each implementation’s performance on each dataset using 60 prob-lem instances (i.e., seeds). This will be done by way of performance profile,where one performance profile will be generated per dataset.All experiments were conducted on an Intel i9-10900K @ 3.70GHz (10cores–20 threads/workers) with 32.0 GB memory using IBM ILOG CPLEXOptimization Studio 22.1.0.0. There are three experiment configurations.Each configuration has the following settings for the timeslot assignmentmodel:− Search Type = Restart,− Restart Fail Limit = 20,− Search Phase = CP Optimizer default search phase with the tE (times-lot assignment for exam E) variables, and− Time limit = 600 seconds.23The room assignment model, which uses the solution from the timeslot as-signment model and is run once for each timeslot, has the following settings:− Search Type = Default (Restart),− Restart Fail Limit = Default (100),− Search Phase = None specified, and22Technically these problem instances are search instances, but given the limited numberof real-world datasets, we considered the seed as part of the input data.23We chose this time limit after testing with larger and smaller time limits. The timelimit did not appear to drastically change the model behaviour. Therefore, the middletime limit was chosen to allow for representative objective function values while providinga large enough sample size, given restricted resources, for an accurate representation ofeach model’s behaviour.676.3. ROOM-CUTS VERSUS ROOM-PACKINGS− Time limit = 60 seconds.24The configurations then differ in terms of which representative examsize (i.e., the size of the exams of E>ri−1 \ E>ri , ui) is used in the room-cutsconstraints in the timeslot assignment model. The configurations are:− Configuration A: u▽i ,− Configuration B: u△i , and− Configuration C: u▽i + (u△i − u▽i ) · 0.75.We will refer to the room-cuts approach as solver sc, and the room-packings approach as solver sp. In the performance profiles, if the room as-signment subproblem was infeasible (i.e., the room’s capacity was exceededby some exam),25 then we regard this as the approach was not able to solvethat problem instance (though it technically did find a solution in the times-lot assignment model). Only the feasible solutions contributed to calculatingthe average and minimum evaluation function values. In Section 6.3.2, wewill discuss a slight variation, which allows for the room capacity constraintto be softened for particular datasets.6.3.1 UBCOTo compare the room-cuts and room-packings approaches for UBCO,we used two datasets, UBCO 2021/2022 Term 1 and Term 2, each with twovariations, Version 1 and 2, resulting in a total of four datasets. Version 1refers to the original data as provided by UBCO. Version 2 is a modified ver-sion of the dataset where all exams require rooms. In the original datasets,many exams were held online due to the COVID-19 pandemic. Since themain issue we faced while modeling revolved around room assignments, wedecided to test a modified version of the dataset to get a more accurate pic-ture of how the model will perform post-pandemic. Statistics about thesedatasets can be found in Appendix A.UBCO’s examination period follows the structure shown in Example 4.1.Configuration A is used for all experiments in this section and all of theconstraints required by UBCO are included. Specifically, the exceptionalscenarios mentioned in Section 6.1 are incorporated, except we do not mini-mize the use of the gym. The list of constraints for the timeslot assignment24For most instances, optimality was quickly achieved and the room assignment modeldid not use the full time limit.25The room assignment model was never infeasible for other reasons.686.3. ROOM-CUTS VERSUS ROOM-PACKINGSmodel and the room assignment model are shown in Tables 6.2 and 6.3, re-spectively. Besides the primary goal of having zero 3-in-27-hours hardshipsand meeting the double-seating requirement, the objective for the runs is tominimize back-to-back hardships (i.e., d1). In practice, we found that theCP model performs best when only one term is included in the objectivefunction, hence why we only minimize back-to-backs.Table 6.2: List of constraints included in the timeslot assignment model forthe experiments with the UBCO 2021/2022 datasets.Requirement Description ConstraintType1 No student/instructor can havemore than one exam per timeslotHard2 Exam duration requirementis met implicitly by input dataHard5 Set domain for the exam timeslotbased on instructor requestsHard8 Cross-listed or common exams requiredto be assigned the same timeslotHard9.1 Certain groups of exams cannot bescheduled in the same timeslotHard10, 11 Room-cuts (necessary conditionto satisfy room constraints)Optional,Hard10, 11 Room-packings Optional,Hard15 Zero 3-in-27-hours hardships(h3,54 = 0)Hard15 Minimize back-to-back hardships (d1) OptimizedIn order to analyze the performance of the two approaches, we computedthe implementation metrics of model options (recall Table 5.5). These com-696.3. ROOM-CUTS VERSUS ROOM-PACKINGSTable 6.3: List of constraints included in the room assignment model for theexperiments with the UBCO 2021/2022 datasets.Requirement Description ConstraintType3, 10 Gym hosts at most three exams;all other rooms host at most one examHard4, 11 Number of students writing examsscheduled in a room is at most the effectiveroom sizeaHard5 Set domain for the exam roombased on instructor requestsHardaThe constraint is softened for exams with specific room requests.putations can be found in Table 6.4. For each dataset, the model when usingthe room-cuts approach has fewer variables and constraints than when usingthe room-packings approach. The Version 2 datasets have larger implemen-tation metrics in terms of the number of variables and global constraintswhen using the room-cuts approach compared with the corresponding Ver-sion 1 datasets. On the other hand, for the room-packings approach, thenumber of non-global constraints decreases while the other metrics remainunchanged. Note that the Version 2 datasets have less exams. This is be-cause the cross-listed or common exams that were online in Version 1 nowrequire rooms. Therefore, the second version has more Requirement 8.2constraints to ensure that all cross-listed and common exams will be in thesame room as their coupled exam. Since we amalgamate exams involvedin these constraints, more exams are combined into one, resulting in fewerexams. This also increases the number of exam sizes.706.3. ROOM-CUTS VERSUS ROOM-PACKINGSTable 6.4: Calculations of implementation metrics of model options with multitasking rooms for the UBCO2021/2022 datasets. These calculations are based on the ones listed in Table 5.5. The leftmost column, P,corresponds to the dataset (e.g., T1V1 is Term 1 Version 1). The columns labeled “Cut” and “Pack” correspondto the results from the room-cuts and room-packings approaches, respectively.# Variables #Non-Global# Global Total #ConstraintsP |E| |R| m |U | q Cut Pack Cut Pack Cut Pack Cut PackT1V1 358 45 44 119 30 7876 17732 3960 15752 5236 88 9196 15840T1V2 342 45 44 172 30 10208 17028 3960 15048 7568 88 11528 15136T2V1 378 47 46 135 31 9062 19550 4278 17388 6210 92 10488 17480T2V2 369 47 46 169 31 10626 19136 4278 16974 7774 92 12052 17066716.3. ROOM-CUTS VERSUS ROOM-PACKINGSTable 6.5: Statistics of evaluation functions for UBCO 2021/2022 datasets. The number of CP variables andconstraints counts all variables and constraints used in the timeslot assignment model. The leftmost column, P,corresponds to the dataset (e.g., T1V1 is Term 1 Version 1). EF indicates the Evaluation Function, which inthis case is the number of back-to-backs. The best average and minimum evaluation functions achieved for thedataset are bolded. The column “# Room Inf.” refers to the number of instances that were solved in the timeslotassignment model but did not produce feasible room assignment solutions. The column “Avg. # Fails” refers tothe average number of fails from the search in CP Optimizer. The columns labeled “Cut” and “Pack” correspondto the results from the room-cuts and room-packings approaches, respectively.Total # ofall CP vari-ablesTotal # ofall CP Con-straintsAvg. # Fails #RoomInf.Avg. EF Min. EFP Cut Pack Cut Pack Cut Pack Cut Pack Cut Pack Cut PackT1V1 30543 33880 53466 70099 255853 209283 0 0 119 124 49 51T1V2 32658 39398 52950 81530 191126 154450 0 0 170 214 70 92T2V1 35027 42188 55039 84536 252838 193755 0 0 60 71 9 17T2V2 36688 47655 54302 95797 209134 147868 0 0 79 123 31 35726.3. ROOM-CUTS VERSUS ROOM-PACKINGSTable 6.5 lists the objective function values (i.e., number of back-to-backs) for the experiments. We can see that the room-cuts approach achievesbetter objective function values compared with the room-packings approach.Note that the number of CP variables and constraints is not always consis-tent with the calculations in Table 6.4 (for the room-cuts approach, thenumber of constraints should be larger for the Version 2 datasets than theVersion 1 datasets, and the opposite should occur when using the room-packings approach). However, recall that the calculations omitted the inter-mediate variables, whereas the counts provided by CP Optimizer include allvariables. Another observation to note is that the room-cuts approach hasa higher average number of fails for each dataset (a failure is when a branchin the CP Optimizer search tree failed to find a feasible solution based onprevious assignments in the branch).The performance profiles from these experiments are shown in Figures 6.1-6.4. In these figures, we can see that for all four datasets, both approachesare able to solve all problem instances. For Term 1 Version 2 and Term 2 Ver-sion 1 and 2, room-cuts outperforms room-packings since ρsc(τ) ≥ ρsp(τ)for all τ . Furthermore, for all datasets, ρsc(1) > ρsp(1), hence there isa higher probability of room-cuts being the superior approach for all in-stances. For Version 1, room-cuts does slightly better than room-packings,though this is by a fairly small margin, especially for Term 1 (ρsc(1) ≈ 0.55and ρsp(1) ≈ 0.5). This margin increases for Version 2, where room-cuts isstill the winner, but for small values of τ there is a greater difference be-tween the performance profiles of the two implementations ( ρsc(1) ≈ 0.6 andρsp(1) ≈ 0.5). The differences in implementation metrics likely has a role toplay here. Referring back to Table 6.4, more cuts are being generated in theroom-cuts model for the Version 2 data, which may help eliminate poor solu-tions by reducing the search space. Alternatively, the room-packings modelhas fewer variables and constraints, which could lead to a larger search space.This illustrates the difficulty in finding the perfect balance in the number ofconstraints. If the problem is over-constrained, then it may be difficult forthe solver to find a feasible solution. On the other hand, if the problem isunder-constrained, then the solver may struggle to find a good solution.Lastly, for Term 1, both distribution functions of both versions reach1 before τ = 4, whereas for Term 2, the distribution functions for room-packings do not reach 1 until τ > 5. Thus, for the Term 2 data, the room-cuts approaches objective values are smaller than that of the room-packingsapproaches by a greater factor in Term 2 compared to Term 1.In conclusion, room-cuts appear to perform better than room-packings,especially when there are more exams requiring rooms (i.e., Version 2).736.3. ROOM-CUTS VERSUS ROOM-PACKINGS00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on UBCO 2021/2022 Term 1 Version 1room‐cutsroom‐packingsFigure 6.1: Performance profile on the UBCO 2021/2022 Term 1 Version 1Dataset using Configuration A.00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on UBCO 2021/2022 Term 1 Version 2room‐cutsroom‐packingsFigure 6.2: Performance profile on the UBCO 2021/2022 Term 1 Version 2Dataset using Configuration A.746.3. ROOM-CUTS VERSUS ROOM-PACKINGS00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on UBCO 2021/2022 Term 2 Version 1room‐cutsroom‐packingsFigure 6.3: Performance profile on the UBCO 2021/2022 Term 2 Version 1Dataset using Configuration A.00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on UBCO 2021/2022 Term 2 Version 2room‐cutsroom‐packingsFigure 6.4: Performance profile on the UBCO 2021/2022 Term 2 Version 2Dataset using Configuration A.756.3. ROOM-CUTS VERSUS ROOM-PACKINGS6.3.2 ITC 2007To further test our models we ran experiments using the 12 ITC 2007datasets, which are common benchmarks to use when testing examinationscheduling systems. They are available for download from [3]. Also availableare the current best known solutions and their evaluation functions. Therules for the ITC 2007 examination timetabling track can be found in thepaper by McMullan et al. [56]. Note that we do not abide by the rulespertaining to computation time. Our main goal is to provide a comparisonof the room-cuts and room-packings approaches, not to achieve new boundson the evaluation functions. However, we do include all of the constraintsfor the ITC 2007 problems, which are summarized in Tables 6.6 and 6.7.Constraints of note in the timeslot assignment model include the additionof Requirements 7 (i.e., the “after” constraint in the ITC 2007 problemdescription), 13, 14.1, and a new variation of Requirement 15 (Hardships).This new hardship requirement evaluates the “period-spread” of pairs ofstudents’ exams, that is, it measures the occurrence of a student havingtwo exams within a specified number of timeslots, and minimizes this value.With our formulation of hardships, this is defined as minimizing h2,d, whered is a function of an input data parameter. As an aside, Requirements 8and 9 are referred to as the “exam-coincidence” and “exclusive” constraints,respectively, in the ITC 2007 problem description. Constraints of note in theroom assignment model include Requirement 9.2 (i.e., the “room-exclusive”constraint in the ITC 2007 problem description), and Requirement 12. Thenumber of exams that can be scheduled in a room is not restricted, thoughthe room capacity must not be exceeded. Statistics about the datasets (e.g.,the weightings for soft constraints), can be found in Appendix A.The evaluation function (EF) for these datasets is a function of the softconstraints (related to rooms and/or timeslots), which are each provided aweight in the dataset. The objective function for the timeslot assignmentmodel is the portion of the evaluation function pertaining to timeslot assign-ments (i.e., frontload, timeslot penalties, period-spread violations, back-to-backs, and 2-in-1s). However, the room-related portion of the evaluationfunction (i.e., mixed-duration and room penalties) cannot be minimized inthe timeslot assignment model unless the room-packings approach is used(since room assignments would need to be known), which would lead toan unfair comparison between the two approaches. Thus, the room-relatedpart of the evaluation function is the objective function in the room assign-ment model, but is omitted from the timeslot assignment model. In doingso, there is limited optimization that the room assignment model can per-766.3. ROOM-CUTS VERSUS ROOM-PACKINGSform, since it is subject to the assignments made in the timeslot assignmentmodel. For some datasets, the room-related penalties are small so this is notan issue, while for others, room-related penalties contribute noticeably tothe objective function. Since there is no room assignment optimization byeither approach in the timeslot assignment model, we assume that neitherapproach has an advantage. That being said, this leads to higher evalua-tion function values and a worse performance when compared to the currentbest evaluation functions in the literature (see the rightmost three columnsof Table 6.9).There is a solution validator tool available at [66]. The validator ensuresthat all constraints are being satisfied and computes the evaluation functionof a solution. We tested every solution with this tool. Two of the datasetshave infeasible parameters for some constraints.26 With the exception ofthese datasets, all datasets were validated with the tool.Table 6.8 shows the calculations of the implementation metrics of modeloptions and the values used in these calculations. As with the UBCO data,the room-cuts approach always has less variables and non-global constraintsthan the room-packings approach, whereas the room-packings approach hasfewer global constraints. The datasets with the largest number of variablesand constraints for both approaches are 3, 7, and 8. Table 6.9 shows thetotal number of CP variables and constraints used in the models. For alldatasets except Dataset 12, the room-cuts implementation has fewer vari-ables and constraints, which is mostly consistent with the calculations of theimplementation metrics. Dataset 12 is small, which could be why the room-cuts and room-packings approaches have similar numbers of constraints andvariables. Also shown in this table are metrics from the experiments. Again,for every dataset, the room-cuts approach always has a greater average num-ber of fails during the search. In addition to the comparison between modelsthat will soon follow, these results provide context for each model’s potentialif applied at other institutions. While the comparison between the evalua-tion functions obtained from our experiments and that seen in the literatureare not the goal of this thesis, our results show that for some datasets, ourCP implementation of the ESP provides evaluation functions that are closeto the best known bounds, specifically for Datasets 2 and 12.26Datasets 6 and 8 are the two datasets with infeasible parameters for the frontload andperiod-spread constraints. These parameters are provided in the data. When we say theparameters are infeasible, this means that there is no way to satisfy the constraint. Sincethe constraints are soft, the dataset still has a feasible solution. However, every exam willcontribute to the evaluation function for the two constraints with bad input parameters.776.3. ROOM-CUTS VERSUS ROOM-PACKINGSTable 6.6: List of constraints included in the timeslot assignment model forthe experiments with the ITC 2007 datasets.Requirement Description ConstraintType1 No student can havemore than one exam per timeslotHard2 Exam duration requirement Hard7 Require that specific exams come afterother specific exams (i.e., the “after”constraint)Hard8 Groups of exams can request the sametimeslot (i.e. the “exam-coincidence”constraint)Hard9.1 Certain exams require that they cannotbe at the same time as other certainexams (i.e., the “exclusion” constraint)Hard11 Room-cuts (necessary conditionto satisfy room constraints)Optional,Hard11 Room-packings Optional,Hard13 Frontload large exams Optimized14.1 Penalize the use of specific timeslots Optimized15 Minimize 2-in-1-day hardships (d3) Optimized15 Minimize back-to-back hardships (d1) Optimized15 Minimize “period-spread” hardships(h2,d, where d determined by dataset)Optimized786.3. ROOM-CUTS VERSUS ROOM-PACKINGSTable 6.7: List of constraints included in the room assignment model for theexperiments with the ITC 2007 datasets.Requirement Description ConstraintType9.2 Certain exams cannot be scheduled in thesame room as any other exam (i.e., the“room-exclusive” constraint)Hard11 Number of students writing examsscheduled in a room is at most the effectiveroom sizeSoftened(Opti-mized)12 Minimize the number of rooms hostingexams of different durationsOptimized14.2 Penalize the use of specific rooms Optimized796.3. ROOM-CUTS VERSUS ROOM-PACKINGSTable 6.8: Calculations of implementation metrics of model options for concurrent exams for the ITC 2007 datasets.These calculations are based on the ones listed in Table 5.5. The columns labeled “Cut” and “Pack” correspondto the results from the room-cuts and room-packings approaches, respectively.# Variables #Non-Global# Global Total #ConstraintsP |E| |R| m |U | q Cut Pack Cut Pack Cut Pack Cut Pack1 607 7 54 156 7 9180 33156 1134 32778 8424 108 9558 328862 870 49 40 159 31 8840 36760 3720 34800 6360 80 10080 348803 934 48 36 214 40 10584 35352 4320 33624 7704 72 12024 336964 273 1 21 111 1 2373 5754 63 5733 2331 42 2394 57755 1018 3 42 160 3 6972 42882 378 42756 6720 84 7098 428406 242 8 16 117 6 2064 4000 288 3872 1872 32 2160 39047 1096 15 80 178 9 15680 88880 2160 87680 14240 160 16400 878408 598 8 80 154 8 13600 48480 1920 47840 12320 160 14240 480009 169 3 25 45 3 1275 4300 225 4225 1125 50 1350 427510 214 48 32 84 15 3648 8384 1440 6848 2688 64 4128 691211 934 40 26 214 33 7280 25324 2574 24284 5564 52 8138 2433612 78 50 12 56 18 1104 1536 648 936 672 24 1320 960806.3. ROOM-CUTS VERSUS ROOM-PACKINGSTable 6.9: Statistics of evaluation functions for ITC 2007 datasets. The number of CP variables and constraintscounts all variables and constraints used in the timeslot assignment model. The leftmost column, P, indicatesthe dataset number. EF indicates the evaluation function (which is evaluated according to ITC 2007 rules). Thebest average and minimum evaluation functions achieved for the dataset are bolded. The column “# Room Inf.”refers to the number of instances that were solved in the timeslot assignment model but did not produce feasibleroom assignment solutions. The column “Avg. # Fails” refers to the average number of fails from the searchin CP Optimizer. The columns labeled “Cut” and “Pack” correspond to the results from the room-cuts androom-packings approaches, respectively.Total # ofall CP vari-ablesTotal # ofall CP Con-straintsAvg. # Fails #RoomInf.Avg. EF Min. EF BestinLit.P Cut Pack Cut Pack Cut Pack Cut Pack Cut Pack Cut Pack1 48475 71675 48054 78963 136847 24231 20 0 8593 10046 7453 8335 34632 31198 56477 38965 68103 189089 8298 54 0 435 1804 479 12754 3803 96863 83099 107683 98700 27541 4256 2 0 27464 70407 17560 53911 70414 25357 28646 27236 32834 430672 363603 0 0 26198 26166 21663 21014 107495 27556 63213 28821 70941 226509 7971 0 0 4802 42184 3817 23648 23276 10055 11708 16060 19398 1593346 884573 4 0 27305 27678 26355 26870 251457 65997 137785 65861 150512 51553 3536 0 0 13823 43759 6770 37859 33448 48752 82489 44867 89629 117832 10465 5 0 10994 38386 10269 17616 72809 6297 9218 5792 9683 1943064 1128951 2 0 1624 1567 1429 1426 90110 9683 13479 9178 14738 1969362 791323 0 0 24939 25090 24877 24902 1287811 57199 73261 68904 88775 83420 9731 4 0 153801 134002 125006 90333 2218612 4038 3948 5405 5532 2658340 2187588 14 6 5274 5269 5162 5164 5095816.3. ROOM-CUTS VERSUS ROOM-PACKINGSThe results for Datasets 1, 2, and 12 will be discussed separately, as theanalysis for these datasets is more involved. While comparing the perfor-mance profiles in this section, note that they differ in terms of the rangeof τ .For Datasets 3 and 8, whose performance profiles are shown in Figures 6.5and 6.10, room-cuts appears to be the better approach; however, this modeloption does not attain feasible room assignment solutions for all instances(Dataset 3 had 2 infeasible instances, i.e., 3%, and Dataset 8 had 5 infeasibleinstances, i.e., 8%). As Figures 6.7 and 6.9 show, for Datasets 5 and 7, room-cuts is the clear winner over room-packings since the distribution function forthe room-cuts approach is constant at 1, whereas the distribution functionfor room-packings slowly climbs to 1 until τ ≈ 15 (Dataset 5) and τ ≈ 6(Dataset 7).For the rest of the datasets, the two approaches’ performance profilesare more similar. Dataset 4 only has one room, and therefore the room-packings approach turns into a simple bin packing constraint with two bins,the one room and the virtual bin, and the room-cuts approach only hasone cut that limits the number of students assigned to a timeslot. We cansee from the performance profile on this dataset, shown in Figure 6.6, thatthe room-cuts and room-packings implementations perform similarly. Theaverage and minimum evaluation function values are slightly better for theroom-packings approach (room-cuts’s EF is within 3%). In the Dataset 6and 10 profiles, seen in Figures 6.8 and 6.12, ρsc(1) > ρsp(1), but as τapproaches 1.1, the probability distributions go towards 1. Therefore, room-cuts has better objective function values, but not by a large margin. Thisis confirmed in Table 6.9.The profiles in Figures 6.11 and 6.13 for Datasets 9 and 11, exhibit theopposite behavior in that ρsc(1) < ρsp(1), though as τ approaches 2, theprobability distributions still go towards 1 quickly. The average and mini-mum evaluation functions values are slightly better for the room-packingsapproach for Dataset 9, whereas for Dataset 11, the evaluation functionvalues for the room-packings approach are remarkably lower.For the datasets already discussed, the percentage of problem instancessolved by the room-cuts approach is always above 90% and the room-packings model is able to produce feasible room assignments for all instances.This is not the case for Datasets 1, 2 and 12, where the room-cuts approachfails to produce feasible room assignments for many of the instances. Toassist in the analysis of these datasets, three versions of the room-cuts androom-packings approaches are introduced. If a solution has no feasible roomassignment, the model will make room assignments but minimize the num-826.3. ROOM-CUTS VERSUS ROOM-PACKINGS00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 3room‐cutsroom‐packingsFigure 6.5: Performance profile on ITC 2007 Dataset 3 using Configura-tion A.00.20.40.60.811 1.1 1.2 1.3 1.4 1.5ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 4room‐cutsroom‐packingsFigure 6.6: Performance profile on ITC 2007 Dataset 4 using Configura-tion A.836.3. ROOM-CUTS VERSUS ROOM-PACKINGS00.20.40.60.811 3 5 7 9 11 13 15ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 5room‐cutsroom‐packingsFigure 6.7: Performance profile on ITC 2007 Dataset 5 using Configura-tion A.00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 6room‐cutsroom‐packingsFigure 6.8: Performance profile on ITC 2007 Dataset 6 using Configura-tion A.846.3. ROOM-CUTS VERSUS ROOM-PACKINGS00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on ITC Dataset 7room‐cutsroom‐packingsFigure 6.9: Performance profile on ITC 2007 Dataset 7 using Configura-tion A.00.20.40.60.811 3 5 7 9 11 13 15ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 8room‐cutsroom‐packingsFigure 6.10: Performance profile on ITC 2007 Dataset 8 using Configura-tion B.ber of students that exceed a room’s capacity as the first priority in the856.3. ROOM-CUTS VERSUS ROOM-PACKINGS00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 9room‐cutsroom‐packingsFigure 6.11: Performance profile on ITC 2007 Dataset 9 using Configura-tion B.00.20.40.60.811 1.1 1.2 1.3 1.4 1.5ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 10room‐cutsroom‐packingsFigure 6.12: Performance profile on ITC 2007 Dataset 10 using Configura-tion B.866.3. ROOM-CUTS VERSUS ROOM-PACKINGS00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 11room‐cutsroom‐packingsFigure 6.13: Performance profile on ITC 2007 Dataset 11 using Configura-tion A.objective function (i.e., the most heavily weighted). This allows for thefollowing versions of the model options:− Version 1: all solutions are accepted as feasible and the excess studentsin a room are ignored.− Version 2: if the room capacity requirement is not met the solution isdeemed infeasible.− Version 3: all solutions are judged to be feasible, but every student thatis scheduled in a room exceeding the room’s capacity adds a weight of1000 to the evaluation function.For Dataset 1, ignoring infeasibilities (Version 1) would lead to room-cuts being the better option, as shown in Figure 6.14. Furthermore, theweighted version of room-cuts (Version 3) has a higher probability thanroom-packings of the performance ratio being within a factor of τ of thebest approach when τ < 1.25. However, if infeasibilities are completelyruled out (Version 2), then the room-cuts approach only produces solutionsfor two thirds of the instances. Also note that rM < 7, thus the weightedevaluation function does not greatly increase the objective function valuebecause room capacities are only being exceeded by a few students and the876.3. ROOM-CUTS VERSUS ROOM-PACKINGSscale of the evaluation function is large (i.e., the evaluation function valuesare in the thousands).In Figure 6.15, for Dataset 2, room-cuts would be the clear winner if theinfeasibilities are ignored. If infeasibilities are allowed but weighted, then theroom-cuts implementation would still be a better option than room-packingssince the performance profile for room-cuts Version 2 is greater than thatof room-packings when τ < 30. However, if no infeasibilties are allowed,room-packings is the clear winner since room-cuts only provides feasiblesolutions for 26% of the instances. Note that the scale of the evaluationfunction for this dataset is much smaller (i.e., the evaluation function valuesare in the hundreds for the room-cuts approach), hence a weight of 1000 forinfeasibilities greatly increases the objective function value and the valueof rM .Due to the number of Requirement 9.2 constraints specified in Dataset 12,the room-packings approach also produces timeslot solutions that do nothave a corresponding feasible room assignment. This is because sometimesexams are scheduled in a room assuming that they can share the room withanother exam, but later during the room assignment phase the exam is con-strained to be alone in the exam room. Thus, we apply the three versions tothe room-packings approach as well, as seen in Figure 6.16. For this dataset,the room-cuts and room-packings approaches perform very similarly if all in-feasibilities are ignored. Otherwise, if infeasibilities are included or weighted,room-packings has approximately a 10% higher probability of obtaining aperformance ratio within a factor τ of the best approach.Overall, the experiments with the ITC 2007 datasets present mixed re-sults for choosing between the room-cuts and room-packings approaches.For the five smaller datasets (i.e., Datasets 4, 6, 9, 10, and 12), the two ap-proaches produce similar evaluation function values, and the room-packingsapproach does slightly better than room-cuts for Datasets 4, 9 and 12.Dataset 11 appears to be an anomaly. Unlike the other large datasets whereroom-cuts is the clear winner, the room-packings approach has a higherprobability of being the better solver, and the minimum and average evalu-ation functions obtained across the 60 instances are approximately 28% and13%, respectively, lower than the evaluation function values obtained usingthe room-cuts approach.We note here that 8 of the 12 datasets (Datasets 2 - 7, and 11) useConfiguration A (i.e., the minimum size of exam in the set E>ri−1 \E>ri , u▽i ) forthe room-cuts approach. This is the least restricted version of this constraintand does not cut off any potential feasible solutions. Other configurationswere tested for Dataset 2, such as using u△i , but this did not lead to more886.3. ROOM-CUTS VERSUS ROOM-PACKINGS00.20.40.60.811 2 3 4 5 6 7ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 1room‐cuts V1room‐cuts V2room‐cuts V3room‐packingsFigure 6.14: Performance profile on ITC 2007 Dataset 1 using Configura-tion C.00.20.40.60.811 21 41 61 81 101ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 2room‐cuts V1room‐cuts V2room‐cuts V3room‐packingsFigure 6.15: Performance profile on ITC 2007 Dataset 2 using Configura-tion A.896.4. DISCUSSION00.20.40.60.811 1.5 2 2.5 3ρ sሺ τሻτPerformance Profile on ITC 2007 Dataset 12room‐cuts V1room‐cuts V2room‐cuts V3room‐packings V1room‐packings V2room‐packings V3Figure 6.16: Performance profile on ITC 2007 Dataset 12 using Configura-tion A.feasible room assignment solutions.Three datasets (Dataset 8, 9, 10) used Configuration B (i.e., the maxi-mum size of exam in the set E>ri−1 \ E>ri , u△i ) so that the experiments wouldhave more feasible room assignments. This configuration may cut off poten-tial solutions during the timeslot assignment model.Dataset 1 used Configuration C (u▽i +(u△i −u▽i ) ·0.75). Configuration Bwas infeasible for this dataset, whereas Configuration A produced timeslotsolutions that did not have feasible room assignments. This configurationalso has the possibility of cutting off feasible solutions during the timeslotassignment model.6.4 DiscussionIn this section, we describe the implications of the results from Sec-tion 6.3 and provide some remarks about the models presented in this thesis.The results in Section 6.3.1 illustrate that the room-cuts approach iseffective to use on the UBCO datasets, the datasets that the model wasoriginally built for. For both versions of the two datasets explored, room-cuts has the higher probability of providing the best performance ratioscompared with the room-packings approach when the number of back-to-906.4. DISCUSSIONbacks is used as the performance metric.The effectiveness of our two approaches is further demonstrated in Sec-tion 6.3.2, where we test a generalized version of the model on benchmarkdatasets representing realistic data from other institutions. For four of thetwelve ITC 2007 datasets, Datasets 3, 5, 7, and 8, the room-cuts approach isthe clear winner, achieving much lower evaluation function values and pro-viding feasible room assignments for over 90% of the instances (i.e., seedsfor the solver). These are four of the five biggest datasets.For two of the datasets, Datasets 6 and 10, again feasible room assign-ments are found for over 90% of the instances, and the room-cuts approachstill outperforms the room-packings approach, but the difference betweenevaluation function values is smaller. On the other hand, there are twodatasets, Datasets 4 and 9, where the two approaches have similar perfor-mances, but the room-packings model achieves slightly better evaluationfunction values. Dataset 4, 6, 9, and 10 are the four smallest datasets.Among the datasets where most instances result in a feasible roomassignment solution using the room-cuts approach, there is one outlier,Dataset 11. This is one of the five largest datasets, but unlike the others, theroom-packings approach has the higher probability of being the better solversince it achieves smaller evaluation function values across problem instances.The scale for the evaluation function values for this dataset is the largestamong all datasets. However, there are no other clear indicators that canexplain the differing results, since the number of constraints and variablesfollow a similar pattern as with the other big datasets. For the most part,the types of constraints in this dataset also do not differ in noticeable ways.In fact, referring to Table A.2 in Appendix A, we can see that Datasets 3and 11 are similar in most characteristics (e.g., number of exams, numberof students, number of timeslot-related additional hard constraints, etc.),but there is a distinct difference in the parameter for the frontload examsconstraint. Dataset 11 includes more exams in this constraint comparedwith Dataset 3, that is, the 400 largest exams are constrained in Dataset 11versus the 200 largest exams in Dataset 3. This could lead to larger evalua-tion function values for Dataset 11, though it is not obvious how this wouldimpact the room-cuts and room-packings constraints.In the remaining three datasets, Datasets 1, 2 and 12, the room-cutsapproach did not fair as well. For these datasets, the room-cuts approachdid not produce feasible room assignment solutions for 33%, 74%, and 23%of the instances, respectively. For Datasets 1 and 2, the precise reason forthese infeasibilities is not known, however, accumulating slack in the room-cuts may be the cause. The room-cuts constraints do not include task limits916.4. DISCUSSIONon the rooms (i.e., there is no defined limit on how many exams can bescheduled in a room). So when there are many rooms, small amounts ofslack (i.e., remaining seats) accumulate, and without a room task constraintto limit the number of exams assigned to a timeslot, there is a greaterchance that exams are allowed to be scheduled into a timeslot without away to assign them to rooms. More specifically, the model may allow thatthe smaller exams can be scheduled in the larger rooms, where in fact, forthis to occur, the smaller exam would have to be split across rooms. Thisphenomenon is illustrated in more detail in Example 6.1. The danger ofaccumulating slack is greater for the ITC 2007 datasets compared with theUBCO datasets, since in the latter, most rooms can only host one exam.Example 6.1 (Accumulating Room Slack).Consider the room assignment solution for a specific timeslot shown inTable 6.10. There are 59 exams being assigned to 44 rooms. This solutionwas produced in the room assignment model from a timeslot assignmentmade using the room-cuts approach for ITC 2007 Dataset 2. The excesscolumns count the number of students exceeding the room’s capacity thatare scheduled to write an exam in that room for the timeslot. The totalexcess number of students across all rooms was minimized. Observe thatthe excesses are at most two, and are the result of medium-sized examsbeing scheduled in rooms that are too small.This example serves to illustrate that a room assignment solution istypically infeasible because of only a couple extra students being scheduledin a room. Infeasibilities such as the one shown are especially common whenmany exams are being scheduled into a single timeslot.We already mentioned that the inclusion of many Requirement 9.2 con-straints in Dataset 12 leads to infeasibilities when using the room-packingsapproach. This is also the case for the room-cuts approach. Thus, if adataset has many room-related requirements (i.e., Requirements 5, 9.2, 12,and 14.2), to avoid infeasible room assignments, either pre-processing needsto be performed (which requires simpler room constraints and a thorough un-derstanding of the problem), or the room-packings approach should be usedand the room-related constraints added to the unified model. We showedthat when the room capacity constraint is softened, the room-cuts approachstill competes with, and potentially beats, the room-packings approach. Wechose to explore these variations because the room capacity constraint maynot be a hard constraint in some universities. For instance, at UBCO somestudents write their exams in a separate room (the Disability Resource Cen-ter) than the one scheduled because they require special accommodations.926.4. DISCUSSIONTable 6.10: Accumulating room slack example.Room RoomSize#Stud.Excess Room RoomSize#Stud.Excess1 424 300 21 60 531 424 122 22 60 61 12 400 258 23 60 552 400 74 24 58 582 400 65 25 51 513 264 200 26 50 51 13 264 64 27 50 494 219 215 28 50 495 195 127 29 50 51 15 195 65 30 40 356 143 78 31 40 156 143 63 31 40 157 127 125 31 40 108 120 67 32 40 398 120 52 33 39 399 110 62 34 38 359 110 48 34 38 110 110 112 2 35 36 3511 100 51 36 30 1611 100 49 36 30 1412 100 86 37 30 2212 100 9 38 30 2413 92 91 39 30 2314 90 83 40 27 2515 85 82 40 27 116 80 75 41 25 2217 80 75 42 23 2318 72 73 1 43 19 1119 70 69 44 14 120 60 54Thus, the number of students scheduled to write the exam in the room maybe smaller than the true exam size. Additionally, because of the double-seating requirement, the room capacity can be slightly exceeded by a hand-ful of students without an issue. Thus, if the room capacity constraint is936.4. DISCUSSIONnot strict, the room-cuts approach should be considered.All experiments showed that the room-cuts approach had a higher aver-age number of failures during the search than the room-packings approach.The large number of failures could indicate that less domain reduction isbeing done at each node of the search tree, resulting in the solver choosingto branch on bad values in a variable’s domain, which later results in aninfeasiblility and a failure. Alternatively, the large number of failures couldmean that more space of the search tree is being explored quickly, whichcould lead to more failures. Thus, the average number of failures is not areliable indicator of the quality of either method’s performance.While our results from the experiments with the ITC 2007 datasets donot improve upon any of the current best evaluation function values, thevalues produced are in the same ranges as those seen in the literature. Sothough more work would need to be done to make our system produce betterresults than those of other researchers, the results we see here give the modelmerit and provide evidence that it can be applied to other institutions. Onepossible improvement that could produce better solutions is the incorpo-ration of the mixed duration and room penalties portion of the evaluationfunction into the timeslot assignment model when using the room-packingsconstraints.CP Optimizer has shown large improvements in terms of global con-straints, search phases, and search strategies since its first release. This ispromising for the combinatorial optimization community because this solvercontinues to become a viable tool for more and more scheduling applications.Other solvers do not implement the same global constraint library and mayhave different underlying filtering algorithms. Further research could beconducted to test the effectiveness of other solvers, such as the open sourcesolver Google OR-Tools. Additionally, other solvers’ global constraint li-braries, such as OR-Tools, do not include a bin packing constraint, whichare used in the room-packings approach of the timeslot assignment model.In this case, if the solver provides a GCC constraint, then the room-cutsmodel option could be used as an alternative. Thus, the model options pre-sented in this thesis can provide practitioners with different tools dependingon the solvers available to them.As previously mentioned, there is room for improvement in our models.While we used global constraints wherever we thought was suitable, there aremany choices that are made when deciding how to model constraints. Thus,the use of different types of CP constraints or representations can always bemade and tests can be performed to reveal which constraint implementationsyield the best performance. Furthermore, as mentioned in previous chapters,946.4. DISCUSSIONadditional experiments could be conducted to explore more search phasesand goals within CP Optimizer to improve the search for optimal solutions.95Chapter 7ConclusionIn this thesis we have presented a constraint programming model thatsolves the examination scheduling problem. The ESP has been studiedby numerous researchers and has been involved in several internationaltimetabling competitions, each of which produced a plethora of models usedto approach the ESP. We have provided a literature review to detail thehistory of the exam scheduling problem and the various methods used.The University of British Columbia’s Okanagan campus has require-ments that fall outside of the scope of existing models and their currentscheduling software. Therefore, a new scheduling system is needed that canaccommodate UBCO’s specific situation. This thesis outlines the researchproject that involved producing the CP exam scheduling system that gener-ated the exam schedules for UBCO’s 2021/2022 academic year. These examschedules exhibited optimized metrics which improved the overall quality forthe various stakeholders, providing UBCO with a higher standard for futureexam schedules. Furthermore, we provide a generic specification of the examscheduling problem, as well as the corresponding CP implementation.The CP model has two main features that distinguish it from the restof the literature. First, we introduce a new formulation of a hardship rule,which is defined as students having to write multiple exams within a certainlength of time. For UBCO, a student hardship is specified as a studenthaving to write three exams within a consecutive 27-hour window. Wedescribe a CP implementation to model the generic specification of thisrequirement.The second key contribution of this work is a novel set of cuts, calledroom-cuts, which enable the ESP to be split into two phases: the timeslotassignment phase and the room assignment phase. The set of room-cuts isnecessary to provide a timeslot assignment that can later lead to a roomassignment where each exam can be assigned to a room while respectingeach room’s capacity. In the case that only one exam is allowed in a roomat a given time, this set of cuts is proven to be sufficient. We also introducea unified approach, where the timeslot assignment and room assignment arespecified in the same model. This is called the room-packings approach.96The advantage of this approach is that one can guarantee a feasible roomassignment during the first, and only, phase (if one exists and a solutioncan be found). However, there is an associated cost in terms of modelperformance and efficiency.We test this model on the UBCO data used to generate the 2021/2022exam schedules, as well as the ITC 2007 benchmark datasets. Performanceprofiles are produced to compare and contrast the room-cuts and the room-packings approaches. For the UBCO datasets, the room-cuts approach wasthe clear winner. On the other hand, for the ITC 2007 datasets, the problemsize of the dataset was shown to be an important factor in determining whichapproach would lead to the better solutions. Thus, the two approaches eachhave a distinct set of advantages, and the choice between model optionsgreatly depends on problem size and the solvers available for the users.All in all, the constraint programming models described in this thesisprovide new real-world examination scheduling tools for researchers andpractitioners alike.97Bibliography[1] Benchmark Exam Timetabling Datasets. http://www.cs.nott.ac.uk/~pszrq/data.htm. Accessed: 2022-07-11. → pages 2[2] CP Optimizer User’s Manual - IBM Documentation.https://www.ibm.com/docs/en/icos/22.1.0?topic=optimizer-cp-users-manual. Accessed: 2022-07-09. → pages18[3] Optimization Hub – Problem Management System. https://opthub.uniud.it/problem/timetabling/edutt/ett/itc-2007-ett. Ac-cessed: 2022-07-07. → pages 16, 76[4] PATAT - International Conference on the Practice and Theoryof Automated Timetabling. https://www.patatconference.org/communityService.html. Accessed: 2022-07-07. → pages 15[5] E. Aarts and J. K. Lenstra, eds., Local Search in CombinatorialOptimization, Princeton University Press, 2018. → pages 98, 102, 103[6] E. H. . L. Aarts, J. H. M. Korst, and P. J. M. van Laarhoven,Simulated annealing, in Aarts and Lenstra [5], pp. 91–120. → pages 6[7] A. Ahmeti and N. Musliu, Hybridizing constraint programming andmeta-heuristics for multi-mode resource-constrained multiple projectsscheduling problem, in Proceedings of the 13th International Conferenceon the Practice and Theory of Automated Timetabling-PATAT, vol. 1,2021. → pages 14[8] S. M. Al-Yakoob and H. D. Sherali, Mixed-integer programmingmodels for an employee scheduling problem with multiple shifts and worklocations, Annals of Operations Research, 155 (2007), pp. 119–142. →pages 7[9] F. Al-Hawari, M. Al-Ashi, F. Abawi, and S. Alouneh, A prac-tical three-phase ILP approach for solving the examination timetabling98Bibliographyproblem, International Transactions in Operational Research, 27 (2020),pp. 924–944. → pages 2, 16[10] J. F. Bard, C. Binici, and A. H. desilva, Staff scheduling atthe united states postal service, Computers & Operations Research, 30(2003), pp. 745–771. → pages 7[11] M. Battistutta, S. Ceschia, F. D. Cesco, L. D. Gaspero,A. Schaerf, and E. Topan, Local search and constraint program-ming for a real-world examination timetabling problem, in InternationalConference on Integration of Constraint Programming, Artificial Intel-ligence, and Operations Research, Springer, 2020, pp. 69–81. → pages15[12] M. Battistutta, A. Schaerf, and T. Urli, Feature-based tuningof single-stage simulated annealing for examination timetabling, Annalsof Operations Research, 252 (2017), pp. 239–254. → pages 16[13] N. Beldiceanu, M. Carlsson, and J.-X. Rampon, Global Con-straint Catalog, 2nd edn. (revision a), tech. rep., SICS Technical Report2012:03, 2012. → pages 17, 18, 20[14] D. Bergman, A. A. Cire, W.-J. Van Hoeve, and J. Hooker,Decision Diagrams for Optimization, Springer, Cham, 2016. → pages13[15] S. Broder, Final examination scheduling, Communications of theACM, 7 (1964), pp. 494–498. → pages 15[16] E. K. Burke and Y. Bykov, An adaptive flex-deluge approach to uni-versity exam timetabling, INFORMS Journal on Computing, 28 (2016),pp. 781–794. → pages 16[17] , The late acceptance Hill-Climbing heuristic, European Journal ofOperational Research, 258 (2017), pp. 70–78. → pages 16[18] Y. Bykov and S. Petrovic, A Step Counting Hill Climbing Al-gorithm applied to University Examination Timetabling, Journal ofScheduling, 19 (2016), pp. 479–492. → pages 16[19] H. Cambazard, E. Hebrard, B. O’Sullivan, and A. Papadopou-los, Local search and constraint programming for the post enrolment-based course timetabling problem, Annals of Operations Research, 194(2012), pp. 111–135. → pages 1599Bibliography[20] M. W. Carter, A survey of practical applications of examinationtimetabling algorithms, Operations Research, 34 (1986), pp. 193–202.→ pages 5[21] A. Cataldo, J. C. Ferrer, J. Miranda, P. A. Rey, andA. Saure´, An integer programming approach to curriculum-based ex-amination timetabling, Annals of Operations Research, 258 (2017),pp. 369–393. → pages 16[22] X. Chen, G. Reinelt, G. Dai, and A. Spitz, A mixed integer linearprogramming model for multi-satellite scheduling, European Journal ofOperational Research, 275 (2019), pp. 694–707. → pages 7[23] A. J. Cole, The preparation of examination time-tables using a small-store computer, The Computer Journal, 7 (1964), pp. 117–121. → pages15[24] G. Da Col and E. C. Teppan, Industrial size job shop schedul-ing tackled by present day cp solvers, in International Conference onPrinciples and Practice of Constraint Programming, Springer, 2019,pp. 144–160. → pages 8[25] H. G. de Alba, S. Nucamendi-Guille´n, and O. Avalos-Rosales,A mixed integer formulation and an efficient metaheuristic for the unre-lated parallel machine scheduling problem: total tardiness minimization,EURO Journal on Computational Optimization, (2022), p. 100034. →pages 14[26] B. De Backer, V. Furnon, P. Shaw, P. Kilby, and P. Prosser,Solving vehicle routing problems using constraint programming andmetaheuristics, Journal of Heuristics, 6 (2000), pp. 501–523. → pages14[27] R. Dechter, D. Cohen, et al., Constraint processing, Morgan Kauf-mann, 2003. → pages 7[28] E. Demirovic´ and P. J. Stuckey, Constraint programming for highschool timetabling: A scheduling-based model with hot starts, in Lec-ture Notes in Computer Science (including subseries Lecture Notes inArtificial Intelligence and Lecture Notes in Bioinformatics), vol. 10848,Springer Verlag, 2018, pp. 135–152. → pages 15100Bibliography[29] G. Derval, J. C. Re´gin, and P. Schaus, Improved filtering for thebin-packing with cardinality constraint, Constraints, 23 (2018), pp. 251–271. → pages 10, 12[30] E. Dolan and J. More´, Benchmarking optimization software withperformance profile, Mathematical Programming, 91 (2001), pp. 201–213. → pages 65, 66[31] R. Duque, A. Arbelaez, and J. F. D´ıaz, Cp and mip approachesfor soccer analysis, Journal of industrial and management optimization,15 (2019), pp. 1535–1564. → pages 14[32] C. A. Floudas and X. Lin, Mixed integer linear programming inprocess scheduling: Modeling, algorithms, and applications, Annals ofOperations Research, 139 (2005), pp. 131–162. → pages 7[33] E. C. Freuder and A. K. Mackworth, Constraint satisfaction: Anemerging paradigm, vol. 2, Elsevier B.V., 2006. → pages 7[34] B. Genc and B. O’Sullivan, A Two-Phase Constraint Program-ming Model for Examination Timetabling at University College Cork,vol. 12333 LNCS, Springer International Publishing, 2020. → pages 2,16[35] N. Ghandehari and K. Kianfar, Mixed-integer linear programming,constraint programming and column generation approaches for operat-ing room planning under block strategy, Applied Mathematical Mod-elling, 105 (2022), pp. 438–453. → pages 14[36] A. Gogna and A. Tayal, Metaheuristics: review and application,Journal of Experimental & Theoretical Artificial Intelligence, 25 (2013),pp. 503–526. → pages 5, 6[37] C. Gogos, G. Goulas, P. Alefragis, V. Kolonias, andE. Housos, Distributed scatter search for the examination timetablingproblem, PATAT 2010 - Proceedings of the 8th International Confer-ence on the Practice and Theory of Automated Timetabling, (2010),pp. 211–223. → pages 16[38] B. Go¨kgu¨r, B. Hnich, and S. O¨zpeynirci, Parallel machinescheduling with tool loading: a constraint programming approach, In-ternational Journal of Production Research, 56 (2018), pp. 5541–5557.→ pages 8101Bibliography[39] C. P. Gomes, B. Selman, and H. Kautz, Boosting combinatorialsearch through randomization, in 15th National Conference on AritificlaIntelligence (AAAI-98), American Association for Artificial Intelligence,1998, pp. 431–437. → pages 19[40] A. Gu¨lcu¨ and S. Bulkan, Integer programming versus constraintprogramming: A course timetabling case study, International Journalof Industrial Engineering, 26 (2019). → pages 14[41] A. M. Ham, Integrated scheduling of m-truck, m-drone, and m-depotconstrained by time-window, drop-pickup, and m-visit using constraintprogramming, Transportation Research Part C: Emerging Technologies,91 (2018), pp. 1–14. → pages 8[42] S. Hamilton, Math 590 report: A review of “improved filtering for thebin-packing with cardinality constraint”, (2021). Tech. Rep., 16 pages.→ pages 12[43] , Math 620 final report: Distribute in constraint programming,(2021). Tech. Rep., 30 pages. → pages 10, 20[44] S. Hamilton and D. R. Hare, Exam scheduling with hardship mini-mization, in 13th International Conference on the Practice and Theoryof Automated Timetabling, Springer, 2022, pp. 1–29. In Press. → pages3[45] A. Hanset, N. Meskens, and D. Duvivier, Using constraint pro-gramming to schedule an operating theatre, in 2010 IEEE Workshop onHealth Care Management (WHCM), 2010, pp. 1–6. → pages 8[46] A. Hertz, E. Taillard, and D. de Werra, Tabu search, in Aartsand Lenstra [5], pp. 121–136. → pages 6[47] D. S. Holm, R. Mikkelsen, M. Sørensen, and T. J. Stidsen, Agraph-based MIP formulation of the International Timetabling Compe-tition 2019, Journal of Scheduling, (2022). → pages 14, 15[48] J. N. Hooker et al., Integrated methods for optimization, vol. 170,Springer, 2012. → pages 8, 9[49] T. Kim, Optimal approach to game scheduling of multiple round-robintournament: Korea professional baseball league in focus, Computers &Industrial Engineering, 136 (2019), pp. 95–105. → pages 7102Bibliography[50] P. Laborie and J. Rogerie, Temporal linear relaxation in IBMILOG CP Optimizer, Journal of Scheduling, 19 (2016), pp. 391–400.→ pages 13[51] N. Leite, C. M. Fernandes, F. Mel´ıcio, and A. C. Rosa, Acellular memetic algorithm for the examination timetabling problem,Computers & Operations Research, 94 (2018), pp. 118–138. → pages16[52] N. Leite, F. Mel´ıcio, and A. C. Rosa, A fast simulated anneal-ing algorithm for the examination timetabling problem, Expert Systemswith Applications, 122 (2019), pp. 137–151. → pages 16[53] W. T. Lunardi, E. G. Birgin, P. Laborie, D. P. Ronconi, andH. Voos, Mixed integer linear programming and constraint program-ming models for the online printing shop scheduling problem, Comput-ers Operations Research, 123 (2020), p. 105020. → pages 14[54] H. M .˙u hlenbein, Genetic algorithms, in Aarts and Lenstra [5],pp. 137–170. → pages 6[55] A. K. Mandal, M. N. Kahar, and G. Kendall, Addressing ex-amination timetabling problem using a partial exams approach in con-structive and improvement, Computation, 8 (2020). → pages 16[56] B. McCollum, P. McMullan, E. K. Burke, A. J. Parkes, andR. Qu, The Second International Timetabling Competition: Examina-tion Timetabling Track, (2007), p. 10. → pages 15, 76[57] L. Meng, C. Zhang, Y. Ren, B. Zhang, and C. Lv, Mixed-integerlinear programming and constraint programming formulations for solv-ing distributed flexible job shop scheduling problem, Computers & In-dustrial Engineering, 142 (2020), p. 106347. → pages 14[58] L. T. Merlot, N. Boland, B. D. Hughes, and P. J. Stuckey,A hybrid algorithm for the examination timetabling problem, LectureNotes in Computer Science (including subseries Lecture Notes in Ar-tificial Intelligence and Lecture Notes in Bioinformatics), 2740 (2003),pp. 207–231. → pages 16[59] T. Mu¨ller, ITC2007 solver description: A hybrid approach, Annalsof Operations Research, 172 (2009), pp. 429–446. → pages 15103Bibliography[60] T. Mu¨ller, Real-life examination timetabling, Journal of Scheduling,19 (2016), pp. 257–270. → pages[61] T. Mu¨ller and Z. Mu¨llerova´, Unitime around the world, Presentedat OpenApereo 2022 Conference, 2022. → pages 15[62] R. Qu, E. K. Burke, B. McCollum, L. T. Merlot, and S. Y.Lee, A survey of search methodologies and automated system devel-opment for examination timetabling, Journal of Scheduling, 12 (2009),pp. 55–89. → pages 4, 5, 15[63] E. Rappos, E. Thie´mard, S. Robert, and J. F. Heˆche, A mixed-integer programming approach for solving university course timetablingproblems, Journal of Scheduling, (2022). → pages 15[64] V. Rasouli, I. Gonc¸alves, C. H. Antunes, and Gomes, A com-parison of milp and metaheuristic approaches for implementation of ahome energy management system under dynamic tariffs, in 2019 In-ternational Conference on Smart Energy Systems and Technologies(SEST), 2019, pp. 1–6. → pages 14[65] J. C. Regin, Generalized arc consistency for global cardinality con-straint, Proceedings of the National Conference on Artificial Intelli-gence, 1 (1996), pp. 209–215. → pages 10[66] SaTT, Validation. https://bitbucket.org/satt/examtt-instances/src/master/Validation/. Accessed: 2022-07-11. → pages77[67] E. G. Talbi, Combining metaheuristics with mathematical program-ming, constraint programming and machine learning, Annals of Oper-ations Research, 240 (2016), pp. 171–215. → pages 14[68] T. Wang, N. Meskens, and D. Duvivier, Scheduling operating the-atres: Mixed integer programming vs. constraint programming, Euro-pean Journal of Operational Research, 247 (2015), pp. 401–413. →pages 14[69] S. Zhang and S. Wang, Flexible assembly job-shop scheduling withsequence-dependent setup times and part sharing in a dynamic envi-ronment: Constraint programming model, mixed-integer programmingmodel, and dispatching rules, IEEE Transactions on Engineering Man-agement, 65 (2018), pp. 487–504. → pages 14104[70] M. S¸ahin and T. Kellego¨z, A new mixed-integer linear programmingformulation and particle swarm optimization based hybrid heuristic forthe problem of resource investment and balancing of the assembly linewith multi-manned workstations, Computers and Industrial Engineer-ing, 133 (2019), pp. 107–120. → pages 14105AppendixAppendix ATables106Appendix A. TablesTable A.1: Data properties for the UBCO 2021/2022 data sets. These statis-tics vary slightly for the Version 2 datasets where all exams are scheduledin a room. This is because there are more Requirement 8.2’s (Coupled Ex-ams, room version), leading to more amalgamated courses and less distinctexams.Data Property Term 1 Term 2Number of exams 358 378Number of exams requiring a room 217 275Number of exams representing cross-listed sec-tions23 33Number of exams representing common exams 41 41Number of students enrolled in exams 10031 9369Average number of exams per student 3.4 3.4Average number of students per exam 96.4 84.9Number of instructors 256 269Number of regular roomsa 32 32Number of gyms 1 1Number of computer rooms 8 8Number of restricted rooms 4 6Number of triples of exams with students incommon15848 15457Number of pairs of exams with students in com-mon9345 9033Concurrent exam periods constraints (Req. 8.1) 20 19Different period constraints 0 0Concurrent exam rooms constraints (Req. 8.2) 0b 0Different room constraints 0 0Time specific constraints (Req. 5) 9 8Room specific constraints (Req. 5) 7 25aAll rooms are available for all timeslots.bAll sets of exams with this requirement were amalgamated into a singleexam in pre-processing.107Appendix A. TablesTable A.2: Data properties for the ITC 2007 benchmark datasets. The dataset number is shown in the leftmostcolumn labeled P. Requirements 7, 8.1, 9.1, and 9.2 refer to the Temporal Precedence, Coupled Exams (timeslots),Separated Exams (timeslots), and Separated Exams (rooms) constraints, respectively. Total Time Hard Cst. refersto the sum of the three columns to the right, that is, the sum of the additional extra timeslot-related constraints.The first number in FT/FE refers to the number of last timeslots which should be avoided for the frontloadconstraint and the second number refers to the number of largest sized exams to include in the constraint.PS indicates the number of timeslots that should occur between any students two exams (i.e., period-spread).Ex./Stud. is the number of exams per student. Stud./Ex. is the number of students per exam.P |E| |P | [m] |R| TotalTimeHardCst.#Req.7#Req.8.1#Req.9.1#Req.9.2FT/FE PS Ex./Stud.Stud./Ex.1 607 7883 54 7 12 9 2 1 0 30/100 5 4.1 53.32 870 12484 40 49 8 3 8 1 2 30/250 1 3 433 934 16365 36 48 83 1 81 1 15 20/200 4 3.7 65.54 273 4421 21 1 20 0 4 16 0 10/50 2 4.9 79.65 1018 8719 42 3 27 6 16 5 0 30/250 5 3.9 33.66 242 7909 16 8 22 2 19 2 0 30/25 20 2.3 76.37 1096 13795 80 15 28 6 13 9 0 30/250 10 3.3 41.58 598 7718 80 8 20 15 5 0 1 100/250 15 4.1 52.59 169 624 25 3 10 7 2 1 0 10/100 5 4.1 1510 214 1415 32 48 58 9 49 0 0 10/100 20 5.5 36.711 934 16365 26 40 83 1 81 1 15 20/400 4 3.7 65.512 78 1653 12 50 9 0 2 7 7 5/25 5 2.2 47.2108
Thesis/Dissertation
eng
Mathematics
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Hare, Donovan
Constraint programming models for real-world examination scheduling
Text