title: Optimal minimal-perturbation university timetabling with faculty preferences
authors: Jakob Kotas Peter Pham Sam Koellmann
text: 
  
  
  Optimal minimal-perturbation university
   timetabling with faculty preferences
      
  Jakob KotasDepartment of Mathematics, University of Portland, 5000 N Willamette Blvd, Portland OR 97203 USA; kotas@up.edu [Corresponding author] Peter PhamShiley School of Engineering, University of Portland, 5000 N Willamette Blvd, Portland OR 97203 USA; phamp23@up.edu, koellman23@up.edu Sam Koellmann[2]
      December 30, 2023
  =======================================================================================================================================================================================================================================================================================================================
  
  
  In the university timetabling problem, sometimes additions or cancellations of course sections occur shortly before the beginning of the academic term, necessitating last-minute teaching staffing changes. We present a decision-making framework that both minimizes the number of course swaps, which are inconvenient to faculty members, and maximizes faculty members' preferences for times they wish to teach. The model is formulated as an integer linear program (ILP). Numerical simulations for a hypothetical mid-sized academic department are presented.
  
  
  Keywords: scheduling, university timetabling, integer program, minimal perturbation
  
  
  
  § INTRODUCTION
  
  
  Scheduling and assignment problems have long been a focus of study in the operations research community. In particular, the problem of scheduling university courses has been investigated by a number of authors dating back at least to the 1970s.<cit.> A number of models for university course scheduling, also known as timetabling, have been proposed. The overall problem contains subproblems including (a) determining time slots that courses may be offered during, (b) deciding which course is assigned to a particular room at a given time, (c) deciding which instructor is assigned to a given course, and so forth.<cit.> In this work we focus on the dynamic rescheduling problem that sometimes occurs after a timetable has been chosen, due to issues such as unexpected enrollment fluctuations. In this case, we wish to develop a new schedule which minimizes in some sense the number of course swaps, which are inconvenient to faculty members as well as students after registration has occurred; while at the same time taking into consideration faculty preferences for times they wish to teach.
  
  In the scheduling literature, the reassignment problem is sometimes referred to as a “minimal perturbation" problem (MPP). Barták, Müller, Rudová, and Murray were the first to study the MPP in the context of university course scheduling and have published several papers on the topic.<cit.> Their approach is called “iterative forward search" which operates over feasible, but incomplete solutions (meaning some variables are unassigned). Their work builds off of El Sakkout, Richards, and Wallace<cit.> who introduced the MPP for general dynamic programs. More recent work in high school timetabling has been that of Kingston<cit.>, who describes an algorithm called “polymorphic ejection chains," which repair an infeasibility while possibly creating a new one, in a successive fashion until the solution is feasible. Finally, Phillips, Walker, Ehrgott and Ryan<cit.> minimize course swaps in the university timetabling problem by only searching for solutions in a neighborhood of the original (now-infeasible) solution, and expanding the neighborhood until a solution is found.
  
  In contrast to the aforementioned works, the model we present here represents a new multiobjective approach, where swaps are minimized through explicit inclusion in the objective function. The benefits of this approach are several. First, ours is an exact solution method that does not rely on heuristics, so an optimal solution is guaranteed. Second, since both the minimizing of perturbations as well as a weighted sum of faculty time-preferences are considered in the objective function, we favor swaps that improve the times at which faculty teach. This also allows the decision-maker to choose the relative importance of these two objectives. Our formulation is an integer linear program (ILP) and thus can be solved with virtually any commonly-used optimization software package; there is no need for a problem-specific solution algorithm.
  
  In this paper we borrow notation from a model put forth by Kumar.<cit.> That model is also an ILP that schedules courses to time slots and assigns instructors to them.  The objective function is a linear weighted sum of faculty time-preferences. Note that Kumar's model is for the original timetabling assignment problem and not the reassignment problem.
  
  
  
  
  
  
  § MODEL
  
  
  Decision variables
  
  
      P_ijt     =     1     if course i is added to faculty j in time slot t
  
           =     -1     if course i is removed from faculty j in time slot t
  
           =     0     otherwise
  
  
  
  
  Also T_ij are decision variables which will be necessary to linearize the objective function; see below.
  
  
  Parameters
  
  
    * Obsolete schedule
  
  
      X_ijt     =     1 if course i had been assigned to faculty j in time slot t
  
          =     0 otherwise
  
  
  
  The new schedule is X_ijt + P_ijt.
  
  
    * Faculty time-preference matrix
  
  
      W_jt     ≥     0     indicate faculty j's preference for teaching in time slot t.
  
  
  Higher scores correspond to more desirable times. 0 indicates unavailability during time slot.
  
  
    * Faculty time availability matrix
  
  
      F_jt     =     1 if W_jt > 0     indicates faculty j is available in time slot t
  
          =     0 if W_jt = 0     otherwise
  
  
  
  
    * Course swap penalty matrix
  
  
      α_ij     ≥     0     are penalty factors for making changes to course i in faculty j's schedule.
  
  
  
  This penalty applies for either adding a course that was previously not in faculty j's schedule, or for removing a course that was previously in faculty j's schedule. Simply changing to a different section of an existing course incurs no penalty due to α_ij. However note that a reward/penalty for changing the time slot to a more or less desirable time for faculty i is handled via W_jt.
  
  
    * Course-time slot matrix
  
  
      M_it     =     number of sections of course i scheduled at time slot t
  
  
  
  Note that due to this definition of M_it differs from the Kumar model.
  
  
    * Faculty-course matrix
  
  
      C_ij     =     1 if course i can be taught by faculty j
  
          =     0 otherwise
  
  
  
  
    * Teaching load
  
  
      N^+_j     =     maximum number of courses/credit hours that can be assigned to faculty j
  
      N^-_j     =     minimum number of courses/credit hours that can be assigned to faculty j
  
      H_i     =     number of courses/credit hours that course i counts as
  
  
  Our model accommodates faculty contracts on either a per-course or per-credit hour basis. If faculty member j must teach an exact number, then N^+_j=N^-_j. Part-time faculty with a range on how many courses/credit hours (including zero) can also be accommodated.
  
  
  
  
  Objective function
  
  The objective function is the weighted sum of faculty time-preferences, plus the weighted sum of the absolute value of courses added and subtracted:
  
      max∑_j ∑_t ( W_jt∑_i P_ijt)_faculty time preferences - ∑_i ∑_j ( α_ij|∑_t P_ijt| )_course swaps
  
  
  Where |·| is in the componentwise sense. Note that this objective function is not linear but can be made linear through the introduction of the new variables T_ij. We arrive at our final form:
  
      max∑_j ∑_t ( W_jt∑_i P_ijt) - ∑_i ∑_j α_ij T_ij
  
  along with additional constraints labeled “new variable constraints" below.
  
  
  Constraints
  
  
    * New variable constraints:
  
   T_ij≥∑_t P_ijt∀ i ∀ j
  
   T_ij≥ -∑_t P_ijt∀ i ∀ j
  
  These constraints are necessary to convert the |∑_t P_ijt| term in the objective function into linear form.
  
  
    * New schedule is binary:
  
   X_ijt+P_ijt≥ 0 ∀ i ∀ j ∀ t
  
   X_ijt+P_ijt≤ 1 ∀ i ∀ j ∀ t
  
  This set of constraints ensures that you cannot add a course and time that a faculty member already has, nor can you remove a course and time that a faculty member did not have.
  
  
    * Assign all courses:
  
   ∑_j (X_ijt + P_ijt) = M_it∀ t ∀ i
  
  These constraints ensure that every section of every course is assigned to a faculty member.
  
  
    * Faculty teach only courses from their choice list:
  
   ∑_t (X_ijt+P_ijt) ≤ C_ij∑_t M_it∀ i ∀ j
  
  These constraints ensure that faculty only teach courses they are able to teach.
  
  
    * Faculty teach only during their available times:
  
   ∑_i (X_ijt+P_ijt) ≤ F_jt∀ j ∀ t
  
  These constraints ensure that faculty are not scheduled during times they are not available, and also that a faculty member may teach no more than one course simultaneously.
  
  
    * Teaching load requirements:
  
   ∑_i H_i ∑_t (X_ijt+P_ijt) ≤ N_j^+ ∀ j
  
   ∑_i H_i ∑_t (X_ijt+P_ijt) ≥ N_j^- ∀ j
  
  These constraints ensure that each faculty member teaches the correct number of courses.
  
  
    * Avoid time slot conflicts:
  
   ∑_i (X_ijt'+P_ijt') + ∑_i (X_ijt”+P_ijt”) ≤ 1 ∀ j ∀ t', t” that conflict
  
  These constraints prevent a faculty from teaching at both time slots t' and t”. This could be because t' and t” overlap or because we wish to prevent faculty from teaching both early mornings and late evenings, or both Mon/Wed/Fri and Tue/Thur, etc.
  
  
    * Decision variables are binary:
  
   -1≤ P_ijt≤ 1, P_ijt integer
  
   0≤ T_ij≤ 1, T_ij integer
  
  This enforces that each element of the decision variable P_ijt∈{-1,0,1} and T_ij∈{0,1}.
  
  
  
  
  
  
  § SIMULATIONS
  
  
  In this section we present numerical simulations for a hypothetical department offering 57 sections of 17 different courses, with 13 full-time and 9 part-time faculty members, during 24 possible time slots. These values were based on the Fall 2020 semester schedule for the Mathematics Department at the University of Portland. All full-time faculty must teach 3 courses while part-time faculty may teach between 0 and 2 courses. Some pairs of time slots conflict with each other (time slots 8:10-9:05 Mon/Wed/Fri and 8:10-9:05 Mon/Tue/Wed/Fri are one such example.) We assume for simplicity that the W_jt and α_ij matrices are all 1s, indicating that all faculty are equally satisfied teaching at any time and are equally inconvenienced by a course add or drop. M_it represent actual sections scheduled for Fall 2020 at the University of Portland. For C_ij, an attempt was made to group together faculty based on their subdiscipline; for example, part-time faculty can teach any lower-division course, while pure mathematicians can teach lower-division courses plus pure upper-division courses, whereas applied mathematicians can teach lower-division courses plus applied upper-division courses. X_ijt are a simulated feasible solution based on these constraints.
  
  The IP involved 9350 variables and 39238 constraints. The problem was solved in Matlab R2016b, using the “intlinprog" function in the Optimization Toolbox. Elapsed time to run the entire code, including reading in data from a spreadsheet, setting up constraints to pass to the solver, and displaying the output, was approximately 4 seconds on a single 2.8 GHz Intel Core i5 processor for each simulation that follows; the time for just the solution of the IP was approximately 2 seconds.
  
  
  
  
  
  
  Simulation 1: Removal from part-time faculty
  
  We remove one section of one course that is taught by a part-time faculty member in X_ijt. As expected, P_ijt = -1 for that course-faculty-time slot combination, and P_ijt = 0 for all other combinations indicating that no other changes occur.
  
  
  Simulation 2: Removal from full-time faculty
  
  We remove one section of one course that is taught by a full-time faculty member in X_ijt. Because full-time faculty must teach 3 courses, they are reassigned a course that had been taught by a part-time faculty member. Thus we have P_ijt = -1 in two places (the removed section and the section lost by the part-time faculty member) and P_ijt = 1 in one place (the section moved from part-time to full-time), and P_ijt = 0 elsewhere. We further note that the full-time faculty member is swapped to another section of the same course, which incurs no penalty due to α_ij.
  
  
  Simulation 3: Forcing a course swap
  
  In both previous simulations, our model was able to adjust so that no instructor was forced to take on a new course, as opposed to switching sections of an existing course. However, if we push the system far enough, this becomes inevitable. For example, 8 sections of MTH 201 are offered. We choose to cancel 3 sections assigned to part-time faculty and 1 section assigned to a full-time faculty. The full-time faculty is reassigned to MTH 112 as there are no available sections of MTH 201 left. This is the first simulation in which we have seen an instance of the course swap penalty being activated (i.e., T_ij > 0 for some i, j.)
  
  
  A summary of simulations 1-3 can be found in table <ref>.
  
  
  
  
  
  
  
  
  § CONCLUSION
  
  We have developed a decision-making framework for last-minute teaching staffing changes when courses are added or removed for an academic department. This framework minimizes swaps in such a way that it penalizes changing a faculty member to a different course but not a different section of the same course. It also maximizes faculty members' preferences for times they wish to teach. The relative importance of these factors to each other as well as across various faculty members are handled through the weight matrices W_jt and α_ij. Our framework is easily and quickly solvable using off-the-shelf IP solvers. From the first author's experience teaching in an academic department, last-minute timetable changes are stressful to all involved; our hope is that this framework provides a tool that decision-makers can use to quickly, optimally, and objectively reshuffle teaching assignments when necessary.
  
  
  
  § ACKNOWLEDGMENTS
  
  
  This work was supported by a Summer Undergraduate Research Experience grant from the University of Portland College of Arts & Sciences.
  
  plain
  
  
  