Research.doc - College of Engineering and Applied Science

By Steven Watson,2014-11-07 08:12
28 views 0
Research.doc - College of Engineering and Applied Science

    Teacher Assignment Program

    Master’s Project Final Report

    University of Colorado

    Maria Lizarraga

     June 21, 2010

    create you an application that will find an optimal Abstract

    solution.‖ My first thought is that because it is a Local search techniques are a popular choice for solving

    combinatorial problem, all I would need to do is to high school timetabling problems. Real world

    minimize n, the number of inputs into the problem. scheduling constraints make scheduling of teachers to a

    Then I could find an optimal solution. I quickly put class a difficult problem to solve. By strategically

    some numbers together. The number of selecting a component of the schedule to change based

    permutations for one period is: on the constraint violations and then selecting a

     neighborhood based on the violation, better local search

    (N!) / (N - C)! solutions can be found more quickly, allowing more

     stringent constraint criteria to be used successfully.

    where The solution provided by the Teacher Assignment

    N = number of teachers and Program allows the user to dynamically apply

    C = number of classes. constraints and set their associated weight. It uses

     strategically generated neighborhoods to optimize the

    Roughly the number of permutations for multiple solution.

    periods would be:

     1 Introduction P ((N!)/(N - C)! )I was sitting next to my husband one day as he was trying to put a schedule together for his department in where high school. I asked him, ―Why do you have to do N = number of teachers, this? Doesn‘t the administration do this for you?‖ C = number of classes per period, and As it turns out, the administration does put a schedule P = number of periods. together for them, only it comes back with several problems that need to be fixed. One example of a I say roughly, because realistically each period does not problem is when a teacher is assigned to a class that they contain the same exact number of classes per period. are not certified to teach. Take for instance, a teacher For a small department of four teachers with roughly assigned to teach lifeguarding has to be certified as a three classes per period for seven periods, the number lifeguard instructor. of permutations would be: OK, I understand the problem of assigning teachers to a 7((4!) / (4 - 3)! ) = 4,586,471,424 schedule, so I thought. Yes it is a combinatorial st problem, but after all, this is the 21 century. How This is a big number, but how much computing time many hundreds of schools have to do this? Yes, I are we talking about? My laptop has a CPU speed of covered the traveling sales problem in school. 2.27 GHz. To search the entire problem space Surely, they have learned to solve this very common without taking into account constraints, the order of scheduling problem with some level of acceptability. I magnitude of computing time would be roughly the guess this is their level of acceptability. total number of permutations divided by 2.27GHz. The order of magnitude would be: Naively, I think, ―I‘ll solve this problem for you. I‘ll

    4,586,471,424 / 2.27 e 9 2 sec

    Lizarraga Final Report 1


    This is a doable number. But if I was to create an 1) is the aggregate consequence of performing task application for my husbands department with 6 teachers A first, followed by B.

    and approximately 4 classes per period for 7 periods the 2) is the aggregate consequence of performing task numbers look like: B first, followed by A. 3) Since is preferable to the ordering ―A, then B‖ 7((6!) / (6 - 4)!) 7.8 e 17 is selected. The execution time would be in the order of: In [2], Pinedo uses the machine shop in describing scheduling problems. The single machine is the

     7.8 e 17 / 2.27 e 9 11 years foundation from which all other machine environments

     are modeled. There are several other types of on my laptop. Finding an optimal solution with these machine environments. Below are a few examples of numbers is not doable because of the amount of time it other machine environments.

    would take. The problem then becomes one of

    finding an acceptable solution. This is what the school Parallel Machinesidentical machines in parallel. administration does. They are solving the scheduling Flow Shopmultiple machines in series. problem for hundreds of teachers with hundreds of Flexible Flow Shopa combination of the parallel classes. machines with the flow shop in which there are identical machines at each step of a process (series). The eleven years is an approximation to search the entire problem space. It doesn‘t take into account the The scheduling problem is typically solved as a parallel amount of time needed to determine if the solution machine environment problem. There will be more meets any specified constraints. discussion on this later. This is a high-school timetabling problem. The rest of 2.1 Mathematical Formulations this paper describes this problem by first discussing De Werra in [3] gives a mathematical formulation for some basic scheduling theory along with the the class-teacher model of the timetabling problem. mathematical formulation of the problem. It then He starts with the simple that is solved in polynomial goes into some techniques and approaches that have time. He defines the following terms: been used by others. With this basic foundation, I describe in more depth this problem and my approach

    ,…,c} be a set of all classes C = {c1mto solving it. Finally, I will cover the results of my

     T = {t,…,t} be a set of all teachers solution and indicate areas that I think can be improved 1n

    upon. P = {1,…,p} be a set of periods}

     R, requirements matrix such that r is the mxnij2 Scheduling Problem number of periods assigned to class c and teacher t. ijScheduling problems occur everywhere in everyday

    life. They come in all types, from scheduling people for He defines the problem as follows:

    an appointment at a doctor‘s office, to scheduling tasks

    on a software project, to scheduling machines in a Problem 1 machine shop. A schedule can be for people, activities, or things. In its most basic form the Find: scheduling problem is sequencing problem. In [1], Conway, Maxwell, and Miller describe the sequencing x (i = 1,….,m; j = 1,…,n; k= 1,…,p) ijkproblem as:

    Lizarraga Final Report 2 11/7/2013

