Background

Scheduling Rules

• Common block classes are scheduled manually during the common blocks.  Those classes are

1. ACCT: 2001, 2101, 3201, 3202, 3221, 3260, 4203, and 4243
2. BADM 2710 (The BADM class is cross-taught with ACCT 2101, so it’s final exam is scheduled with that ACCT course)
3. MATH 1020, 1030, 1060, 1070, 1071, 1131, 1132, 2110, 2210, 2410 and 3160
4. CHEM 1127 and 1128
5. **From semester to semester these courses vary slightly.  They can be scheduled manually**

• In ART, DMD and DRAM we scheduled based upon the lab component of the course
• In GSCI 1050 and 1052 we schedule based upon the lab component
• We schedule all seminars
• We schedule everything else based upon the lecture component

Finally, we only schedule active classes with enrollments.  Non-WW courses without classrooms get final exam times but not classrooms.

Evening classes are those starting at 6:00 or later.

The BADM class is cross-taught with ACCT 2101, so it’s final exam is scheduled with that ACCT course.

Every semester we get a list from the ACCT and MATH departments that tell us which courses, and which sections we want in each of the blocks.  This varies from semester to semester in a couple of significant ways:

• The courses in the blocks are not constant.  A MATH course may be added or may be dropped from the block.
• The courses are not always assigned to the same block.  For example, one semester MATH 1020 may be in MATH block 1 and the next it will be in MATH block 2.
• The sections of a course may not always be in the block.  For example, we might get a request that 10 sections of MATH 2210 be in the block but 5 sections of MATH 2210 should not be.

My general feeling is that we should handle the common blocks manually.  We can reserve some final exam blocks for the common exams, then just add those exams to the blocks after the optimizer runs.

Notes:

• Student with 2 WW courses scheduled at the same time have a conflict.
• WW courses are assigned an exam time during finals week.  However, they do not need to be assigned a room. In the unusual situation where such a class needs a room we can do that manually after the optimizer runs.
• Cross-listed exams are the ones with the same CRSE_ID, but different CRSE_OFFERING_NBR. Students register for only one of the sections of the combined course, so there should be no overlapping students between the two (or more!) combined sections. There is a combined sections ID shared by all sections that are combined and is unique to the sections that are combined.
• Sometimes we get requests from departments to break up a single section into multiple exam rooms or blocks.  We currently handle this manually after we do our mass assign, and I would anticipate that this would continue to be a manual process moving forward.
• Common blocks:  There are several exam periods that we reserve to only be used by a particular department.  For example, We have a Chemistry block where we *only* schedule CHEM 1127 and 1128.  So all and only CHEM 1127/1128 will reside in a particular block.  We do the same thing with ACCT and MATH, but those departments get two blocks each. To recap, there are 5 blocks that we reserve for only our common block classes.  These blocks house 2 groups of MATH and ACCT classes, and one group of CHEM classes.

Some other notes:

1. Combined courses often have the same section number, but this is unreliable.  What they do have is a combined sections ID: This number is shared by all sections that are combined and is unique to the sections that are combined.  I can find the table that this is located on if that will help.
2. Students register for only one of the sections of the combined course, so there should be no overlapping students between the two (or more!) combined sections.
3. Sometimes we get requests from departments to break up a single section into multiple exam rooms or blocks.  We currently handle this manually after we do our mass assign, and I would anticipate that this would continue to be a manual process moving forward.
4. Common blocks:  There are several exam periods that we reserve to only be used by a particular department.  For example, We have a Chemistry block where we *only* schedule CHEM 1127 and 1128.  So all and only CHEM 1127/1128 will reside in a particular block.  We do the same thing with ACCT and MATH, but those departments get two blocks each.
5. To recap, there are 5 blocks that we reserve for only our common block classes.  These blocks house 2 groups of MATH and ACCT classes, and one group of CHEM classes.

Requirement

Scheduling Optimization Model

Model Description

The model is developed in R, with data from an underlying Oracle database. Several optimization processes are specialized to several different tasks including:

• Assignment of exams to periods: the optimization process minimizes conflicts specified in the project requirement (Red curve in the video)
• Assignment of exams to rooms: the optimization process minimizes conflicts between exams in the same room, at the same period (Green curve in the video)

 

 

Data

Exams are created following the rules in Exam Scheduling Rules. Other data are collected correspondingly.

Optimization Algorithm

The model takes a heuristic approach for optimization using modifed simulated annealing. For more information, see Simulated Annealing

At each temperature, the algorithm loops for a number of times and select the best move. We are currently working on scaling the algorithm on Spark framework to run on our HPC cluster. SparkR package is used. More details will be updated.

