Automated generation of constructive ordering heuristics for educational timetabling

Annals of Operations Research - Construction heuristics play an important role in solving combinatorial optimization problems. These heuristics are usually used to create an initial solution to the...     

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 mixed-integer mathematical modeling approach to exam timetabling

This paper explores mathematical programming models for an exam timetabling problem related to Kuwait University (KU). In particular, we consider two subproblems: (a) the ExamTimetabling Problem (ETP), which is concerned with assigning exams to designated exam-periods and classrooms, and (b) the Proctor Assignment Problem (PAP), which deals with the assignment of proctors to exams. While this exam timetabling problem is ubiquitous in many academic institutions worldwide, idiosyncrasies of the problem related to gender-based policies and having multiple exam centers at KU require novel models. A mixed-integer exam timetabling programming model (ETM) is developed for ETP, which takes into account restrictions related to exam-period conflicts, facility and human resources, and commuting and traffic considerations. Assuming that exam-periods are specified for all exams as determined by ETM, another mixed-integer programming model is formulated for PAP, denoted by PAM, which incorporates the proctors’ preferences for specific days and exam-periods. Computational results are reported and analyzed for solving ETM and PAM directly using the CPLEX Optimization Software (version 9.0), and for implementing a specialized sequential LP-based heuristic for solving PAM. The results obtained significantly improve upon those derived via the existing manual approach implemented at KU, in terms of eliminating conflicts as well as from the overall efficiency and equity points of view.     

A constructive approach to Noether's problem

A general method is developed to attack Noether's Problem constructively by trying to find minimal bases consisting of rational invariants which are quotients of polynomials of small degrees. This approach turns out to be successful for many small groups and for most of the classical groups with their natural representations. The applications include affirmative answers to Noether's Problem for the conformal symplectic groups CSp _2n (q), for the simple subgroups Ω _n (q) of the orthogonal groups forn andq odd, for some other subgroups of orthogonal groups and for the special unitary groups SU _n (q ²). The author was supported by the Graduate College “Modelling and Scientific Computing in Mathematics and Science” during this work     

A constructive approach to nodal splines

In the context of local spline interpolation methods, nodal splines have been introduced as possible fundamental functions by de Villiers and Rohwer in 1988. The corresponding local spline interpolation operator possesses the desirable property of reproducing a large class of polynomials. However, it was remarked that their definition is rather intricate so that it seems desirable to reveal the actual origin of these splines. The real source can be found in the Martensenoperator which can be obtained by two-point Hermite spline interpolation problem posed and proved by Martensen [Darstellung und Entwicklung des Restgliedes der Gregoryschen Quadraturformel mit Hilfe von Spline-Funktionen, Numer. Math. 21(1973)70–80]. On the one hand, we will show how to represent the Hermite Martensen spline recursively and, on the other hand, explicitly in terms of the B-spline by using the famous Marsden identity. Having introduced the Martensenoperator, we will show that the nodal spline interpolation operator can be obtained by a special discretization of the occurring derivatives. We will consider symmetric nodal splines of odd degree that can be obtained by our methods in a natural way.     

A new model for automated examination timetabling

Automated examination timetabling has been addressed by a wide variety of methodologies and techniques over the last ten years or so. Many of the methods in this broad range of approaches have been evaluated on a collection of benchmark instances provided at the University of Toronto in 1996. Whilst the existence of these datasets has provided an invaluable resource for research into examination timetabling, the instances have significant limitations in terms of their relevance to real-world examination timetabling in modern universities. This paper presents a detailed model which draws upon experiences of implementing examination timetabling systems in universities in Europe, Australasia and America.     

A column generation approach to train timetabling on a corridor

We propose heuristic and exact algorithms for the (periodic and non-periodic) train timetabling problem on a corridor that are based on the solution of the LP relaxation of an ILP formulation in which each variable corresponds to a full timetable for a train. This is in contrast with previous approaches to the same problem, which were based on ILP formulations in which each variable is associated with a departure and/or arrival of a train at a specific station in a specific time instant, whose LP relaxation is too expensive to be solved exactly. Experimental results on real-world instances of the problem show that the proposed approach is capable of producing heuristic solutions of better quality than those obtained by these previous approaches, and of solving some small-size instances to proven optimality.      

A constructive approach to steady nonlinear kinetic equations

We study steady boundary value problems of nonlinear kinetic theory. Using a continuation argument based on the variation of the Knudsen number we derive a method for the construction of steady solutions of discrete velocity models in a slab. This method is readily transformed into a numerical code. In a preliminary numerical test case the numerical scheme turns out to yield solutions even for Knudsen numbers small enough to calculate with high precision the asymptotic flow field adjacent to a kinetic boundary layer. Thus, we are able to numerically simulate in a simplified situation the transition from a (mesoscopic) kinetic boundary layer to the (macroscopic) far field.     

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.     

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.     

