Algorithms Used For Tackling Course Timetabling Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Timetabling is an area of increasing interest in the community of both research and practice in recent decades. Typical cases in this area include educational timetabling, sport timetabling, employee timetabling, transport timetabling and so on. In this study, we consider an educational timetabling problem. Educational timetabling problems are classified into two categories: exam timetabling and course timetabling. The later can be further divided into two sub-categories: post enrollment-based course timetabling and curriculum-based course timetabling. The main difference is that for post enrollment timetabling, conflicts between courses are set according to the students en-rollment data, whereas the curriculum-based course timetable is scheduled based on the curriculum published by the university. Every year or term in a university, each individual department has to design a new timetable for subjects or lessons. The timetabling problems are multi-dimensional assignment optimization and constrained combinatorial optimization problem that consists of allocating a set of lectures in between faculty and students in a finite period of time (typically a week), in available classrooms, that satisfies a set of constraints. University Course Timetabling Problem (UCTP) is one of its types. Many of these problems are tackled manually, which is a tough and time-consuming task. The impact of generating a timetable manually was when preconditions change; then whole work becomes unusable (low quality timetable), and has to be restarted from scratch. In this paper, we have surveyed different types of algorithms used to tackle Course Timetabling Problem and tabulated their various parameters along with merits, demerits, issues to be addressed and so on. Largely, the existing timetabling algorithm does not consider fitness value and the maximum number of free timeslots allocated. Therefore, there is a need to implement a Course Timetabling algorithm that can enhance the optimality and fitness.

Keywords

Hard Constraints, Soft Constraints, Fitness Function, Execution Time, Local Search, Genetic Algorithm, Particle Swarm Optimization, Tabu Search, Simulated Annealing.

1. INTRODUCTION

Timetabling is one of the common scheduling problems, which we see, in day-to-day life. It is a multi-dimensional assignment problem in which set of events, resources, students, faculty, classrooms and timeslots are scheduled according to given constraints depends on the specific problem. An Efficient solution of timetable problem of specific domain will not work well for some other domain problem depending upon the constraints specified. Generally, there are two types of constraints namely hard constraints and soft constraints. Hard constraints are constraints, which are not to be violated at any cost. Soft constraints are constraints, which can be accepted with a penalty associated to their violation. A feasible solution of timetabling problem is one, which satisfies all the hard constraints, and the quality of feasible solution is measured by satisfying soft constraints while satisfying all hard constraints as well.

Many algorithms have been proposed to solve the timetabling problem. In earlier days, graph-coloring method is used. It works well for small instances but as the number of instances increased, it could not work efficiently. Later stochastic algorithms like Genetic Algorithm, Stimulated Annealing Algorithm, Tabu Search Algorithm, etc., were introduced. There are two types of algorithms used namely local-area-based algorithms and population-based algorithms. Each type has its own advantages and disadvantages.

Local-area-based algorithms concentrate on exploitation i.e. they search in one direction without finding all the possible solutions. E.g., Simulated Annealing, Very Large Neighborhood Search, Tabu Search, etc. These kinds of algorithms improve the quality of solution.

Population-based algorithm starts with number of solutions and refines the solutions to get optimum solution. Therefore, this is called as global-area-based algorithms. It requires more time and premature convergence. E.g. Evolutionary Algorithm, Particle Swarm Optimization, Ant-Colony Optimization, Artificial Immune System, Genetic Algorithm etc. Various combinations of local-area-based and global-area-based algorithms are reported to solve timetabling problem.

The objective of this paper is to focus on various Course Timetabling algorithms. The rest of the paper is organized as follows. Section II presents various existing Course Timetabling algorithms. Section III presents the comparison of the timetabling algorithms along with the tables. Section IV highlights the performance metrices of the algorithms and section V concludes the paper with a summary of our contributions.

2. VARIOUS COURSE TIMETABLING ALGORITHMS

In this chapter, we will review most recent and significant works about the algorithms used for solving Course Timetabling Problem. Algorithms are grouped as local-area-based and population-based or global-area-based. Some algorithms used both kinds to obtain better results. The Following Course Timetabling algorithms are currently prevalent in use and these algorithms are summarized in Table1 and Table2.

2.1 A HYBRID SIMULATED ANNEALING WITH KEMPE CHAIN NEIGHBORHOOD ALGORITHM

Tuga M. et al. [1] proposed an algorithm to address a feasible solution for timetabling problem. A feasible solution is one that satisfies all hard constraints. This method proposes the solution by relaxing one of its hard constraints and creating a soft constraint to compensate.

