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.     

Curriculum based course timetabling: new solutions to Udine benchmark instances

We present an integer programming approach to the university course timetabling problem, in which weekly lectures have to be scheduled and assigned to rooms. Students’ curricula impose restrictions as to which courses may not be scheduled in parallel. Besides some hard constraints (no two courses in the same room at the same time, etc.), there are several soft constraints in practice which give a convenient structure to timetables; these should be met as well as possible.     

Flexible <Emphasis Type="Italic">versus</Emphasis> fixed timetabling: a case study

This case study presents the timetabling problem of the Flight Training Department at Embry-Riddle Aeronautical University. The problem consists of scheduling the flight resources to students to various time blocks. This problem represents a well-studied field in operations research, mainly adopting variations of mathematical programming models. This paper initially presents the efforts towards developing a fixed timetable using optimization models for the case under study. It is, however, demonstrated that implementation of optimum solutions obtained using this approach cannot be sustained, mainly because of the dynamic nature of the governing parameters. A flexible and dynamic timetable utilizing the university computer network, allowing the instructors and students to make their own decentralized flexible timetables, is proposed. A simulation study is initiated to compare the performance measures under both timetables. The analysis shows that implementation of a flexible system generates higher utilization of flight resources as well as improving key performance measures.     

A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations

This paper considers the class scheduling and timetabling problem faced at Kuwait University (KU). The principal focus is to design efficient class offering patterns while taking into consideration newly imposed gender policies. We formulate a mathematical programming model that assigns offered classes to time-slots and addresses gender issues by defining appropriate surrogate constraints along with objective penalty terms. The model aims to enhance existing manual scheduling and timetabling approaches that are often accompanied with arduous combinatorial tasks such as resolving class conflicts, dealing with parking and traffic congestion, and ensuring an efficient utilization of facility and human resources. This modeling approach emphasizes the generation of flexible class timetables for students, and the efficient utilization of available facility resources. Computational results based on a number of case studies related to Kuwait University reveal that this approach yields improved schedules in terms of offering patterns and class conflicts.     

Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems

High school timetabling problems consist in building periodic timetables for class-teacher meetings considering compulsory and non-compulsory requirements. This family of problems has been widely studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the efficient search of optimal or near-optimal solutions is still a challenge for many problems of practical size. In this paper, we investigate mixed-integer programming formulations and a parallel metaheuristic based algorithm for solving high school timetabling problems with compactness and balancing requirements. We propose two pattern-based formulations and a solution algorithm that simultaneously exploits column generation and a team of metaheuristics to build and improve solutions. Extensive computational experiments conducted with real-world instances demonstrate that our formulations are competitive with the best existing high school timetabling formulations, while our parallel algorithm presents superior performance to alternative methods available in the literature.     

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.     

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.     

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.     

An improved solution methodology for the arsenal exchange model (AEM)

We develop an iterative approach for solving a linear programming problem with prioritized goals. We tailor our approach to preemptive goal programming problems and take advantage of the fact that at optimality, most constraints are not binding. To overcome the problems posed by redundant constraints, our procedure ensures redundant constraints are not present in the problems we solve. We apply our approach to the arsenal exchange model (AEM). AEM allocates weapons to targets using linear programs (LPs) formulated by the model. Our methodology solves a subproblem using a specific subset of the constraints generated by AEM. Violated constraints are added to the original subproblem and redundant constraints are not included in any of the subproblems. Our methodology was used to solve five test cases. In four of the five test cases, our methodology produced an optimal integer solution. In all five test cases, solution quality was maintained or improved.     

An improved multi-staged algorithmic process for the solution of the examination timetabling problem