Multi-item single source ordering problem with transportation cost: A Lagrangian decomposition approach

As a part of supply chain management literature and practice, it has been recognized that there can be significant gains in integrating inventory and transportation decisions. The problem we tackle here is a common one both in retail and production sectors where several items have to be ordered from a single supplier. We assume that there is a finite planning horizon to make the ordering decisions for the items, and in this finite horizon the retailer or the producer knows the demand of each item in each period. In addition to the inventory holding cost, an item-base fixed cost associated with each item included in the order, and a piecewise linear transportation cost are incurred. We suggest a Lagrangean decomposition based solution procedure for the problem and carry out numerical experiments to analyze the value of integrating inventory and transportation decisions under different scenarios.     

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.     

A constructive approach to the problem of program correctness

As an alternative to methods by which the correctness of given programs can be established a posteriori, this paper proposes to control the process of program generation such as to produce a priori correct programs. An example is treated to show the form that such a control might then take. This example comes from the field of parallel programming; the way in which it is treated is representative of the way in which a whole multiprogramming system has actually been constructed.     

A constructive approach to minimal projections in Banach spaces

Let X be a Banach space and Y a finite-dimensional subspace of X. Let P be a minimal projection of X onto Y. It is shown (Theorem 1.1) that under certain conditions there exist sequences of finite-dimensional “approximating subspaces” X_m and Y_m of X with corresponding minimal projections P_m: X_m → Y_m, such that lim_m→∞ P_m = P. Moreover, a certain related sequence of projections i_m○P_m○π_m: X → Y has cluster points in the strong operator topology, each of which is a minimal projection of X onto Y. When X = C[a, b] the result reduces to a theorem of [7.]. It is shown (Corollary 1.11) that the hypothesis of Theorem 1.1 holds in many important Banach spaces, including C[a, b], L^P[a, b] and l^P for 1 p < ∞, and c₀, the space of sequences converging to zero in the sup norm.     

A great deluge algorithm for a real-world examination timetabling problem

The examination timetabling problem involves assigning exams to a specific or limited number of timeslots and rooms with the aim of satisfying all hard constraints (without compromise) and satisfying the soft constraints as far as possible. Most of the techniques reported in the literature have been applied to simplified examination benchmark data sets. In this paper, we bridge the gap between research and practice by investigating a problem taken from the real world. This paper introduces a modified and extended great deluge algorithm (GDA) for the examination timetabling problem that uses a single, easy to understand parameter. We investigate different initial solutions, which are used as a starting point for the GDA, as well as altering the number of iterations. In addition, we carry out statistical analyses to compare the results when using these different parameters. The proposed methodology is able to produce good quality solutions when compared with the solution currently produced by the host organisation, generated in our previous work and from the original GDA.     

A constructive approach to the finite congruence lattice representation problem

A finite lattice is representable if it is isomorphic to the congruence lattice of a finite algebra. In this paper, we develop methods by which we can construct new representable lattices from known ones. The techniques we employ are sufficient to show that every finite lattice which contains no three element antichains is representable. We then show that if an order polynomially complete lattice is representable then so is every one of its diagonal subdirect powers. Received August 30, 1999; accepted in final form November 29, 1999.     

A stochastic local search algorithm with adaptive acceptance for high-school timetabling

Automating high school timetabling is a challenging task. This problem is a well known hard computational problem which has been of interest to practitioners as well as researchers. High schools need to timetable their regular activities once per year, or even more frequently. The exact solvers might fail to find a solution for a given instance of the problem. A selection hyper-heuristic can be defined as an easy-to-implement, easy-to-maintain and effective ‘heuristic to choose heuristics’ to solve such computationally hard problems. This paper describes the approach of the team hyper-heuristic search strategies and timetabling (HySST) to high school timetabling which competed in all three rounds of the third international timetabling competition. HySST generated the best new solutions for three given instances in Round 1 and gained the second place in Rounds 2 and 3. It achieved this by using a fairly standard stochastic search method but significantly enhanced by a selection hyper-heuristic with an adaptive acceptance mechanism.     

A two-phase multiple objective approach to university timetabling utilising optimisation and evolutionary solution methodologies

The timetabling problem is generally large, highly constrained and discrete in nature. This makes solution by exact optimisation methods difficult. Therefore, often a heuristic search is deemed acceptable providing a simple (non-optimal) solution. This paper discusses the timetabling problem for a university department, where a large-scale integer goal programming (IGP) formulation is implemented for its efficient optimal solution in two phases. The first phase allocates lectures to rooms and the second allocates start-times to lectures. Owing to the size and complicated nature of the model, an initial analysis procedure is employed to manipulate the data to produce a more manageable model, resulting in considerable reductions in problem size and increase of performance. Both phases are modelled as IGPs. Phase 1 is solved using a state-of-the-art IGP optimisation package. However, due to the scale of the model, phase 2 is solved to optimality using a genetic algorithm approach.