In its broadest context, an academic scheduling and timetabling problem deals with classes, sections of classes, tutorial and lab sessions, faculty members, teaching assistants, midterm and final exams, available time-slots, and available facility resources, in addition to certain enhancing features such as preferences of faculty members and teaching assistants, while providing conflict-free class schedules. The intricacy and combinatorial nature of such problems for relatively large universities highlight the need for developing efficient quantitative approaches for generating acceptable, flexible, and robust class schedules.

In this paper, we address a novel problem related to generating weekly workload schedules for teaching assistants at academic institutions. In order to illustrate the proof-of-concept along with modelling and algorithmic constructs, we focus on analysing a case study pertaining to the Department of Mathematics at Kuwait University. However, the proposed modelling and solution approach can be readily adapted to likewise study problems having similar intrinsic structures as faced by many relatively large-sized academic institutions worldwide.

In previous research (Al-Yakoob and Sherali, 2006, 2007, 2015), we designed a two-stage approach to address such a problem at Kuwait University (KU). Stage I of this approach (see Al-Yakoob and Sherali, 2007) deals with the generation of an efficient class timetable that provides flexible class and time schedules, while considering available resources such as classrooms, laboratories, and parking facilities, as well as related traffic issues. Stage II (see Al-Yakoob and Sherali, 2006; Al-Yakoob et al., 2010) subsequently assigns faculty members to sections of offered classes within individual departments, while permitting at most a 15% rescheduling of classes as mandated by the Office of the Registrar.

More specifically, the Mathematics Department at KU offers a number of sections for a deficiency Pre-Calculus class (Math91-1) for students majoring in science or engineering who have not passed the Mathematics Placement Aptitude Test. Similar deficiency Pre-Calculus classes oriented toward business students (Math91-2) and social science students (Math91-3) are also offered. In the sequel, we will use Math91 to jointly refer to Math91-1, Math91-2, and Math91-3. Moreover, certain freshman and sophomore level mathematics classes are offered along with problem-solving tutorial sessions (Al-Yakoob and Sherali, 2006). For ease in reference, we will refer to these problem-solving tutorial sessions simply as tutorials. A solution to the Stage II problem alluded to above specifies subsets of days on which certain tutorials are to be offered, without specifying time-slots and instructors, such that each tutorial is offered on a day that is disjoint from those on which the corresponding class is taught. Hence, another timetabling problem that emerges from this two-stage approach is the Teaching Assistant Workload Assignment Problem, denoted TAP, which is mainly concerned with assigning sections of Math91 and tutorials to available teaching assistants, and also with specifying required help-hours for each assistant. Note that the two-stage approach described in Al-Yakoob and Sherali (2006, 2007, 2015) handles the assignment of classes to faculty members, classrooms, and time-slots but it does not deal with Problem TAP, which is the principal focus of the present paper.

The classes that are offered along with tutorials in the Mathematics Department at KU are Calculus I (Math101), Calculus II (Math102), Calculus for Biology (Math103), Calculus for Social Studies (Math108), Linear Algebra (Math111), Discrete Math (Math115), Calculus III (Math211), Differential Equations (Math240), and Numerical Analysis (Math352). Furthermore, there are two types of help-hours offered for students: a) regular office-hours where a teaching assistant allocates a certain number of instructional hours for students, and b) other types of help-hours related to the Mathematics Laboratory (MathLab) to assist freshman and sophomore students in general. Note that MathLab is typically open for students on a daily basis from 9:00 a.m. to 5:00 p.m. with at least two assistants on duty during any given hour. MathLab is designed to complement the regular office-hours by providing students with convenient individual and group study environments, with available on-the-spot assistance as necessary.

In constructing schedules for assistants, certain essential weekly workload requirements must be satisfied, as detailed below with specific information displayed in Table 1:

The remainder of this paper is organized as follows. Section 2 presents a discussion of the literature related to Problem TAP. Section 3 introduces our notation along with certain preliminary modelling constructs. Section 4 formulates a mixed-integer program (denoted TAM), which selects valid combinations of weekly schedules for assistants from the set of all feasible weekly schedules. Sections 5 and 6 describe constraints that are used to characterize columns of Model TAM. A column generation algorithm is designed in Section 7 to solve the linear relaxation of Model TAM, based on which, a sequential variable-fixing heuristic is devised to solve Model TAM. Computational results and analyses related to solving Model TAM are presented in Section 8, and we close the paper in Section 9 with a summary, concluding remarks, and directions for future research.