Feasible solution is constructed for relaxed constraint problem by using graph-based method. In graph-based method, events are considered as nodes and there is an edge between two nodes if and only those events are assigned at the timeslot.

Simulated Annealing based approach is used for minimizing soft constraints. Simulated Annealing is a stochastic search method used in local search i.e. in each step, it moves either to better neighborhood solution if it finds or to a worse solution.

To improve diversification, kempe chain neighborhood is introduced. Apart from simple and swap neighborhood, kempe chain neighborhood operates over two selected timeslots. For this, bipartite graph is used in which each node consists of an event and a resource for one of its timeslot and an edge exists if and only if the two resources are used by conflicting events within those timeslots.

A kempe chain neighborhood is formed by choosing one resource randomly from timeslot t1 and corresponding event will trigger a chain which forms connected sub graph. New Timetable can be obtained by reassigning events in this chain to the events present in the pair timeslot.

2.2 TABU SEARCH ALGORITHM

Z.Lu et al. [28] and Khang Nguyen et al. [2] proposed an adaptive tabu search algorithm which follows a general framework consists of 3 phases namely initialization, intensification and diversification.

In initialization phase, feasible initial timetable is obtained using fast greedy heuristics. In fast greedy heuristics, at each step, one lecture is inserted into timetable at each time. In each step, two operations, one is selection of unassigned lecture and second is to determine a period-room for this lecture.

Intensification and diversification phases are used to minimize number of soft constraints while maintaining hard constraints satisfaction. Intensification uses tabu search, which explores the search space by replacing the current solution with non-recently visited neighboring solution even if the later is worse than current solution. Tabu list is maintained to avoid cycling and the search to go further by storing already visited solutions.

This approach introduces other significant features like original double kempe chains neighborhood structure, a penalty-guided perturbation operator, and an adaptive search mechanism. In Original double kempe chain neighborhood, two kempe chains are allowed to swap their lecture and period and thus producing new solution. In diversification, original double kempe chain neighborhood is used.

When the best solution cannot be improved using Tabu search, a perturbation operator is used. It is guided by perturbation strength. If perturbation strength is strong, restart will be at random. Otherwise, search will start from the just visited local optimum and search space is small. All the lectures are arranged in non-increasing penalty values according to the soft constraints. Highly penalized lectures are first assigned to a random selection of a given number of neighborhood moves.

2.3 VARIABLE NEIGHBOURHOOD SEARCH ALGORITHM

Salwani Abdullah t al. [3] proposed a very large neighborhood search to satisfy as much as possible soft constraints while maintaining hard constraints satisfaction. It proposes 11 neighborhood moves to produce as many solutions as possible so that it will satisfy soft constraints.

2.4 LOCAL SEARCH HEURISTIC ALGORITHM

Halvard Arntzen et al. [4] proposed a local search heuristic algorithm, which uses a simple adaptive memory search to improve the quality of an initial solution. The search is guided by tabu search mechanisms based on recency and frequency of certain attributes of previous moves.

IMPROVED MEMETIC ALGORITHM WITH LOCAL SEARCH

Majid Joudaki et al. [5] proposed a hybrid method, which is based on combination of improved Memetic and Simulated Annealing Algorithms using Simulated Annealing Algorithm as the local search routine increases exploiting ability of Memetic Algorithm. In addition, modifying Crossover operator of Memetic Algorithm and creating initial population by a heuristic-based method improves this algorithm.

In order to improve produced chromosomes and decreasing the number of violation of the constraints, a new operator is designed and added to Memetic Algorithm, called improvement operator.

2.6 A MAX-MIN ANT-COLONY OPTIMIZATION

Krzysztof Socha et al. [6] presented a Max-Min Ant-Colony optimization uses separate local search routine. In addition, it proposes appropriate construction graph and pheromone matrix representation. Construction graph is given by E - T, where E is events and T is timeslots. We can also decide whether move along list of timeslots and choose events to be placed or move along lists of events and choose suitable timeslots. Pheromone matrix is a matrix of values τ: E - T  R ≥ 0, where E is events and T is timeslots. These values are initialized to a parameter τ0 and eventually updated by local and global rules. At the end of the iterative search, event-timeslot assignment is converted into candidate solution (timetable). This can be improved by local search.

2.7 EVOLUTIONARY ALGORITHM

Sastry et al. [29] and Salwani Abdullah et al. [7] proposed an evolutionary algorithm which comprises of three stages: Selection, Reproduction and replacement. In the selection stage, the fittest individuals have a higher chance than the less fit of being chosen as parents for the next generation. The quality of the solution is measured in terms of a penalty value which represents the degree to which various soft constraints are satisfied.

