Universiti Malaysia Pahang examination timetabling problem: scheduling invigilators

This paper presents a real-world examination timetabling problem from Universiti Malaysia Pahang (UMP), Malaysia. The problem involves assigning invigilators to examination rooms. This problem has received less attention than the examination timetabling problem from the research community partly because no data sets are available in the literature. In modelling, and solving, this problem we assume that there is already an examination timetable in place (this was the subject of our previous work) and the task is to assign invigilators to that timetable. The contributions of this paper are to formally define the invigilator scheduling problem and to present a constructive algorithm that is able to produce good quality solutions that are superior to the solutions produced when using the university's current software. We also include additional constraints taking into account the comments made by the invigilators, which the current system fails to capture. The model we present, we believe, accurately reflects the real-world problem, capturing various aspects of the problem that have not been presented before in the scientific literature. Moreover, the proposed approach adheres to all hard constraints, which the university's current system fails to do.     

A tabu-based large neighbourhood search methodology for the capacitated examination timetabling problem

Neighbourhood search algorithms are often the most effective known approaches for solving partitioning problems. In this paper, we consider the capacitated examination timetabling problem as a partitioning problem and present an examination timetabling methodology that is based upon the large neighbourhood search algorithm that was originally developed by Ahuja and Orlin. It is based on searching a very large neighbourhood of solutions using graph theoretical algorithms implemented on a so-called improvement graph. In this paper, we present a tabu-based large neighbourhood search, in which the improvement moves are kept in a tabu list for a certain number of iterations. We have drawn upon Ahuja–Orlin's methodology incorporated with tabu lists and have developed an effective examination timetabling solution scheme which we evaluated on capacitated problem benchmark data sets from the literature. The capacitated problem includes the consideration of room capacities and, as such, represents an issue that is of particular importance in real-world situations. We compare our approach against other methodologies that have appeared in the literature over recent years. Our computational experiments indicate that the approach we describe produces the best known results on a number of these benchmark problems.     

RobinX: A three-field classification and unified data format for round-robin sports timetabling

Sports timetabling problems are combinatorial optimization problems which consist of creating a timetable that defines against whom, when, and where teams play games. In the literature, sports timetabling problems have been reported featuring a wide variety of constraints and objectives. This variety makes it challenging to identify the relevant set of papers for a given sports timetabling problem. Moreover, the lack of a generally accepted data format makes that problem instances and their solutions are rarely shared. Consequently, it is hard to assess algorithmic performance since solution methods are often tested on just one or two specific instances. To mitigate these issues, this paper presents RobinX, a three-field notation to describe a sports timetabling problem by means of the tournament format, the constraints in use, and the objective. We use this notation to classify sports timetabling problems presented in the operations research literature during the last five decades. Moreover, RobinX contains xml-based file templates to store problem instances and their solutions and presents an online platform that offers three useful tools. First, a query tool assists users to select the relevant set of papers for a given timetabling problem. Second, the online platform provides access to an xml data repository that contains real-life problem instances from different countries and sports. Finally, the website enables users to interact with a free and open-source C++-library to read and write xml files and to validate and evaluate encoded instances and solutions.     

A multiobjective framework for heavily constrained examination timetabling problems

University examination timetabling is a challenging set partitioning problem that comes in many variations, and real world applications usually carry multiple constraints and require the simultaneous optimization of several (often conflicting) objectives. This paper presents a multiobjective framework capable of solving heavily constrained timetabling problems. In this prototype study, we focus on the two objectives: minimizing timetable length while simultaneously optimizing the spread of examinations for individual students. Candidate solutions are presented to a multiobjective memetic algorithm as orderings of examinations, and a greedy algorithm is used to construct violation free timetables from permutation sequences of exams. The role of the multiobjective algorithm is to iteratively improve a population of orderings, with respect to the given objectives, using various mutation and reordering heuristics.     

The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution

This paper presents a real-world, capacitated examination timetabling problem from Universiti Malaysia Pahang (UMP), Malaysia. The problem has constraints which have not been modelled before, these being the distance between examination rooms and splitting exams across several rooms. These constraints provide additional challenges in defining a suitable model and in developing a constructive heuristic. One of the contributions of this paper is to formally define this real-world problem. A further contribution is the constructive heuristic that is able to produce good quality solutions for the problem, which are superior to the solutions that are produced using the university’s current software. Moreover, our method adheres to all hard constraints which the current systems fails to do.     

Timetabling for Greek high schools

The timetabling process and the resulting weekly schedules are important components for the daily operation of any school. This paper presents an efficient solution to the timetabling problem for the secondary educational system in Greece. Such a problem involves scheduling a large number of classes, teachers, courses, and classrooms to a number of time-periods. The development of the basic structure and the modelling of the problem as an integer mathematical program allows for the generation of constraints necessary for the satisfaction of all the school system rules and regulations. The integer programming approach and the commercial tools available for this class of problems facilitated the process of locating the optimal solution for the problem. The model is flexible and modular allowing for adaptations to satisfy the local characteristics of each school by changing the parameters of the model and adding or replacing constraints. A fully defined timetabling problem for a typical Greek high school is presented and optimally solved in order to demonstrate the effectiveness of the model in satisfying both the hard and the soft operational rules of the problem. Implementation of the new methodology for regular use for high schools is currently being attempted.     