Where: Find:

    x = 0 or 1 (i = 1,…,m; j=1,…,n; k=1,…,p). ijk

     (i = 1,….,m; j = 1,…,n; k= 1,…,p) xijk

    Such that

    Where: p

    x = 0 or 1 (i = 1,…,m; j=1,…,n; k=1,…,p). ( x = r (i = 1,…,n; j=1,…,n) ijkijkijk=1

    Such that n

    p ( x = 1 (i = 1,…,m; k=1,…,p) ijkj=1 ( x = r (i = 1,…,n; j=1,…,n) ijkijk=1 m

    n ( x = 1 (j = 1,…,n; k=1,…,p) ijki=1( x = t (i = 1,…,m; k=1,…,p) ijkikj=1 This can be read as find a solution that assigns lectures to a class, a teacher, and a period such that: m

    ( x = c (j = 1,…,n; k=1,…,p) x = 1 if class i and teacher j meet at period k, ijkjkijki=1 0 otherwise

     Each teacher is assigned to the required number of The two changed constraints can be read as follows: lectures given to class

     t is 1 if the teacher is available to teach course i in ik Each teacher is assigned to only one lecture per period k and is 0 otherwise. period

     c is 1 if the class taught by teacher j in period k is jk Each class is assigned to only one lecture per period available and is 0 otherwise. So that at most one teacher and one class is assigned to each lecture This problem is NP-Complete as shown by Evan in [14] which means it can only be solved with the use of De Werra [3] goes on to state that a solution exists to heuristics. Problem1 so long as: m In order to optimize the solution, some sort of weight ( r <= p (j=1,…,n) ijhas to be added to the problem. Junginger in [4] does ii=1 this by adding the following objective function

    n mnp( r <= p (i=1,…,m) ijmin ( ( ( wx ijkijkj=1 i = 1j = 1 k = 1 The required number of lectures assigned to a teacher where a weight is added to the objective function for and a class is less than or equal to the number of each lecture in which an undesirable condition occurs. periods. By adding weights to the problem and comparing one Problem1 is not a realistic problem. There are usually schedule against another, searching for a solution several constraints that need to be considered. In [4], becomes a problem of finding a schedule that minimizes Junginger modifies the problem as follows to consider the total weight. In the generic scheduling problem, the modified constraints. this is known as the objective function. The feasibility problem becomes an optimization problem. In Problem 2 finding a feasible solution, a solution technique has to find any acceptable solution and can stop there. The Lizarraga Final Report 3 11/7/2013

optimization problem tries to find the best solution Iteration S CC N1 N2 N3 NC

    within some given execution time limit criteria. It 1 30 30 29 42 36 29

    does not guarantee finding the optimal solution. The 2 29 29 30 31 42 31

    execution time can be limited by criteria such as: 3 29 31 15 37 29 15

     4 15 15 27 19 23 19

    5 15 19 33 20 5 5 all possible solutions are tested,

     a fixed number of iterations have been completed, Table 1. Local search example

    or within the locality of the current candidate solution, a fixed time constraint is reached. hence the name local search. A possible solution

     within the locality is created by mutating a component It should be noted that an optimization problem can of the current candidate solution. These mutated easily be made into a feasibility problem by determining solutions are referred to as the neighborhood. Local whether a candidate solution meets some level of search techniques are differentiated from one another threshold. most often by the criteria they use to accept a neighbor

     solution as a candidate solution. For example, some 3 Techniques and Approaches use a deterministic method and others use probabilistic The techniques used to solve most scheduling method.

    problems, in general, can also be applied to the high

    school timetabling problem. In [6], Schaerf provides a The basic algorithm of a local search heuristic as it survey of the papers on timetabling up to 1999. Even pertains to the high school timetabling problem is as though the paper is dated, the basic techniques and follows.

    approaches are the basically the same as those covered

    by Pinedo [2] and [5]. Some of these techniques have A. Initialize

    used object oriented program, including Tan in [10]. 1. Create initial candidate solution using any


    Schaerf [6] indicates that because of the difficulty in 2. Calculate candidate.ObjectiveFunctionValue

    solving timetabling problems, they require heuristics 3. Make solution = candidate

    which don‘t guarantee an optimal solution. The 4. Make aspirationCriteria =

    techniques and approaches he discusses include local solution.ObjectiveFunctionValue

    search techniques, genetic algorithms, ant colony B. Find next candidate

    optimization, linear programming, algorithms on 1. Obtain candidate neighborhood solutions

    network flow, and color graphing techniques. 2. Make candidate = the next candidate solution

     chosen from the possible neighborhood The rest of this section discusses local search solutions

    techniques, more specifically, tabu-search and C. Test candidate.ObjectiveFunctionValue against

    simulated annealing. It also discusses genetic aspirationCriteria

    algorithms and Ant Colony Optimization. These are 1. If candidate.objectiveFunctionValue <

    some of the more widely used techniques. Lastly, I aspirationCriteria, then

    will discuss some the benefits and drawbacks of linear solution = candidate, and

    programming aspirationCriteria=candidate.objectiveFunctionValue

     D. If the time limit criterion is not yet reached, return 3.1 Local Search Techniques to step B.

    Local search techniques are often applied to timetabling

    scheduling problems. It starts with an initial The table 1 shows an example of what the data could candidate solution and continually tries to improve the look like.

    solution by selecting the next candidate solution from

    Lizarraga Final Report 4 11/7/2013

     Initial Iteration 1 Iteration 2 Iteration 3

    Class CC N1 N2 N3 N1 N2 N3 N1 N2 N3

    1 A B C D A B B A C D

    2 B A B B B C D C B C

    3 C C A C C A C B A A

    4 D D D A D D A D D B

    Weight 30 29 42 36 30 31 42 15 37 29

    Table 2. Neighbor mutations

     The variables are defined as follows: 5. In iteration five, N3 with a weight 5 becomes the

    selected neighbor and the solution. S - solution weight

     CC - current candidate weight

    6. In iteration six, N3 is chosen as the selected N1 - neighbor 1 weight neighbor. Since it does not improve the solution N2 - neighbor 2 weight weight, it is not set as the solution. N3 - neightbor3 weight

     NC - selected neighbor weight Note that the solution is selected using a greedy

     algorithm approach. However, the selection of the In this example the initial solution weight is 30. The candidate may or may not be a greedy selection process. time limit criterion is 6 iterations. The method In the preceding example, the candidate selection proceeds as follows: process did not use a greedy selection process.

    1. Neighbors N1, N2, and N3 are chosen using a The greedy algorithm selects the next solution only if it

    neighborhood selection process. Then using some makes an improvement in the solution. Several local

    selection criteria, N1 with a weight of 29 is chosen search techniques do not use a greedy algorithm in

    as the selected neighbor and set to the current selecting the neighbor from the neighborhood. Using

    candidate. Because the weight is lower than the a greedy algorithm in selecting the neighbor can cause a

    solution weight of 30 it is also set as the solution search to reach a local minimum situation, thereby

     prohibiting any further improvements to the schedule. 2. In the next iteration, neighbor N2 with a weight of A local minimum solution is not necessarily the

    31 is chosen as the selected neighbor and set as the optimum solution.

    current candidate. Because the weight is not less

    than 29, it does not become the solution. The following aspects of this heuristic are left to the

     designer to decide its implementation:

    At this point of the discussion, the acceptance

    criteria are not pertinent to showing how the basic how the initial schedule is created,

    algorithm works. The acceptance criteria will be how the neighborhood is defined, and discussed in more detail when discussing specific the criteria used to select a candidate from within local search techniques. the neighborhood. 3. In iteration three, N1 with a weight of 15 becomes Local search algorithms are widely used probably the selected neighbor. Because the weight is less because they are relatively simple to implement and can than the solution weight, N1 becomes the solution. find good solutions within a reasonable amount of time. 4. In iteration four, N2 becomes the selected 3.1.1 Tabu-search neighbor. Tabu-search is a local search technique. This search

    Lizarraga Final Report 5 11/7/2013

technique maintains a tabu list that contains mutations

    that are not allowed. The acceptance criteria in the Case Study

    high school timetabling problem would be the objective In [8], Clark uses a repair-based local search technique function of total weight. The next candidate to solve a high school timetabling problem. To solution is made by choosing the neighbor with the improve the performance of the search, Clark minimum weight, so long as the move to this candidate implements techniques such a multi-starts, strategic is not on the tabu list. oscillation, and tabu lists.

    How tabu list is populated is best illustrated by an Multi-starts is employed using a technique they call example. Refer to table 1 and table 2. In iteration rapid restarts in which a search is restarted at the best 1, assume the current candidate (CC) has a class1 in solution thus far when a solution doesn‘t improve after which teacher A is assigned. Assume N1 is created by a given number of iterations.

    the mutation that assigns class 1 to teacher B. On the

    next move, it would not make sense to assign teacher A Strategic oscillation is a technique used that changes the back to class 1. Such a scenario can cause the weights of some constraints temporarily during run candidate solution to oscillate between having teacher A time to prevent getting stuck in a local minimum. and teacher B assigned to class 1. To prevent this Repair-based local search selects a weighted random from happening, the mutation that would assign teacher violated constraint and then fixes it.

    A back to class 1 is put on the tabu list.

     Although some aspects of the problem cannot be put After several moves, the schedule may have changed under the umbrella of a tabu search, the approach enough such that moving class 1 from teacher B back to maintains a tabu list and checks if a mutation is on tabu teacher A may now make sense and may even provide a list as part of the selection process. For this reason, I better solution. Therefore, the tabu-list has a limited discuss it in this section. It serves as an example of the size, removing the oldest mutation from the list when variations used in some of the more recent the size limit is reached, allowing the mutation to implementation techniques.


     3.1.2 Simulated Annealing

    Continuing with the example, assume that N1 in the Simulated annealing is a local search technique that uses second iteration is rejected because the mutation that a probabilistic method for accepting a solution. It was creates it is on the tabu list. Even though it had the introduced by Kirkpatrick [9] in 1983. The lowest weight in the neighborhood, it is not selected. acceptance probability function is

    Instead of N1 chosen in the second iteration, N2 is

     (-/T)chosen. The mutation that created N2 is put on the e ,

    tabu list.


    On the third iteration, the selected neighbor solution is

    created by the move from teacher B to teacher A in = selectedNeighbor.objectiveFunctionValue - class 1. This mutation is still on the tabu list. candidate.objectiveFuctionValue and However, now the selected neighbor solution yields a T = is the Temperature and can be a function of the weight of 15 which is better than the aspiration weight. current count of iterations. Because it is better than the aspiration weight, the selection is allowed to occur. This value is compared to a random number between 0 and 1. If it is better than the random number it is Tabu search continues to evolve with new variations to chosen as the next candidate solution. the algorithm. Tabu-search has be used successfully in [8].

    Lizarraga Final Report 6 11/7/2013

    For example, let‘s refer back to Table 1, iteration 2. attempts to resolve the soft constraints. The problem N2 is the selected neighbor with a weight of 31. Let they are solving is assigning a course/teacher pair to a the current temperature be 400. The random number classroom.

    selected to compare against is .335. The probability

    function would be: Classroom Period

     1 2 3 4 5 (-(31-29))/400e .995 1 (2,1) (1,1) (3,1)

     2 (3,1) (1,2) (2,2)

    This value is greater than the random number of .335, 3 (3,2) (1,1) (2,2) (4,1) (3,2)

    so is chosen as the next candidate solution. This 4 (3,2) (4,1) (1,1) (2,1)

    means that the objective function of the newly selected 5 (3,1) (2,1) (1,2)

    candidate can be worse than the current candidate. Table 3. Initial schedule with (Course, Teacher) pairs This helps prevent this technique from getting stuck in a

    local minimum. The neighbor swaps are done by swapping

     course/teacher pairs from one period to another. If The temperature starts at a high number and can be the initial schedule (from [12]) is as shown in table 3, cooled at a rate of: where the pair is defined as (course, teacher), the

     schedule would clearly violate a constraint of assigning a

    T = a * T teacher to only one class per period. nn-1

    where a is a value between 0 and 1. This has the affect After one iteration, say the new schedule is as shown in of lowering the temperature so that T will approach 0. table 4 where period 1 is chosen to be swapped with n

     period 4. Note that only some pairs are swapped. Let‘s say the temperature has been lowered over The swap is made only if it improves the schedule or if multiple iterations to a temperature of 1. Now, the simulated annealing probability factor accepts the

     swap. (-(31-29))/1 e .14

     Classroom Period

    If the random number 335 is selected now, the selected 1 2 3 4 5

    neighbor would not be accepted. So the affect in the 1 (1,1) (2,1) (3,1)

    acceptance of a selected neighbor becomes more and 2 (3,1) (1,2) (2,2)

    more selective as the temperature decreases with the 3 (4,1) (1,1) (2,2) (3,2) (3,2) increasing number of iterations. 4 (3,2) (4,1) (1,1) (2,1) 5 (2,1) (3,1) (1,2) Because there is no tabu-list with this method, this Table 4. Neighborhood swap of period 1 and 4 method can oscillate between two neighbors, especially

    if the difference between them is small. Simulated 3.2 Genetic algorithms

    Annealing was used successfully in [9] and [12]. Genetic algorithms do not select from a local

     neighborhood, rather candidate solutions in the current Case Study generation are produced from the previous generation. In [12], Zhang, Liu, and Leung use simulated annealing One algorithm starts with a population of candidate with a modified neighborhood and had success when schedules determined by any selection process or at compared to other algorithms with similar test cases. random. The two best candidate solutions are chosen They used a phased approach in satisfying their hard and to be parents of the next generation children. Parts soft constraints in which phase one finds a feasible (solution components) of both parents are selected to schedule by satisfying all hard constraints and phase two create the children. The children replace the two Lizarraga Final Report 7 11/7/2013

    candidate solutions in the previous generation with the violations. The goal of phase two is to minimize the worst objective function values. total variance.

    According to Pinedo [2], the advantages of genetic This genetic algorithm uses cloning, crossover, and algorithms are that it is fairly simple to implement and mutation. None of the current generation is carried offers good solutions. However, the execution time forward to the next generation. Instead, each to find a good solution is longer when compared to member of the current generation is a clone, a child solutions that are tailored more to the specific problem. (crossover), or mutant of the previous generation at the

     percentages of 20%, 75%, and 5% respectively. Genetic algorithms carry forward several schedules

    where as simulated annealing and tabu-search carry A clone in the current generation is a copy of a member forward one schedule, making them special cases of the of the previous generation. The mutant is copy of a genetic algorithm. member from the previous generation with the teachers

     for a particular course section modified. In the 3.2.1 Case Study process described above for creating children, the fittest In [13], Gunawan, Ng, and Ong use a genetic algorithm parents were used to create offspring. In this process, for a teacher assignment problem at a university. the parents are chosen at random. It appears that They use a two phased approach. In the first phase, instead of using solution components from both parents teachers are assigned to courses they are qualified to to create one child, this process swaps one or two teach. In phase two, the teachers are assigned to solution components to create two children. different sections of the course. They were successful

    at creating a fall and spring schedule for teachers of the 3.3 Ant Colony Optimization

    Industrial Engineering department at their university. The Ant Colony Optimization (ACO) is somewhat

     modeled after the behavior of ants on their quest for The problem specifies a hard constraint on the food. Ants are able to find the shortest path from maximum number of different courses a teacher can their nest to a food source. All along the way, ants teach and a hard constraint on the number of teachers deposit a chemical substance called pheromone that can be assigned to a course. Phase one makes indicating to other ants whether to follow a particular sure these constraints are met. This phase also seeks route. The more ants that take a particular path the to balance the number of different courses a teacher is more pheromone that is deposited on that path, making assigned to teach. It uses a genetic algorithm to it even more likely that a certain path will be taken. accomplish this. The number of hard constraint

    violations is measured by a penalty function. A Unlike the previous methods discussed thus far, ACO feasible solution has a zero penalty function, no hard constructs a schedule, actually multiple schedules, constraint violations. instead of modifying a single schedule. These multiple

     construction processes represent different ants on Once a zero penalty function is achieved, the different trails. Each solution component maintains a information of teachers assigned to courses is then used variable which represents the amount of pheromone to assign the teacher to course sections. This phase deposited on it. A single schedule is constructed by attempts to balance the load, the number of teaching selecting a solution component to add to a schedule hours per week. It uses a genetic algorithm to based on a probability function that takes into account accomplish this. This load balancing is a soft the amount of pheromone deposited on the solution constraint and is measured by the amount of total component. The probability function can also take variance of the teaching load, which is the objective into account the following factors:

    function. Because the hard constraints have been

    resolved in phase one, this phase does not concern itself

    with hard constraint

    Lizarraga Final Report 8 11/7/2013

    factors that tailored the algorithm to the course objective function,

    timetabling problem. These proposed modifications iteration count, and improved the performance when compared to the heuristic desirability. results using the original Ant System algorithm. Examples of solution components for this timetabling Ants produce a negative pheromone to signal other ants problem would be class 1 assigned to teacher 1, class 1 not to follow a particular path. In [7], the authors assigned to teacher 2, all the way up to class n used this concept to apply negative pheromone to the assigned to teacher n. Each solution component has solution components that did not produce good results. an amount of pheromone deposited on it which can The algorithm with negative pheromone produced depend on the amount of times it was visited and on the better results than without it. value of the objective function in which the solution component was used. The first heuristic incorporated into their solution was to give priority in choosing a destination vertex that has ACO metaheuristic has several algorithms under its the minimum number of edges leading to it from the umbrella which, a lot of times, differ in how and how source. In the high school timetabling problem this much pheromone is deposited on the solution would be the equivalent to giving priority to a teacher components. The basic algorithm remains the same. or course that is highly constrained, for example if a According to Dorigo and co-workers in [11], the teacher has to teach a particular course. This will algorithm is: result in constructing a schedule that is less likely to have constraint violations, giving better initial results. Set parameters, initialize pheromone trails while termination condition not met do The second heuristic is to distribute the load of the Construct Ant Solutions source vertex to the destination vertices. In the high Apply Local Search (optional) school timetabling problem, this would have the affect Update Pheromones of creating more diverse schedules so that the solution endwhile component (a teacher assigned to a class) with the most pheromone doesn‘t always become part of the solution. After a solution is constructed for an ant, a local search This way all the ants don‘t produce the same results. can be applied to further improve the solution before the pheromone deposits are made. The pheromone The third heuristic was to give higher priority to updates are then made on the improved solution. courses that require more time to teach. There isn‘t an exact translation of this heuristic into the type of According to [11], ACO has been used to solve many high school timetabling problem addressed in this paper types of problems including routing problems, where one class takes up one period. However, it assignment problems, and scheduling problems. It has could be used to address other types of constraints such been used in machine learning problems and as a constraint that specifies that a course should be bioinformatics. ACO results keep up with some of taught by every teacher. These classes could be the best performing algorithms and, for some addressed first. problems, out perform other methods. The have used successfully by Djamarus and Ku-Mahamud in [7] and The last heuristic is to give higher priority to edges that by Zhang, Liu, and Leung in [12] represent the lecturer‘s expertise in selecting courses and also preferable time slots. This heuristic could be 3.3.1 Case Study used by the high school timetabling problem to address In [7], Djamarus and Ku-Mahamud used the Ant System preferred constraints, giving precedence in assigning method of the graph problem with the modification of classes affected by preferences over those that aren‘t using negative pheromone and adding four heuristic affected by any constraints. The first and third Lizarraga Final Report 9 11/7/2013

    heuristics address required constraints where this one non-linear equations into linear equations that may would address preferred constraints. work in some situations.

    3.4 Linear Programming 4 Problem Definition

    Linear programming finds the optimal solution for a The problem is to assign teachers to a given course given objective function by solving for variables while schedule given a dynamic set of constraints such that minimizing (maximizing) constraints. The number of constraint violations is minimized and that a mathematical formulation provided in section 2.1 is an teacher is only assigned to one class per period. The example of a linear problem. Several approaches have problem is an optimization problem.

     been applied to linear programming according to [2],

    Each spring in the high school environment, the school including integer programming, simplex methods, and

    administration determines the class schedule for the interior point methods.

    coming year. A simplified version of the process

    could look like the following. Searching for optimal solutions require an exhaustive search. In the introduction, the time to do an

     Determine course requirements exhaustive search is calculated for a few sample

     Determine course schedule scenarios. The different algorithms developed using

    linear programming have reduced the amount of time Assign teachers to the schedule

    and have made using linear programming a feasible Assign students to the schedule approach to solving some scheduling problems.

    However, the scheduling problem has to be expressed The problem addressed in this paper is to assign as a linear expression. teachers to a schedule. The input to this problem is the

     course schedule. The output is a class schedule. The benefit of linear programming is that it does find an

    For purposes of clarification I define the following optimal solution(s). Traditionally, the drawbacks would

    terms. have been the amount of resources it consumed as far as

     CPU time and memory. Today‘s computers allow

    larger problems to be solved. However, the size of Course A course is a subject content area. the problem is still a concern. Class A class is a course that is assigned to a specific period and is assigned a teacher. In [15] and [16], integer programming techniques were Period The time frame that a class is offered. used successfully on fairly large problems. In [16], a The period timeframes are set and so instead of university scheduling problem was tackled that had 25 dealing with the time the class is offered, the to 92 courses and 55 professors. It took up to 17,159 problem deals with the period the class is offered. equations and 19,295 binary variables. The tool is designed to deal with periods and not blocks or other variations of scheduling classes. Another drawback would be the inability of some problems to be expressed as a linear expression. In Pinedo [2] defines the scheduling problem by the the high school timetabling problem, a constraint following characteristics: involving multiple periods may be difficult to express as a linear equality or inequality. A constraint that states The machine environment, ththat Teacher A must teach French 5 period can be

     The processing characteristics and constraints expressed as a linear expression. However, the

     The objective to be minimized. constraint that states that a teacher‘s planning periods

     must not be consecutive would be more difficult if not

    The rest of this section further defines the problem impossible to express as a linear equality or inequality.

    using these three characteristics. Techniques have been developed to aid in converting

    Lizarraga Final Report 10 11/7/2013

Report this document

For any questions or suggestions please email