Define the following set of integer decision variables: x s = number of times schedule s ∈ S is selected for assignment to assistants . Also, we define the following sets of parameters, whose values are known a priori for any given assistant’s schedule; these parameters define each column in Model TAM: δ s , t k = 1 if the assistant teaches a section of Math91- k , for k ∈ K , during time-slot t ∈ T 1 within schedule s ∈ S , 0 otherwise, λ s , t c = 1 if the assistant instructs a tutorial associated with class c during time-slot t ∈ T 2 within schedule s ∈ S , 0 otherwise , π s , t = 1 if the assistant serves in the MathLab during time-slot t ∈ T 3 within schedule s ∈ S , 0 otherwise .

The various problem constraints are formulated in turn next.

A) Assigning assistants to Math91

Offered sections of Math91 must be covered by the assistants, as enforced by constraint (4.1) below: (4.1) ∑ s ∈ S ∑ t ∈ T 1 δ s , t k x s = N k , ∀ k ∈ K .

To avoid clustering sections of Math91 during certain time-slots within T 1, the following constraint sets upper bounds on the number of sections of these classes that are offered during any such time-slots: (4.2) ∑ s ∈ S δ s , t k x s ⩽ U t k , ∀ t ∈ T 1 , k ∈ K .

B) Tutorial sessions

Similar to Math91, tutorials are assigned to assistants as follows: (4.3) ∑ s ∈ S ∑ t ∈ T 2 STT λ s , t c x s = N STT c , ∀ c , (4.4) ∑ s ∈ S ∑ t ∈ T 2 MW λ s , t c x s = N MW c , ∀ c .

The following constraint spreads tutorial offerings by imposing upper bounds on the number of tutorials that are offered during each of the time-slots in T 2: (4.5) ∑ s ∈ S λ s , t c x s ⩽ U t c + 3 , ∀ t ∈ T 2 , c .

C) MathLab hours

Staffing the MathLab by assistants is achieved by setting lower and upper bounds on the number of assistants that are assigned during any given time-slot as follows: (4.6) ∑ s ∈ S π s , t x s ⩾ L t ML , ∀ t ∈ T 3 , (4.7) ∑ s ∈ S π s , t x s ⩽ U t ML , ∀ t ∈ T 3 .

D) Schedule selection

The following constraint ensures that the requisite number of valid schedules is selected for the set of teaching assistants: (4.8) ∑ s ∈ S x s = | A | , ∀ a .

Note that the schedule columns generated for the model, as described in the sequel, ensure that the assistants are actually assigned valid weekly workloads.

The objective function of Model TAM attempts to minimize the sum of the daily assignment time-spans for assistants. Letting c s represent the time-span associated with schedule s ∈ S, the objective function of the proposed model TAM is given by ∑ s ∈ S c s x s , which yields the following formulation: TAM : Minimize [ ∑ s ∈ S c s x s : ( 4.1 ) – ( 4.8 ) , x s integer , ∀ s ∈ S ] .

Next, we define a set of binary variables that will enable us to formulate suitable constraints in Sections 5 and 6 below, whose feasible region characterizes all valid schedules for assistants. This will facilitate the development of a column generation framework in Section 7 to solve Model TAM. Let K = { 1 , 2 , 3 }, and consider the following binary variables, where all indices are assumed to take on their respective values: X a , t k = 1 if assistant a teaches a section of Math91- k , k ∈ K , during time-slot t ∈ T 1 , 0 otherwise, Y a , t c = 1 if assistant a instructs a tutorial associated with class c ∈ C during time-slot t ∈ T 2 , 0 otherwise, Z a , t = 1 if assistant a serves in the MathLab during time-slot t ∈ T 3 , 0 otherwise, and W a , t l = 1 if assistant a allocates an office-hour during time-slot t ∈ T 4 in college l ∈ L , 0 otherwise . Note that if a section of Math91 is held in college l ∈ L, then all or a certain specified number of office-hours associated with this section as specified in Table 1 must be held in the same college. The same holds for tutorials held in college l ∈ { 1 , 2 }, as discussed further in Section 5 below.