Recombination and mutation operators applied to chosen parents perform reproduction. Recombination combines parts of each of two parents to create new individual while mutation makes small alteration to create new individual. Finally, in Replacement individuals of original population is replaced by the newly created ones and delete the worst ones.

2.8 GENETIC ALGORITHM

A. Colorni et al. [30] and Branimir sigl et al. [8] proposed a Genetic algorithm (GA) in which the natural analogy is population genetics. In GA, every possible solution is individual and after the generation of an initial set of feasible solutions i.e. population, individuals are randomly mated allowing recombination of genetic material. The new population so obtained undergoes a process of natural selection where favors the survival of the fittest individuals. The fitness of the individuals is evaluated by fitness function. Algorithm performance was significantly enhanced with modification of basic genetic operators, which restrain the creation of new conflicts in the individual.

Genetic algorithm uses basic genetic operators to generate new population of high fitness. Reproduction operator produces new generation in the increasing number from the old generation. Crossover randomly selects two individuals as parents and combines them to generate two new individuals. Mutation selects two individuals as parents and alters some parts of parents to create new generation.

The Search is directed by fitness function. The objective function is used to limit the number of individuals with infeasibilities. Filtering algorithm is used to filter infeasible solutions from feasible solution. Genetic repair converts infeasible solution to feasible solution by altering it as little as possible.

2.9 GUIDED SEARCH GENETIC ALGORITHM (GSGA)

Sadaf Naseem Jat et al. [9] proposed a genetic algorithm with a guided search strategy and a local search technique. The guided search strategy is used to create offspring into the population based on a data structure that stores information extracted from previous good individuals. The local search technique is used to improve the quality of individuals. In GSGA, initialization of the population by randomly creating each individual via assigning a random time slot for each event according to a uniform distribution and applying the matching algorithm to allocate a room for the event is done. Then, a local search (LS) method is applied to each member of the initial population. The LS method uses three neighborhood structures to move events to time slots and then uses the matching algorithm to allocate rooms to events and time slots.

After the initialization of the population, a data structure (MEM) is constructed, which stores a list of room and time slot pairs (r, t) for all the events with zero penalties (no hard and soft violation at this event) of selected individuals from the population. After that, this MEM can be used to guide the generation of offspring for the following generations.

The MEM data structure is reconstructed regularly, e.g., every n generation. In each generation of GSGA, one child is first generated either by using MEM or by applying the crossover operator. After that, a mutation operator followed by the LS method will improve child. Finally, the worst member in the population is replaced with the newly generated child individual. The iteration continues until one termination condition is reached.

2.10 CONSTRAINT BASED REASONING ALGORITHM (CBR)

Legierski et al. [31] and Ho Sheau Fen et al. [10] proposed a method which deals with an effectiveness of Constraint Programming (CP) for scheduling problem particularly for timetabling. The main advantage of the CP is declarativity, a straightforward statement of the constraints serves as a part of the program and it is compared with local search procedures. The CP's main features are constraint propagation and distribution. The constraint programming language Mozart-Oz allows to express complex constraints and create complicated, custom-tailored distribution strategy, which is needed for solving timetabling problem. Incorporation of the local search into constraint programming is needed as a method for optimization.

This approach uses constraints-based reasoning to search for the best preference value bsed on the student capacity for each lecture.

It automatically removes from the domain of variables all values that do not fulfill constraints. Constraint propagation does not remove all values that are in conflict with all constraints and its performance is measured as a trade-off between number of removed values and execution time. In the most cases constraint propagation does not lead to the solution (as it is also depicted in above-mentioned example). Therefore, there is always added to constraint propagation a distribution connected with search.

Distribution is based on incorporation of an additional constraint, often it is a constraint saying about equality of one variable to one value (one of the task of the distribution is to choose a proper variable and a value). When it is done a consistency is checked and there are three possibilities: a solution is found, variables domains are narrowed, but there is no unique solution, so distribution is made with another variable, the additional constraint is inconsistent with other constraints, so the backtrack is made and from chosen variable domain a chosen value is removed. This process is made in iterative way and is called search. Search is responsible for stopping after finding; first solution or some number of solution or all solution. Search forms a search tree, where each node is a state of variables.

2.11 ADVANCED GENETIC ALGORITHMS

Spyros Kazarlis et al. [11] proposed a method based on Genetic Algorithms (GAs), to solve university course timetabling problems is presented. This method incorporates GAs using an indirect representation based on event priorities, Micro-GAs and heuristic local search operators in order to tackle a real world timetabling problem.