The first optimization process minimizes conflicts specified in the project requirement while keeping the room assignments the same as the class meeting. During the second optimization process, rooms with exam conflicts are moved away.

The solution is better if a reasonably small cooling rate is selected.

Exam Solution

The exam solution is imported to the model database, then PeopleSoft system.

The initial result from the model is as following (Spring 16)

Conflict/Violation Type	Model	Traditional Method
2 at the same time:	0	650
3 in one day:	347	2536
3 over two days:	55	208
4 in two days:	420	1536
Faculty Effected	10	73

Note: There are many cases that an instructor teaches multiple sections of a class that are required to be scheduled at the same time (in common blocks), so it causes unsolvable conflicts for the instructor, so 10 faculty conflicts are actually unsolvable. This can be solved outside the model by assigning other instructors to proctor the exams of other sections.

Definitions

Exams

All the classes are scheduled to their exam periods. Online classes are not scheduled to rooms. A number of non-online classes do not have rooms

Cross-listed exams: exams of classes taught by the same instructor, in the same room, at the same period, and different students. However data show that there are students in more than 1 cross-listed classes

Common block exams: some exams are required to be scheduled in the same common blocks. Currently the model assigns multiple sections of the same course to the same period, not at the course level.

Periods

There are 5 periods each day from Monday to Saturday. Though there are classes on Sunday, Sunday is not used for scheduling.

Rooms

Only real rooms are used for modeling (for example WWWONLINE room isn’t. VARCTBA in Depot Campus Visual Arts Research Center included with 999 seats).

Decision Variables

There are 2 set of decision variables for assigning exams to periods, and exams to rooms, stored in 2 matrices.

exam_period_mat: Matrix row indices are exam IDs, and column indices are period IDs.

exam_room_mat: Matrix row indices are exam IDs, and column indices are room IDs.

Decision variables are of integer type, with values of either 0 or 1, indicating the assignments of exams to rooms or exams to periods.

Other Matrices

student_exam_mat: Matrix that stores data who takes which exams, an element (i,j) = 1 where student i takes the exam j. Data were read from PeopleSoft views

instructor_exam_mat: Matrix that  stores data which instructors proctor which exams, an element (i,j) = 1 where instructor i proctors the exam j. Data were read from PeopleSoft views

period_day_mat: Matrix that converts periods (1-30) to days (1-6)

period_day_four_exams_two_days_mat: Period to day conversion for 4 exams in 2 consecutive days

three_exams_two_days_1_all_periods and three_exams_two_days_2_all_periods: Define all periods that occur at intersections of days, either 2 exams on 1st day and 1 exam early the next day consecutively, or  1 exams on 1st day and 2 exam early the next day consecutively

evening_period: Matrix that specifies which periods are evening

(cont.)

Constraints and Violations

• Students’ constraints:
  • Students should not have 2 exams or more at the same time. Violation if sum(student_period_mat>=2)
  • Students should not have 4 exams in two consecutive calendar days. Violation if sum(four_exam_two_day_mat>=4)
  • Students should not have 3 exams in 1 calendar day. Violation if sum(three_exam_same_day_mat>=3)
  • Students should not have 3 exams in consecutive time blocks spanning 2 consecutive days. Violation if sum(three_exam_two_day_1_mat>=3)+sum(three_exam_two_day_2_mat>=3)
• Faculty members’ constraints
  • Instructors should not proctor 2 exams or more at the same time. Violation if sum(instructor_period_mat>=2)
• Resource constraints
  • There shouldn’t be multiple exams in the same room at the same period. Violation if sum(room_period_mat>=2)
  • The number of seats should suffice the exam student enrollment. Violation if sum(exam_room_sufficient_mat>0)
• Others
  • Finals for evening classes should be given in the evenings. Violation is zero initially as the model purposely assigns evening classes to have exams in the evening, but adjust later during the optimization.
  • Final exams are given in the room that the course normally meets in. Currently exams are assigned to the same rooms of the class meetings even though there are cases that the room cap is less than the exam enrollment. The difference is the violation counts. Exams of classes that have more than 1 rooms are scheduled to 1 selected room out of the class meeting rooms (current settings).
  • Final exams should generally be offered on the same day the class meets during the semester. Violation is zero initially as the model purposely assigns classes to have exams in the same days of class meeting, but adjust later during the optimization.
• Possible addition
  • Classes with multiple rooms should also have multiple rooms for exams

Penalties

Penalties are the weights put on different types of violations, which then form the total cost to be optimized. Very high weights are put on direct conflicts defined by hard constraints, such as students taking 2 or more exams at the same time, instructors proctoring 2 or more exams at the same time,etc. Low weights are put on others defined by soft constraints, such as students taking 3 on the same day, or 4 exams on 2 consecutive days, etc.