Certain daily and weekly workload requirements are discussed in this section.

A) Daily workload requirements

For each assistant, the daily minimum and maximum workload requirements imposed by the Department of Mathematics at KU are enforced by constraints (6.1) and (6.2) given below for days in STT and MW, respectively: (6.1) L d ⩽ ∑ t ∈ T 1 STT ∑ k = 1 3 X a , t k + ∑ c ∑ t ∈ T 2 d Y a , t c + ∑ t ∈ T 3 d Z a , t + ∑ t ∈ T 4 d ∑ l = 1 3 W a , t l ⩽ U d , ∀ a and d ∈ S T T , (6.2) L d ⩽ ∑ t ∈ T 1 MW ∑ k = 1 3 X a , t k + ∑ c ∑ t ∈ T 2 d Y a , t c + ∑ t ∈ T 3 d Z a , t + ∑ t ∈ T 4 d ∑ l = 1 3 W a , t l ⩽ U d , ∀ a and d ∈ M W .

B) Distribution of teaching loads

For a given assistant, teaching duties pertaining to tutorials and to sections of Math91 should not be clustered on a given day and should be spread over the entire week as desired. Thus, constraints (6.3) and (6.4) below set lower and upper bounds as specified by the Department of Mathematics at KU on the total hours of teaching duties for days in STT and MW, respectively: (6.3) L STT d ⩽ ∑ t ∈ T 1 STT ∑ k = 1 3 X a , t k + ∑ c ∑ t ∈ T 2 d Y a , t c ⩽ U STT d , ∀ a and d ∈ S T T , (6.4) L MW d ⩽ ∑ t ∈ T 1 MW ∑ k = 1 3 X a , t k + ∑ c ∑ t ∈ T 2 d Y a , t c ⩽ U MW d , ∀ a and d ∈ M W .

C) Weekly workload

The overall weekly hour-load for a given teaching assistant a is required to lie within some specified range [ L , U ], as enforced by the constraint given next, where the weekly workload values are determined according to Table 1. In current practice, we have [ L , U ] = [ 40 , 48 ]. (6.5) L ⩽ [ 8 ∑ t ∈ T 1 ∑ k = 1 3 X a , t k + 8 ∑ c ∈ C 1 ∪ C 3 ∑ t ∈ T 2 Y a , t c + 4 ∑ t ∈ T 2 ∑ c ∈ C 2 Y a , t 4 + 10 ∑ t ∈ T 2 Y a , t 9 ] ⩽ U , ∀ a .

Teaching duties of an assistant during a given term must cover different class subjects (i.e. combinations of sections of Math91, and tutorials associated with different classes). Currently, the minimum and maximum number of different class subjects are given by two and three, respectively, where these bounds are enforced as follows. First, the following constraint guarantees that the maximum number of sections of Math91 that are assigned to an assistant is three: (6.6) ∑ t ∈ T 1 ∑ k = 1 3 X a , t k ⩽ 3 , ∀ a , and the following constraint guarantees that the maximum number of tutorials associated with any particular class that are assigned to an assistant is three: (6.7) ∑ t ∈ T 2 Y a , t c ⩽ 3 , ∀ a , c . Second, the following constraints ensure that the teaching load of an assistant contains at most three different classes: (6.8) H a ⩾ X a , t k , ∀ a , t ∈ T 1 , k ∈ K , (6.9) H a c ⩾ Y a , t c , ∀ a , t ∈ T 2 , c , (6.10) H a + ∑ c H a c ⩽ 3 , ∀ a . Third, the minimum number of different subjects is modelled via the following constraints: (6.11) Γ a ⩽ ∑ t ∈ T 1 ∑ k = 1 3 X a , t k , ∀ a , (6.12) Γ a c ⩽ ∑ t ∈ T 2 Y a , t c , ∀ a , (6.13) Γ a + ∑ c Γ a c ⩾ 2 , ∀ a , (6.14) 0 ⩽ Γ a ⩽ 1 , 0 ⩽ Γ a c ⩽ 1 , ∀ a , c .