2.12 PARTICLE SWARM OPTIMIZATION

S.F.H Irene et al. [12] proposed particle swarm optimization which is a computational method that optimizes a problem by iteratively trying to improve candidate solutions. Each solution is addressed here as particle. The candidate solutions move around the search space and finds best position for each candidate solution and overall best position according to fitness function. The process is repeated when new positions are discovered so that candidate solution can fit in new position, which is the best.

2.13 PSO WITH LOCAL SEARCH

S.F.H Irene et al. [13] presented a method which is a combination of particle swarm optimization and local search to effectively search the solution space in solving university course timetabling problem. Three different types of dataset range from small to large are used in validating the algorithm. The experiment results show that the combination of particle swarm optimization and local search is capable to produce feasible timetable with less computational time, comparable to other established algorithms.

2.14 PSO WITH CONSTRAINT BASED REASONING

S.F.H Irene et al. [14] presented a method which focuses on developing a hybrid algorithm consisting of a particle swarm optimization and constraint-based reasoning in solving university timetabling problem in generating a feasible and near-optimal solution. The result is compared against standard particle swarm optimization and hybrid particle swarm optimization-local search.

2.15 HARMONY SEARCH WITH BEES ALGORITHM

Khang Nguyen et al. [15] proposed a method which is concerned with the development of a new hybrid metaheuristic approach for solving a pratical university course timetabling problem. It is a combination of Harmony Search (HS) algorithm and the Bees algorithm.

2.16 GENETIC ALGORITHM WITH SEARCH BANK STRATEGIES

A.Araisa Mahiba et al. [16] proposed a new method of Genetic algorithm with Search Bank Strategies namely local, guided and tabu searches. Local Search is used to increase the offspring or solutions. Guided Search is used to narrow the solutions by using events data Structure. Tabu Search is used to remove the used solutions.

2.17 GENETIC ALGORITHM COMBINED WITH BEES ALGORITHM

NguyenBa Phuc et al. [17] presented a method, which combines the optimization capabilities of a genetic algorithm with bees algorithm. The main goal is to find the minimum of optimization problems.

2.18 FUZZY GENETIC ALGORITHM WITH LOCAL SEARCH

Meysam Shahvali Kohshori et al. [18] presented a fuzzy genetic algorithm (GA) with a local search for solving university course timetabling problem (UCTP). The local search is applied to use its exploitive search ability to improve the search efficiency of the proposed GA. Fuzzy logic is used to measure violation of soft constraints in fitness function to deal with inherent uncertainly and vagueness involved in real life data.

2.19 HYBRID HARMONY SEARCH ALGORITHM

Mohammed Azmi Al-Betar et al. [19] proposed a memetic computing technique that is designed for UCTP, called the hybrid harmony search algorithm (HHSA). In HHSA, the harmony search algorithm (HSA) which is a metaheuristic population-based method, has been hybridized by: 1) hill climbing, to improve local exploitation; and 2) a global-best concept of particle swarm optimization to improve convergence.

2.20 A MULTISWAP ALGORITHM

Mohammed Azmi Al-Betar et al. [20] proposed a MultiSwap Algorithm which contributes to major improvement in processing the room operations. This is achieved by combining the MultiSwap algorithm with the graph coloring heuristic method to satisfy the hard constraints and with the local search-based algorithms to minimize the violations of the soft constraints. The MultiSwap is incorporated with local search algorithm to minimize the violation of soft constraints.

2.21 PARALLEL HYBRID METAHEURISTIC ALGORITHM

Ehsan Alirezaei et al. [21] proposed a hybrid algorithm for solving polynomial with satisfying all problem constraints. This approach has two sequential phases with overall parallel implementation; it has a main algorithm that employed prescheduling structure and overall high performance.

2.22 ITERATED LOCAL SEARCH

J-F. Cordeau et al. [22] proposed a method which uses Iterated local search. Local search methods build a trajectory in configuration space, which leads from an initial solution to a local optimum, where local search stops (no improving neighbors are available). If local optima deliver sub-optimal solutions, local search needs to be modified to continue the search beyond local optimality.

A simple modification consists of iterating calls to the local search routine, each time starting from a different initial configuration. This is called repeated local search, and implies that the knowledge obtained during the previous local search phases is not used. Learning implies that the previous history, for example, the memory about the previously found local minima is mined to produce better and better starting points for local search. Iterated Local Search is based on building a sequence of locally optimal solutions by:

perturbing the current local minimum;

Applying local search after starting from the modified solution.

The perturbation strength has to be sufficient to lead the trajectory to a different attraction basin leading to a different local optimum.

CASE BASED REASONING ALGORITHM

Legierski et al. [23] proposed a system that selects a heuristic, from a collection of solutions, based on similarity of the problem, its data set, and objective functions. This approach works under the assumption that similar problems are solved most effectively by similar heuristic approaches. Case-based reasoning is a problem-solving paradigm that in many respects is fundamentally different from other major AI approaches.

Instead of relying solely on general knowledge of a problem domain, or making associations along generalized relationships between problem descriptors and conclusions, CBR is able to utilize the specific knowledge of previously experienced, concrete problem situations (cases). A new problem is solved by finding a similar past case, and reusing it in the new problem situation. A second important difference is that CBR also is an approach to incremental, sustained learning, since a new experience is retained each time a problem has been solved, making it immediately available for future problems.

2.24 ARTIFICIAL IMMUNE SYSTEM

M. R. Malim et al. [24] presented a method which uses three algorithms namely clonal selection, immune network and negative selection.

Clonal selection algorithm uses three operators selection, cloning, and mutation. A timetable is randomly selected to clone. Number of clones will be equal to half of the population. Almost all the clone will undergo mutation to produce new solution. Out of the new solutions, high affinity timetable will be used to replace old low affinity timetable. The process of cloning, mutation and selection will be repeated until the criteria are met.

Immune Network Algorithm uses two operators namely cloning and mutation. All timetables are selected to produce clone. Each timetable will produce one clone. All clone will undergo mutation to produce feasible solution. Timetable with high stimulation will be selected to produce new solution in the next generation. The process of cloning and mutation will be repeated until the criteria are met.

Negative Selection Algorithm uses operators namely negative deletion (censoring), cloning and mutation. In this, timetables in current population are determined by fitness function. If the fitness of the timetable is greater than or equal to the average fitness, it will be deleted from the current population. The remaining timetables will undergo cloning and mutation. Again, mutated timetables will undergo fitness function. If the fitness of the timetable is less than or equal to the average fitness, it will be added to the new population for the next generation.

2.25 HYBRID PSO WITH FLEXIBLE PREFERENCES

Der-Fang Shiau et al. [25] proposed a method which focuses on the novel meta-heuristic algorithm that is based on the principles of particle swarm optimization (PSO). The algorithm includes some features: designing an 'absolute position value' representation for the particle, allowing instructors that they are willing to lecture based on flexible preferences such as their preferred days and time periods, the maximum number of teaching-free time periods and the lecturing format (consecutive time periods or separated into different time periods) and employing a repair process for all infeasible timetables.

Furthermore, in the original PSO algorithm, particles search solutions in a continuous solution space. Since the solution space of the course scheduling problem is discrete, a local search mechanism is incorporated into the proposed PSO in order to explore a better solution improvement.

2.26 BEES ALGORITHM

Nguyen Tan Tran Minh Khang et al. [26] presented the Bees Algorithm to solve a highly constrained real-world university timetabling problem. It is inspired by the foraging behaviour of honeybees and performs a kind of neighbourhood search combined with random search to enable it to locate the global optimum. A number of parameters controls the algorithm.

2.27 DECOMPOSED METAHEURISTIC APPROACH

Patrick De Causmaecker et al. [27] presented a approach in which the first stage reduces the number of subjects through the introduction of new structures that are called as 'pillars'. The next stage involves a metaheuristic search that attempts to solve the constraints one by one, instead of trying to find a solution for all the constraints at once.

5.CONCLUSION

The timetabling problem consists of scheduling a sequence of lectures between teachers and students in a prefixed period of time (typically a week), satisfying a set of constraints of various types. A large number of variants of the timetabling problem have been proposed in the literature, which differ from each other based on the type of institution involved (university or school) and the type of constraints. This problem that has been traditionally considered in the operational research field, has recently been tackled with techniques belonging to Artificial Intelligence (e.g., Genetic Algorithms, Tabu Search, and Constraint Satisfaction). In this paper, we have surveyed different types of algorithms used for tackling Course Timetabling Problem. A comparative analysis has been made with the performance metrices which are tabulated with various parameters along with merits, demerits, issues to be addressed and so on. To a great extent, the existing timetabling algorithm does not consider fitness value, Instance type, Execution time and the maximum number of free timeslots allocated. Therefore, there is a need to implement a Course Timetabling algorithm that can enhance the optimality and fitness to get significant performance enhancements.

.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.