University course timetabling using hybridized artificial bee colony with hill climbing optimizer

University course timetabling is concerned with assigning a set of courses to a set of rooms and timeslots according to a set of constraints. This problem has been tackled using metaheuristics techniques. Artificial bee colony (ABC) algorithm has been successfully used for tackling uncapaciated examination and course timetabling problems. In this paper, a novel hybrid ABC algorithm based on the integrated technique is proposed for tackling the university course timetabling problem. First of all, initial feasible solutions are generated using the combination of saturation degree (SD) and backtracking algorithm (BA). Secondly, a hill climbing optimizer is embedded within the employed bee operator to enhance the local exploitation ability of the original ABC algorithm while tackling the problem. Hill climbing iteratively navigates the search space of each population member in order to reach a local optima. The proposed hybrid ABC technique is evaluated using the dataset established by Socha including five small, five medium and one large problem instances. Empirical results on these problem instances validate the effectiveness and efficiency of the proposed algorithm. Our work also shows that a well-designed hybrid technique is a competitive alternative for addressing the university course timetabling problem.     

A column generation approach for solving the patient admission scheduling problem

This paper addresses the Patient Admission Scheduling (PAS) problem. The PAS problem entails assigning elective patients to beds, while satisfying a number of hard constraints and as many soft constraints as is possible, and arises at all planning levels for hospital management. There exist a few, different variants of this problem. In this paper we consider one such variant and propose an optimization-based heuristic building on branch-and-bound, column generation, and dynamic constraint aggregation to solve it. We achieve tighter lower bounds than previously reported in the literature and, in addition, we are able to produce new best known solutions for five out of twelve instances from a publicly available repository.     

Timetabling University Examinations

The problem of timetabling examinations is one which is faced by most educational institutions, with the problem becoming particularly acute in institutions of higher education. The situation may be formulated generally as a 0-1 integer pregramming problem but, in common with a number of other timetabling problems which have been reported, a heuristic approach is more practical and produces an acceptable solution. The procedure described takes account of the obvious constraints imposed by examination-room availability and capacity, and the need to avoid clashes between common examination papers. In addition, the examinations are scheduled such that the students are faced with a minimum number of occasions when two papers have to be taken in the same day and, for ease of marking, the larger courses are examined early. A computer program to implement the heuristic was developed and was found to produce a better timetable than the previous manual procedure as well as a considerable saving in clerical effort.     

Hybrid variable neighbourhood approaches to university exam timetabling

In this paper, we investigate variable neighbourhood search (VNS) approaches for the university examination timetabling problem. In addition to a basic VNS method, we introduce variants of the technique with different initialisation methods including a biased VNS and its hybridisation with a Genetic Algorithm. A number of different neighbourhood structures are analysed. It is demonstrated that the proposed technique is able to produce high quality solutions across a wide range of benchmark problem instances. In particular, we demonstrate that the Genetic Algorithm, which intelligently selects appropriate neighbourhoods to use within the biased VNS, produces the best known results in the literature, in terms of solution quality, on some of the benchmark instances. However, it requires relatively large amount of computational time. Possible extensions to this overall approach are also discussed.     

A genetic algorithm approach to school timetabling

An adaptive algorithm based on computational intelligence techniques is designed, developed and applied to the timetabling problem of educational organizations. The proposed genetic algorithm is used in order to create feasible and efficient timetables for high schools in Greece. In order to demonstrate the efficiency of the proposed genetic algorithm, exhaustive experiments with real-world input data coming from many different high schools in the city of Patras have been conducted. As well as that, in order to demonstrate the superior performance of the proposed algorithm, we compare its experimental results with the results obtained by another effective algorithm applied to the same problem. Simulation results showed that the proposed algorithm outperforms other existing attempts. However, the most significant contribution of the paper is that the proposed algorithm allows for criteria adaptation, thus producing different timetables for different constraints priorities. So, the proposed approach, due to its inherent adaptive capabilities, can be used, each time satisfying different specific constraints, in order to lead to different timetables, thus meeting the different needs that each school may have.     

A hybrid metaheuristic approach to the university course timetabling problem

This paper describes the development of a novel metaheuristic that combines an electromagnetic-like mechanism (EM) and the great deluge algorithm (GD) for the University course timetabling problem. This well-known timetabling problem assigns lectures to specific numbers of timeslots and rooms maximizing the overall quality of the timetable while taking various constraints into account. EM is a population-based stochastic global optimization algorithm that is based on the theory of physics, simulating attraction and repulsion of sample points in moving toward optimality. GD is a local search procedure that allows worse solutions to be accepted based on some given upper boundary or ‘level’. In this paper, the dynamic force calculated from the attraction-repulsion mechanism is used as a decreasing rate to update the ‘level’ within the search process. The proposed method has been applied to a range of benchmark university course timetabling test problems from the literature. Moreover, the viability of the method has been tested by comparing its results with other reported results from the literature, demonstrating that the method is able to produce improved solutions to those currently published. We believe this is due to the combination of both approaches and the ability of the resultant algorithm to converge all solutions at every search process.     