Note that Γ a or Γ a c can be one only if at least one of variables on the right-hand side of (6.11) or (6.12), respectively, equals one, and are zero otherwise. Hence, (6.13) ensures the desired restriction, even with the Γ-variables declared to be continuous on [ 0 , 1 ] as specified in (6.14).

In this section, we formulate constraints to ensure that no two duties are assigned over consecutive periods in two distinct colleges, and also that the maximum number of switches between locations on any given day is smaller than some pre-specified value N L S . To achieve this, we first define the following binary variables, noting that T 1 d ≡ T 1 STT if d ∈ STT and T 1 d ≡ T 1 MW if d ∈ M W: g a , t l , d = 1 if assistant a is in college l ∈ L during time-slot t ∈ T 1 d of day d ∈ D , 0 otherwise , f a , t l , d ≡ g a , t l , d g a , ( t + 1 ) l , d = 1 if assistant a is in college l ∈ L during time-slots t and t + 1 , on day d ∈ D where t ∈ T 1 d ∖ { 12 , 20 } , 0 otherwise . Then the following constraints enforce the switching restrictions between colleges: (6.15) ∑ l = 1 3 g a , t l , d = 1 , ∀ a , t ∈ T 1 d , d ∈ D , (6.16) ∑ t ∈ T 1 d ∖ { 12 , 20 } ∑ l = 1 3 f a , t l , d ⩾ ( | T 1 d | − 1 − N L S ) , ∀ a , d ∈ D , (6.17) f a , t l , d ⩽ g a , t l , d , f a , t l , d ⩽ g a , t + 1 l , d , f a , t l , d ⩾ g a , t l , d + g a , t + 1 l , d − 1 , f a , t l , d ⩾ 0 , ∀ a , t ∈ T 1 d , d ∈ D , l ∈ L .

Constraint (6.15) assures that any assistant a is present in exactly one college during any time-slot t ∈ T 1 d of any given day d. Note that for a given day d, there are ( | T 1 d | − 1 ) time-slot transitions, and it is required that at most N L S of these transitions involve switching colleges. Hence, for any assistant a and day d, we need at least ( | T 1 d | − 1 − N L S ) f-variables to be one, as enforced by constraint (6.16). The f-variables are linearized via the logical restrictions given in constraint (6.17), where the restriction f a , t l , d ⩾ g a , t l , d + g a , t + 1 l d − 1 can be dropped since (6.16) automatically prefers the corresponding f-variables to be one whenever possible. Finally, any duty assignment is permissible for an assistant at any college l during time-slot t ∈ T 1 d of day d, only if this assistant is available at location l during time-slot ( t − 1 ) ∈ T 1 d of day d. This is accomplished via the constraints in Parts A–C below.

A) Presence at colleges on days in STT during the period 8:00 a.m.–2:00 p.m.

Define the set D J = { ( S , 0 ) , ( T , 12 ) , ( T h , 24 ) }, where the first element of each pair in DJ represents some day d ∈ STT and the second element represents an index j = { 0 , 12 , 24 } that is used to model the various defined time-slot activities. The following constraints handle the availability restrictions for days in STT during the time-duration 8:00 a.m.–2:00 p.m., noting that tutorials are not offered during this time-duration: (6.18) X a , t 1 + Z a , t + j + W a , t + j l ⩽ g a , t − 1 1 , d , ∀ a , t ∈ { 2 , … , 6 } , ( d , j ) ∈ D J , (6.19) X a , t 2 + W a , t 2 ⩽ g a , t − 1 2 , d , ∀ a , t ∈ { 2 , … , 6 } , ( d , j ) ∈ D J , (6.20) X a , t 3 + W a , t 3 ⩽ g a , t − 1 3 , d , ∀ a , t ∈ { 2 , … , 6 } , ( d , j ) ∈ D J .

B) Presence at colleges on days in STT for the period 2:00 p.m.–8:00 p.m.