The efficient creation of examination timetables is a recurring and important problem for universities worldwide. Good timetables typically are characterized by balanced distances between consecutive exams for all students. In this contribution an approach for the examination timetabling problem as defined in the second International Timetabling Competition () is presented. The solution approach is managed on the top level by GRASP (Greedy Randomized Adaptive Search Procedure) and it involves several optimization algorithms, heuristics and metaheuristics. A construction phase is executed first producing a relatively high quality feasible solution and an improvement phase follows that further ameliorates the produced timetable. Each phase consists of stages that are consumed in a circular fashion. The procedure produces feasible solutions for each dataset provided under the runtime limit imposed by the rules of the ITC07 competition. Results are presented and analyzed.     

Real-time vehicle rerouting problems with time windows

This paper introduces and studies real-time vehicle rerouting problems with time windows, applicable to delivery and/or pickup services that undergo service disruptions due to vehicle breakdowns. In such problems, one or more vehicles need to be rerouted, in real-time, to perform uninitiated services, with the objective to minimize a weighted sum of operating, service cancellation and route disruption costs. A Lagrangian relaxation based-heuristic is developed, which includes an insertion based-algorithm to obtain a feasible solution for the primal problem. A dynamic programming based algorithm solves heuristically the shortest path problems with resource constraints that result from the Lagrangian relaxation. Computational experiments show that the developed Lagrangian heuristic performs very well.     

Constructing Good Solutions for the Spanish School Timetabling Problem

In the school timetabling problem a set of lessons (combinations of classes, teachers, subjects and rooms) has to be scheduled within the school week. Considering classes, teachers and rooms as resources for the lessons, the problem may be viewed as the scheduling of a project subject to resource constraints. We have developed an algorithm with three phases. In Phase I an initial solution is built by using the scheme of parallel heuristic algorithm with priority rules, but imbedding at each period the construction of a maximum cardinality independent set on a resource graph. In Phase II a tabu search procedure starts from the solution of Phase I and obtains a feasible solution to the problem. The solution obtained is improved in Phase III. Several procedures based on the calculation of negative cost cycles and shortest paths in a solution graph are used to get more compact timetables.The algorithms have been imbedded in a package designed to solve the problem for Spanish secondary schools. The computational results show its performance on a set of real problems. Nevertheless, it can be applied to more general problems and results on a set of large random problems are also provided.     

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 graph-based hyper-heuristic for educational timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.     

A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

A general MPCC model and its solution algorithm for continuous network design problem

This paper formulates the continuous network design problem as a mathematical program with complementarity constraints (MPCC), with the upper level a nonlinear programming problem and the lower level a nonlinear complementarity problem. Unlike in most previous studies, the proposed framework is more general, in which both symmetric and asymmetric user equilibria can be captured. By applying the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level and smooth nonlinear programming problem. In order to solve the problem, a relaxation scheme is applied by progressively restricting the complementarity condition, which has been proven to be a rigorous approach under certain conditions. The model and solution algorithm are tested for well-known network design problems and promising results are shown.     

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.     

Nonnormal deterministic equivalents and a transformation in stochastic mathematical programming

This paper considers random variables of the continuous type in a stochastic programming problem and presents (1) a general approach to the development of deterministic equivalents of constraints to be satisfied within certain probability limits, and (2) a deterministic transformation of a stochastic programming problem with random variables in the objective function. Deterministic equivalents are developed for constraints containing uniform random variables, but the approach used can be applied to other types of continuous random variables, as well. When the random variables appear in the objective function, a deterministic transformation of the stochastic programming problem is obtained to yield a closed-form solution without resort to a Monte Carlo computer simulation. Extension of this approach to stochastic problems with discrete random variables and integer decision variables is discussed briefly. A numerical example is presented.     

A globally most violated cutting plane method for complex minimax problems with application to digital filter design

In [4,6], the authors have presented a numerical method for the solution of complex minimax problems, which implicitly solves discretized versions of the equivalent semi-infinite programming problem on increasingly finer grids. While this method only requires the most violated constraint at the current iterate on a finite subset of the infinitely many constraints of the problem, we consider here a related and more direct approach (applicable to general convex semi-infinite programming problems) which makes use of the globally most violated constraint. Numerical examples with up to 500 unknowns, which partially originate from digital filter design problems, are discussed.