In this section, we cover the problem of scheduling under time constraints and limited availability.
Exploration9.3.1.
Consider the last time you had to pick classes to fit a schedule. What were some things you had to consider in doing so? What sort of constraints did you consider neccesary, and which were considered preferences? How does your answers compare to your classmates?
Activity9.3.2.
Yafa is an incoming freshman at Fantasi College and she is picking classes for her first semester. Fantasi College has classes either on Monday-Wednesday-Friday from 8:30-9:30, 10:00-11:00, 12:30-1:30 and 2:00-3:00, and on Tuesday-Thursday from 8:30-10:00, 10:30-12:00, and 1:00-2:30.
Yafa has put together a list of potential classes she could take this semester, and assigned to them a score from 1 - 10 depending on her interest in the class, the time of day, and her own “research” looking up professors on external rating sites. (Yafa has not yet taken her introductory statistics course, and so doesn’t yet know how unreliable and biased these sites, and reviews in general, are.)
(Note that this is not altogether realistic, in that this is a massive oversimplification for the purpose of understanding the key ideas.)
# \((j)\)
Course Name and Time
Score \((c_j)\)
1
Art MWF 12:30-1:30
8
2
Art MWF 2:00-3:00
5
3
Art TuTh 10:30-12:00
7
4
Art TuTh 1:00-2:30
5
5
CS MWF 10:00-11:00
8
6
CS TuTh 10:30-12:00
8
7
Econ MWF 8:30-9:30
6
8
Econ MWF 12:30-1:30
7
9
Econ TuTh 10:30-12:00
8
10
Econ TuTh 1:00-2:30
7
11
Hist MWF 8:30-9:30
6
12
Hist TuTh 10:30-12:00
8
13
Lit MWF 10:00-11:00
7
14
Lit MWF 12:30-1:30
7
15
Lit MWF 2:00-3:00
6
16
Lit TuTh 8:30-10:00
5
17
MathA MWF 8:30-9:30
3
18
MathA MWF 10:00-11:00
5
19
MathA TuTh 8:30-10:00
7
20
MathB MWF 10:00-11:00
9
21
MathB MWF 12:30-1:30
7
22
MathB TuTh 10:30-12:00
8
23
Sem MWF 10:00-11:00
6
24
Sem MWF 10:00-11:00
8
25
Sem TuTh 10:30-12:00
8
26
Sem TuTh 10:30-12:00
7
Additionally, she has the following stipulations to her schedule:
No student is allowed to enroll in different offerings of the same class, MathA and MathB are considered different classes.
No student can enroll in more than 1 course in the same timeslot.
To prevent burnout, no student each student must have at least one time-slot off every day.
No student can enroll in more than 6 or fewer than 4 classes.
Each income student must enroll in a Freshman Seminar (Sem).
Because of her major, Yafa intends to enroll in at least 1 Math class this semester (either A or B, not exclusive).
Yafa wishes to get a headstart on her general education, so she wants to take at least one of either Literature (Lit) or Art (Art). Similarly, she wishes to take at least one of Economics (Econ) or History (Hist).
Let \(x_j\) be 1 if she takes course \(j\) and 0 otherwise.
(a)
What is a reasonable linear objective function to maximize?
(b)
Write out the constraints which restrict students to at most 1 offering of the same class.
(c)
Write out the constraints which restrict students to at most 1 course in a given timeslot.
(d)
Write out the constraints which ensure each student will have at least one free time-slot a day.
(e)
Write out the constraints which ensure each student is enrolled in at least 4 and at most 6 courses.
(f)
Write out the constraint which ensure each student enrolls in one seminar.
(g)
Write out the constraint which ensure that Yafa enrolls in (at least) one Math class.
(h)
Write out the constraints which ensure that Yafa is on track with her general education credits.
(i)
Write out the integer maximization problem we have constructed.
(j)
(Optional) Solve it:
Activity9.3.3.
Let’s call Yafa from Activity 9.3.2 student \(1\text{.}\) In a gross oversimplification suppose there were in total 5 students including Yafa registering, and that each class could sit at most 2 students.
Each student assigns their own score to each course, \(c_{ij}\) being the score that student \(i\) gives to course \(j\text{.}\) Let \(x_{ij}\) be 1 if student \(i\) enrolls in course \(j\) and 0 otherwise.
\(j\)
Course Name and Time
\(c_{1j}\)
\(c_{2j}\)
\(c_{3j}\)
\(c_{4j}\)
\(c_{5j}\)
1
Art MWF 12:30-1:30
8
10
4
6
9
2
Art MWF 2:00-3:00
5
8
5
5
7
3
Art TuTh 10:30-12:00
7
9
7
5
8
4
Art TuTh 1:00-2:30
5
6
3
5
6
5
CS MWF 10:00-11:00
8
2
8
9
5
6
CS TuTh 10:30-12:00
8
5
7
8
6
7
Econ MWF 8:30-9:30
6
6
8
4
7
8
Econ MWF 12:30-1:30
7
7
7
6
4
9
Econ TuTh 10:30-12:00
8
8
3
6
7
10
Econ TuTh 1:00-2:30
7
9
4
5
6
11
Hist MWF 8:30-9:30
6
5
7
7
6
12
Hist TuTh 10:30-12:00
8
6
8
9
7
13
Lit MWF 10:00-11:00
7
8
6
5
5
14
Lit MWF 12:30-1:30
7
8
7
6
7
15
Lit MWF 2:00-3:00
6
9
6
3
7
16
Lit TuTh 8:30-10:00
5
8
6
2
6
17
MathA MWF 8:30-9:30
3
2
5
5
6
18
MathA MWF 10:00-11:00
5
2
5
6
6
19
MathA TuTh 8:30-10:00
7
4
9
7
8
20
MathB MWF 10:00-11:00
9
1
1
1
8
21
MathB MWF 12:30-1:30
7
1
1
1
9
22
MathB TuTh 10:30-12:00
8
1
1
1
7
23
Sem MWF 10:00-11:00
6
10
9
7
4
24
Sem MWF 10:00-11:00
8
4
7
6
5
25
Sem TuTh 10:30-12:00
8
7
9
6
3
26
Sem TuTh 10:30-12:00
7
5
3
8
6
In addition to the constraints that all students have to abide by, we have the following constraint for each student:
Yafa (student 1) still has her constraints from Activity 9.3.2.
Student 2 has to take at least 1 Art class, either Computer Science (CS) or Math, and either Economics or History.
Student 3 has to take at least 1 Economics class, 1 Math and 1 Literature class.
Student 4 has to take a Computer Science class and a History class.
Student 5 has to take both Math classes.
(a)
How might the objective function and constraints from Activity 9.3.2 be adapted to this situation?
(b)
What additional constraints are required?
(c)
Depending on how you set up the objective function, a student who rates everything highly will be prioritized over a student who ranks everything more modestly. To prevent gaming the system, what could be done to ameliorate this effect?
(d)
The Dean approves one of the classes to be increased in size to a whopping 3 students. How can the dual problem inform how this choice of class should be made?
Now model a scheduling problem that is not oversimplified. Perhaps one based on your current or former institution(s).
Project9.3.6.
For the truly ambitious, model a scheduling problem for the offering of courses, factoring in preferred times, preferred courses, preffered classrooms, changes in staffing, fluctuating student demand and flow of courses in the future etc. 1
This is as open a problem as there can be. Someone who solves this problem will gain more recognition than if they solved all the Millennium Problems.