Tutorials can be offered during the period 2:00 p.m.–8:00 p.m. on any day in STT, each of which is of one-hour-and-half duration, while other load activities on these days cover one-hour time-slots. Therefore, this case entails special attention since we are dealing with workload activities having time-slots of different durations. Note that the time duration of the hour-and-half tutorial time-slot t = 1 contains the one-hour time duration of the Math91 time-slot t = 7, the MathLab time-slot t = 7, and the office-hour time-slot t = 7. Moreover, the tutorial time-slot t = 1 partially overlaps with the one-hour time duration of the Math91 time-slot t = 8, the MathLab time-slot t = 8, and the office-hour time-slot t = 8. Similar comments apply for the tutorial time-slots t = 2 , 3, and 4. For convenience in formulation, we define the following sets, each element of which is given by a quadruple ( d , t , t 1 , j ), where d ∈ D STT , t ∈ { 7 , … , 12 } (one-hour MathLab time-slots), t 1 ∈ T 2 STT (an-hour-and-half tutorial time-slots), and where j is an index as before that will be used to appropriately model the various activity time-slots: D J S = { ( S , 7 , 1 , 0 ) , ( S , 8 , 1 , 0 ) , ( S , 8 , 2 , 0 ) , ( S , 9 , 2 , 0 ) , ( S , 10 , 3 , 0 ) , ( S , 11 , 3 , 0 ) , ( S , 11 , 4 , 0 ) , ( S , 12 , 4 , 0 ) } , D J T = { ( T , 7 , 5 , 12 ) , ( T , 8 , 5 , 12 ) , ( T , 8 , 6 , 12 ) , ( T , 9 , 6 , 12 ) , ( T , 10 , 7 , 12 ) , ( T , 11 , 7 , 12 ) , ( T , 11 , 8 , 12 ) , ( T , 12 , 8 , 12 ) } , D J T h = { ( T h , 7 , 9 , 24 ) , ( T h , 8 , 9 , 24 ) , ( T h , 8 , 10 , 24 ) , ( T h , 9 , 10 , 24 ) , ( T h , 10 , 11 , 24 ) , ( T h , 11 , 11 , 24 ) , ( T h , 11 , 12 , 24 ) , ( T h , 12 , 12 , 24 ) } , and D J STT = D J S ∪ D J T ∪ D J T h , where, D J S , D J T , and D J T h are respectively associated with the days Sunday, Tuesday, and Thursday. The second and third terms of each quadruple in D J STT represent the overlapping or partially overlapping time-slots associated with Math91 and tutorials. For example, for d = 1, the Math91 time-slot t = 8 partially overlaps with the tutorial time-slots t = 1 and t = 2. Based on the above discussion, we formulate the following constraints: (6.21) X a , t 1 + ∑ c ∈ C 1 Y a , t 1 c + Z a , t + j + W a , t + j 1 ⩽ g a , t − 1 1 , d , ∀ a , ( d , t , t 1 , j ) ∈ D J STT , (6.22) X a , t 2 + Y a , t 1 4 + W a , t + j 2 ⩽ g a , t − 1 2 , d , ∀ a , ( d , t , t 1 , j ) ∈ D J STT , (6.23) X a , t 3 + W a , t + j 3 ⩽ g a , t − 1 3 , d , ∀ a , ( d , t , t 1 , j ) ∈ D J STT .

C) Presence at colleges on days in MW

Constraints (6.24)–(6.26) below handle the availability-on-campus restrictions for d ∈ M W: (6.24) X a , t 1 + ∑ c ∈ C 1 Y a , t + j c + Z a , t + j + 24 + W a , t + j + 24 1 ⩽ g a , t − 1 1 , d , ∀ a , t = 14 , … , 20 , ( d , j ) ∈ { ( M , 0 ) , ( W , 8 ) } , (6.25) X a , t 2 + Y a , t + j 4 + W a , t + j + 24 2 ⩽ g a , t − 1 2 , d , ∀ a , t = 14 , … , 20 , ( d , j ) ∈ { ( M , 0 ) , ( W , 8 ) } , (6.26) X a , t 3 + W a , t + j + 24 3 ⩽ g a , t − 1 3 , d , ∀ a , t = 14 , … , 20 , ( d , j ) ∈ { ( M , 0 ) , ( W , 8 ) } .