An XML format for benchmarks in High School Timetabling

The High School Timetabling Problem is amongst the most widely used timetabling problems. This problem has varying structures in different high schools even within the same country or educational system. Due to lack of standard benchmarks and data formats this problem has been studied less than other timetabling problems in the literature. In this paper we describe the High School Timetabling Problem in several countries in order to find a common set of constraints and objectives. Our main goal is to provide exchangeable benchmarks for this problem. To achieve this we propose a standard data format suitable for different countries and educational systems, defined by an XML schema. The schema and datasets are available online.     

A decomposed metaheuristic approach for a real-world university timetabling problem

In this paper we present a decomposed metaheuristic approach to solve a real-world university course timetabling problem. Essential in this problem are the overlapping time slots and the irregular weekly timetables. A first stage in the approach reduces the number of subjects through the introduction of new structures that we call ‘pillars’. The next stages involve 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. Test results for a real-world instance are presented.     

Linear combinations of heuristics for examination timetabling

Although they are simple techniques from the early days of timetabling research, graph colouring heuristics are still attracting significant research interest in the timetabling research community. These heuristics involve simple ordering strategies to first select and colour those vertices that are most likely to cause trouble if deferred until later. Most of this work used a single heuristic to measure the difficulty of a vertex. Relatively less attention has been paid to select an appropriate colour for the selected vertex. Some recent work has demonstrated the superiority of combining a number of different heuristics for vertex and colour selection. In this paper, we explore this direction and introduce a new strategy of using linear combinations of heuristics for weighted graphs which model the timetabling problems under consideration. The weights of the heuristic combinations define specific roles that each simple heuristic contributes to the process of ordering vertices. We include specific explanations for the design of our strategy and present the experimental results on a set of benchmark real world examination timetabling problem instances. New best results for several instances have been obtained using this method when compared with other constructive methods applied to this benchmark dataset.     

Memetic algorithms for solving job-shop scheduling problems

The job-shop scheduling problem is well known for its complexity as an NP-hard problem. We have considered JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints. In this paper, we developed a memetic algorithm (MA) for solving JSSPs. Three priority rules were designed, namely partial re-ordering, gap reduction and restricted swapping, and used as local search techniques in our MA. We have solved 40 benchmark problems and compared the results obtained with a number of established algorithms in the literature. The experimental results show that MA, as compared to GA, not only improves the quality of solutions but also reduces the overall computational time.     

Hores: A timetabling system for Spanish secondary schools

Summary Constructing a timetable is a difficult problem faced by every school every year. A feasible solution has to satisfy many different requirements and constraints. A good solution has to provide compact timetables for classes and teachers. In order to help the schools, we have developed HORES, a robust and flexible timetabling system suited to the needs of Spanish secondary schools. HORES runs on a PC and is fast and user-friendly. It may handle virtually every condition required by the schools and obtains good quality solutions in very short computing times. It also allows the user to modify interactively the solutions. HORES is now being used by schools with satisfactory results.     

A survey of school timetabling research

Although there has been a fair amount of research in the area of school timetabling, this domain has not developed as well as other fields of educational timetabling such as university course and examination timetabling. This can possibly be attributed to the fact that the studies in this domain have generally been conducted in isolation of each other and have addressed different school timetabling problems. Furthermore, there have been no comparative studies on the success of different methodologies on a variety of school timetabling problems. As a way forward this paper provides an overview of the research conducted in this domain, details of problem sets which are publicly available and proposes areas for further research in school timetabling.     

<Emphasis Type="Italic">α</Emphasis>-Conservative approximation for probabilistically constrained convex programs

In this paper, we address an approximate solution of a probabilistically constrained convex program (PCCP), where a convex objective function is minimized over solutions satisfying, with a given probability, convex constraints that are parameterized by random variables. In order to approach to a solution, we set forth a conservative approximation problem by introducing a parameter α which indicates an approximate accuracy, and formulate it as a D.C. optimization problem.     

Evolving hyper-heuristics for the uncapacitated examination timetabling problem

This paper reports on the use of an evolutionary algorithm (EA) to search a space of heuristic combinations for the uncapacitated examination timetabling problem. The representation used by an EA has an effect on the difficulty of the search and hence the overall success of the system. The paper examines three different representations of heuristic combinations for this problem and compares their performance on a set of benchmark problems for the uncapacitated examination timetabling problem. The study has revealed that certain representations do result in a better performance and generalization of the hyper-heuristic. An EA-based hyper-heuristic combining the use of all three representations (CEA) was implemented and found to generalize better than the EA using each of the representations separately.