Abstract
The exam scheduling problem is one of the most interesting and common optimization problems to the university management. In these years, it has been solved with various methods using meta-heuristics and intelligent algorithms. Base on the requirement from University of Connecticut, we present in this paper an optimization solution with Simulated Annealing method. The solution satisfies the specific schedule requirement of final exams in University of Connecticut, also the general final exam schedule requirement. The report is in its initial stage of the research and does not necessarily reflect the complete picture of the whole project.
Keywords: Exam Scheduling, Scheduling Problem, SA, Simulated Annealing, Timetabling
1 Introduction to Exam Scheduling Problem
The exam scheduling problem is a specific case for the scheduling problems, which has a long story since 2500 years ago Sun Tzu wrote a fantastic scheduling strategy paper from military perspective.
As an important application of the Scheduling problem(Others we have course scheduling problems, airline crew and flight scheduling problems, job and machine scheduling , etc.)［1］, the definition of exam scheduling problem is direct and simple:
“A combinatorial optimization problem that consists of scheduling a number of examinations in a given set of exam sessions so as to satisfy a given set of constraints.［2］”
We take the following objects into consideration: Student, Exam, Day/Period. Assuming that we have two days for the final exams. There are 4 periods each day, meaning a total of 8 periods. 24 exams are scheduled into these 8 periods, which is the main challenge of this problem. This is a little more difficult than putting 24 balls into 8 boxes, since we still have the student information. Constraints are, for example, students should not have two or more exams at the same time, or have four exams on the same day (hard constraints and soft constraints). Those constraints, which must be always satisfied in the solution, are called hard constrains, such as one students just have one exam at one period. And soft constraints should be maximally satisfied, but do not need to be 100% satisfied. We want to minimize the weighted sum of conflicts of hard constraints and soft constraints.
We use a variation of D. de Werra’s[14] definition of the timetabling problem. Note that a class consists of a set of students who follow exactly the same program. So Let:
- E={e1,. . . ,en} a set of exams
- S={s1,. . . ,sm} the set of students
- D={d1,. . . ,dz} the set of the examination days
- P={p1,. . . ,ps} the set of periods (sessions) of the examination days.
Since all the students registered in a class ci follow the same program, we can therefore associate for each class ci an exam ei to be included in the examination schedule. So all the students registered in class ci will be required to pass the exam ei.
2 Introduction to Simulated Annealing Algorithm
We define S to be the solution space, which is the finite set of all available solutions of our problem, and f as the real valued cost function defined on members of S. The problem is to find a solution or state, i ∈ S, which minimizes f over S. SA is a type of local search algorithm that starts with an initial solution usually chosen at random and generates a neighbor of this solution, and then the change in the cost f is calculated. If a reduction in cost is found, the current solution is replaced by the generated neighbor. Otherwise (unlike local search and descent algorithms, like the hill climbing algorithm), if we have an uphill move that leads to an increase in the value of f, which means that, if a worse solution is found, the move is accepted or rejected depending on a sequence of random numbers, but with a controlled probability. This is done so that the system does not get trapped in what is called a local minimum (as opposed to the global minimum where the near optimal solution is found). The probability of accepting a move which causes an increase in f is called the acceptance function and is normally set to:
exp(−ϕ/T )
where T is a control parameter, ϕ the difference of cost. We can see that, as the temperature of the system decreases, the probability of accepting a worse move is decreased, and when the temperature reaches zero then only better moves will be accepted which makes simulated annealing act like a hill climbing algorithm[16] at this stage. Hence, to avoid being prematurely trapped in a local minimum, SA is started with a relatively high value of T. The algorithm proceeds by attempting a certain number of neighborhood moves at each temperature, while the temperature parameter is gradually dropped.
Algorithm of the SA algorithm shows as below:
Algorithm 1 Simulated Annealing Algorithm
Select an initial solution i ∈ S
Select an initial temperature T0 > 0
Select a temperature reduction function α
Repeat
Set repetition counter n = 0
Repeat
Generate state j, a neighbor of i
calculate ϕ = f(j) – f(i)
Ifϕ < 0 Then i = j
Else
generate random number x ∈ [0, 1]
If x < exp(-ϕ/t) Then i = j
n = n + 1
Until n = maximum neighborhood moves allowed at each temperature
endif
endif
Update temperature decrease function α
T = α · (T)
Until stopping condition = true.
3 SA Applied to The Exam Scheduling Problem
Based on the requirement of University of Connecticut, we have the following information:
- Number of periods/days.
- Exam information: Exams each student takes. (Student ID, Exam ID)
- Room Information: Capability of each Room. (Room ID, Capabilit)
We have the following constraints:
Hard Constraints:
- Two exams can not be at the same time.
- Room should suffice exam cap.
- Each exam is located to at most 1 room, and to at most 1 period is already there.
- Two exams can not share the same room in 1 same period.
Soft Constraints:
- Students should not have more than or equal to 3 exams on the same day.
- Students should not have more than or equal to 4 exams in 2 consecutive days.
- Students should not have exams in 2 consecutive days, either case 1 (2 in day1, 1 in day 2) or case 2 (1 in day1, 2 in day 2).
Based on the the above requirement, we did the following steps.
(1) Transformation
We create (0-1) matrix “student_exam_matij”, i=1,…,n_student, j=1,…,n_exam
(2) Initialization
- Initialize assignments for exams to periods, one exam to 1 period. And create (0-1) matrix “exam_period_mat”.
- Initialize assignments for exams to rooms, one exam to 1 room. And create (0-1) matrix “exam_room_mat”.
- Initialize assignments for exams to days, one exam to 1 day. And create (0-1) matrix “period_day_mat”.
(3) Cooling function
We have two ways of temperature cooling function:
- Simple linear cooling (Randelman and Grest):
- The exponential temperature cooling function (Kirkpatrick) :
(4) Neighbor Function
By randomly choose a row, and in the same row, we exchange the element which equals to 1 to another random element which equals to 0. Then we get a neighborhood to the former solution.
(5) Cost Function
By weighted summarize all thee hard constrains and soft constrains. We get the total cost.
(6) Applying the SA algorithm to get the optimization solution.
The code is programmed in R. we use R Package “optim()” to computer the optimization solution.
Reference
[1]Patrick Weaver, 2007, A BRIEF HISTORY OF SCHEDULING
[2] Nader Chmait, Khalil Challita, 2013, Using Simulated Annealing and Ant Colony Optimization Algorithms to Solve the Scheduling Problem, Computer Science and Information Technology 1(3): 208-224