D) One-activity-per-time-slot restrictions

Naturally, at most one activity can be assigned to any assistant during any given time period of the school week. Constraints (6.18)–(6.26) automatically imply this restriction for all time-slots of week except for the first time-slot of each day, which is handled next.

a) Restrictions for the first time-slot of days in D STT

Constraints (6.27)–(6.28) below respectively enforce the single-activity restriction during the first time-slot of days d ∈ D STT . (6.27) ∑ k = 1 3 X a , 1 k + Z a , 1 + ∑ l = 1 3 W a , 1 l ⩽ 1 , ∀ a , (6.28) ∑ k = 1 3 X a , 1 k + Z a , 13 + ∑ l = 1 3 W a , 13 l ⩽ 1 , ∀ a , (6.29) ∑ k = 1 3 X a , 1 k + Z a , 25 + ∑ l = 1 3 W a , 25 l ⩽ 1 , ∀ a .

b) Restrictions for the first time-slot of days in D MW

Constraints (6.30)–(6.31) below respectively enforce the single-activity restriction during the first time-slot of days d ∈ D MW . (6.30) ∑ k = 1 3 X a , 13 k + ∑ c Y a , 13 c + Z a , 37 + ∑ l = 1 3 W a , 37 l ⩽ 1 , ∀ a , (6.31) ∑ k = 1 3 X a , 13 k + ∑ c Y a , 21 c + Z a , 45 + ∑ l = 1 3 W a , 45 l ⩽ 1 , ∀ a .

We introduce in this section constraints to represent the daily work time-spans of assistants. The constraints formulated above enforce all the stated departmental rules regarding the generation of the weekly load of assistants. However, the schedule for each assistant can be enhanced by reducing the daily time-span of duties in an equitable manner. This is addressed next in Sections A–C.

A) Earliest time for Sunday

The following constraints provide the earliest activity time of an assistant on Sunday, starting at time zero for the first time-slot, where recall that the total number of time-slots on Sunday is | T 3 S | ≡ 12: (6.32) E a S ⩽ ( t − 1 ) X a , t k + | T 3 S | ( 1 − X a , t k ) , ∀ a , t ∈ T 1 STT , k ∈ K , (6.33) E a S ⩽ [ 6 + 1.5 ( t − 1 ) ] Y a , t c + | T 3 S | ( 1 − Y a , t c ) , ∀ a , t ∈ { 1 , 2 , 3 , 4 } , c , (6.34) E a S ⩽ ( t − 1 ) Z a , t + | T 3 S | ( 1 − Z a , t ) , ∀ a , t ∈ T 3 S , (6.35) E a S ⩽ ( t − 1 ) W a , t l + | T 3 S | ( 1 − W a , t l ) , ∀ a , t ∈ T 4 S , l ∈ L .

For any assistant a, constraint (6.32) asserts that the earliest time this assistant teaches a section of Math91 on Sunday is an upper bound on the variable E a S . If this assistant does not teach any section of Math91 on Sunday, then all the corresponding X-variables are identically zero, and hence, constraint (6.32) reduces to the redundant constraint E a S ⩽ | T 3 S |. Constraints (6.33)–(6.35) are formulated similarly for tutorials, MathLab sessions, and office-hours, respectively.

B) Latest time for Sunday

Likewise, the following constraints provide the latest activity time for an assistant on Sunday: (6.36) L a S ⩾ t X a , t k , ∀ a , t ∈ T 1 STT , k ∈ K , (6.37) L a S ⩾ ( 6 + 1.5 t ) Y a , t c , ∀ a , t ∈ { 1 , 2 , 3 , 4 } , c , (6.38) L a S ⩾ t Z a , t , ∀ a , t ∈ T 3 S , (6.39) L a S ⩾ t W a , t l , ∀ a , t ∈ T 4 S , l ∈ L .

For an assistant a, minimizing the term ( L a S − E a S ) achieves the objective of minimizing the time-span for this assistant on Sunday. The terms for Monday through Thursday can be formulated similarly; let these collectively be denoted by ( L a d − E a d ), ∀ d ∈ D.