Teacher Assignment Program
Master’s Project Final Report
University of Colorado
Maria Lizarraga
June 21, 2010
Lizarraga – Final Report 4 7/10/2010
Abstract
Local search techniques are a popular choice for solving high school timetabling problems. Real world scheduling constraints make scheduling of teachers to a class a difficult problem to solve. By strategically selecting a component of the schedule to change based on the constraint violations and then selecting a neighborhood based on the violation, better local search solutions can be found more quickly, allowing more stringent constraint criteria to be used successfully. The solution provided by the Teacher Assignment Program allows the user to dynamically apply constraints and set their associated weight. It uses strategically generated neighborhoods to optimize the solution.
1 Introduction
I was sitting next to my husband one day as he was trying to put a schedule together for his department in high school. I asked him, “Why do you have to do this? Doesn’t the administration do this for you?” As it turns out, the administration does put a schedule together for them, only it comes back with several problems that need to be fixed. One example of a problem is when a teacher is assigned to a class that they are not certified to teach. Take for instance, a teacher assigned to teach lifeguarding has to be certified as a lifeguard instructor.
OK, I understand the problem of assigning teachers to a schedule, so I thought. Yes it is a combinatorial problem, but after all, this is the 21st century. How many hundreds of schools have to do this? Yes, I covered the traveling sales problem in school. Surely, they have learned to solve this very common scheduling problem with some level of acceptability. I guess this is their level of acceptability.
Naively, I think, “I’ll solve this problem for you. I’ll create you an application that will find an optimal solution.” My first thought is that because it is a combinatorial problem, all I would need to do is to minimize n, the number of inputs into the problem. Then I could find an optimal solution. I quickly put some numbers together. The number of permutations for one period is:
(N!) / (N - C)!
where
N = number of teachers and
C = number of classes.
Roughly the number of permutations for multiple periods would be:
((N!)/(N - C)! )P
where
N = number of teachers,
C = number of classes per period, and
P = number of periods.
I say roughly, because realistically each period does not contain the same exact number of classes per period. For a small department of four teachers with roughly three classes per period for seven periods, the number of permutations would be:
((4!) / (4 - 3)! )7 = 4,586,471,424
This is a big number, but how much computing time are we talking about? My laptop has a CPU speed of 2.27 GHz. To search the entire problem space without taking into account constraints, the order of magnitude of computing time would be roughly the total number of permutations divided by 2.27GHz. The order of magnitude would be:
4,586,471,424 / 2.27 e 9 @ 2 sec
This is a doable number. But if I was to create an application for my husbands department with 6 teachers and approximately 4 classes per period for 7 periods the numbers look like:
((6!) / (6 - 4)!)7 @ 7.8 e 17
The execution time would be in the order of:
7.8 e 17 / 2.27 e 9 @ 11 years
on my laptop. Finding an optimal solution with these numbers is not doable because of the amount of time it would take. The problem then becomes one of finding an acceptable solution. This is what the school administration does. They are solving the scheduling problem for hundreds of teachers with hundreds of classes.
The eleven years is an approximation to search the entire problem space. It doesn’t take into account the amount of time needed to determine if the solution meets any specified constraints.
This is a high-school timetabling problem. The rest of this paper describes this problem by first discussing some basic scheduling theory along with the mathematical formulation of the problem. It then goes into some techniques and approaches that have been used by others. With this basic foundation, I describe in more depth this problem and my approach to solving it. Finally, I will cover the results of my solution and indicate areas that I think can be improved upon.
2 Scheduling Problem
Scheduling problems occur everywhere in everyday life. They come in all types, from scheduling people for an appointment at a doctor’s office, to scheduling tasks on a software project, to scheduling machines in a machine shop. A schedule can be for people, activities, or things. In its most basic form the scheduling problem is sequencing problem. In [1], Conway, Maxwell, and Miller describe the sequencing problem as:
1) a is the aggregate consequence of performing task A first, followed by B.
2) b is the aggregate consequence of performing task B first, followed by A.
3) Since a is preferable to b the ordering “A, then B” is selected.
In [2], Pinedo uses the machine shop in describing scheduling problems. The single machine is the foundation from which all other machine environments are modeled. There are several other types of machine environments. Below are a few examples of other machine environments.
· Parallel Machines—identical machines in parallel.
· Flow Shop—multiple machines in series.
· Flexible Flow Shop—a combination of the parallel machines with the flow shop in which there are identical machines at each step of a process (series).
The scheduling problem is typically solved as a parallel machine environment problem. There will be more discussion on this later.
2.1 Mathematical Formulations
De Werra in [3] gives a mathematical formulation for the class-teacher model of the timetabling problem. He starts with the simple that is solved in polynomial time. He defines the following terms:
· C = {c1,…,cm} be a set of all classes
· T = {t1,…,tn} be a set of all teachers
· P = {1,…,p} be a set of periods}
· Rmxn, requirements matrix such that rij is the number of periods assigned to class ci and teacher tj.
He defines the problem as follows:
Find:
xijk (i = 1,….,m; j = 1,…,n; k= 1,…,p)
Where:
xijk = 0 or 1 (i = 1,…,m; j=1,…,n; k=1,…,p).
Such that
p
å xijk = rij (i = 1,…,n; j=1,…,n)
k=1
n
å xijk = 1 (i = 1,…,m; k=1,…,p)
j=1
m
å xijk = 1 (j = 1,…,n; k=1,…,p)
i=1
This can be read as find a solution that assigns lectures to a class, a teacher, and a period such that:
· xijk = 1 if class i and teacher j meet at period k, 0 otherwise
· Each teacher is assigned to the required number of lectures given to class
· Each teacher is assigned to only one lecture per period
· Each class is assigned to only one lecture per period
· So that at most one teacher and one class is assigned to each lecture
De Werra [3] goes on to state that a solution exists to Problem1 so long as:
m
å rij <= p (j=1,…,n)
ii=1
n
å rij <= p (i=1,…,m)
j=1
The required number of lectures assigned to a teacher and a class is less than or equal to the number of periods.
Problem1 is not a realistic problem. There are usually several constraints that need to be considered. In [4], Junginger modifies the problem as follows to consider the modified constraints.
Find:
xijk (i = 1,….,m; j = 1,…,n; k= 1,…,p)
Where:
xijk = 0 or 1 (i = 1,…,m; j=1,…,n; k=1,…,p).
Such that
p
å xijk = rij (i = 1,…,n; j=1,…,n)
k=1
n
å xijk = tik (i = 1,…,m; k=1,…,p)
j=1
m
å xijk = cjk (j = 1,…,n; k=1,…,p)
i=1
The two changed constraints can be read as follows:
· tik is 1 if the teacher is available to teach course i in period k and is 0 otherwise.
· cjk is 1 if the class taught by teacher j in period k is available and is 0 otherwise.
This problem is NP-Complete as shown by Evan in [14] which means it can only be solved with the use of heuristics.
In order to optimize the solution, some sort of weight has to be added to the problem. Junginger in [4] does this by adding the following objective function
m n p
min å å å wijkxijk
i = 1 j = 1 k = 1
where a weight is added to the objective function for each lecture in which an undesirable condition occurs.
By adding weights to the problem and comparing one schedule against another, searching for a solution becomes a problem of finding a schedule that minimizes the total weight. In the generic scheduling problem, this is known as the objective function. The feasibility problem becomes an optimization problem. In finding a feasible solution, a solution technique has to find any acceptable solution and can stop there. The optimization problem tries to find the best solution within some given execution time limit criteria. It does not guarantee finding the optimal solution. The execution time can be limited by criteria such as:
· all possible solutions are tested,
· a fixed number of iterations have been completed, or
· a fixed time constraint is reached.
It should be noted that an optimization problem can easily be made into a feasibility problem by determining whether a candidate solution meets some level of threshold.
3 Techniques and Approaches
The techniques used to solve most scheduling problems, in general, can also be applied to the high school timetabling problem. In [6], Schaerf provides a survey of the papers on timetabling up to 1999. Even though the paper is dated, the basic techniques and approaches are the basically the same as those covered by Pinedo [2] and [5]. Some of these techniques have used object oriented program, including Tan in [10].
Schaerf [6] indicates that because of the difficulty in solving timetabling problems, they require heuristics which don’t guarantee an optimal solution. The techniques and approaches he discusses include local search techniques, genetic algorithms, ant colony optimization, linear programming, algorithms on network flow, and color graphing techniques.
The rest of this section discusses local search techniques, more specifically, tabu-search and simulated annealing. It also discusses genetic algorithms and Ant Colony Optimization. These are some of the more widely used techniques. Lastly, I will discuss some the benefits and drawbacks of linear programming
3.1 Local Search Techniques
Table 1. Local search example
Local search techniques are often applied to timetabling scheduling problems. It starts with an initial candidate solution and continually tries to improve the solution by selecting the next candidate solution from within the locality of the current candidate solution, hence the name local search. A possible solution within the locality is created by mutating a component of the current candidate solution. These mutated solutions are referred to as the neighborhood. Local search techniques are differentiated from one another most often by the criteria they use to accept a neighbor solution as a candidate solution. For example, some use a deterministic method and others use probabilistic method.
The basic algorithm of a local search heuristic as it pertains to the high school timetabling problem is as follows.
A. Initialize
1. Create initial candidate solution using any technique
2. Calculate candidate.ObjectiveFunctionValue
3. Make solution = candidate
4. Make aspirationCriteria = solution.ObjectiveFunctionValue
B. Find next candidate
1. Obtain candidate neighborhood solutions
2. Make candidate = the next candidate solution chosen from the possible neighborhood solutions
C. Test candidate.ObjectiveFunctionValue against aspirationCriteria
1. If candidate.objectiveFunctionValue < aspirationCriteria, then
solution = candidate, and
aspirationCriteria=candidate.objectiveFunctionValue
D. If the time limit criterion is not yet reached, return to step B.
The table 1 shows an example of what the data could look like.
Iteration / S / CC / N1 / N2 / N3 / NC1 / 30 / 30 / 29 / 42 / 36 / 29
2 / 29 / 29 / 30 / 31 / 42 / 31
3 / 29 / 31 / 15 / 37 / 29 / 15
4 / 15 / 15 / 27 / 19 / 23 / 19
5 / 15 / 19 / 33 / 20 / 5 / 5
The variables are defined as follows:
· S - solution weight
· CC - current candidate weight
· N1 - neighbor 1 weight
· N2 - neighbor 2 weight
· N3 - neightbor3 weight
· NC - selected neighbor weight
In this example the initial solution weight is 30. The time limit criterion is 6 iterations. The method proceeds as follows:
1. Neighbors N1, N2, and N3 are chosen using a neighborhood selection process. Then using some selection criteria, N1 with a weight of 29 is chosen as the selected neighbor and set to the current candidate. Because the weight is lower than the solution weight of 30 it is also set as the solution