New integer linear programming approaches for course timetabling

The most complete form of academic timetabling problem is the population and course timetabling problem. In this problem, there may be multiple classes of each subject, and the decision on which students are to constitute each class is made in concert with the decision on the timetable for each class. In order to solve this problem, it is normally simplified or decomposed in some fashion. One simplification commonly used in practice is known as blocking: it is assumed that the classes can be partitioned into sets of classes (or blocks) that will be timetabled in parallel. This restricts clashing to occur only between classes in the same block, and essentially removes the timetabling aspect of the problem, which can be carried out once the blocks are constituted and the classes populated. The problem of constituting the blocks and populating the classes, known as the course blocking and population problem, is nevertheless a challenging problem, and provides the focus of this paper. We demonstrate, using data provided by a local high school, that integer linear programming approaches can solve the problem in a matter of seconds. Key features include remodelling to remove symmetry caused by students with identical subject selection, and the observation that in practice, only integrality of the block composition variables needs to be enforced; the class population aspects of the model have strong integrality properties.     

An ILP based heuristic for a generalization of the post-enrollment course timetabling problem

We consider a new timetabling problem arising from a real-world application in a private university in Buenos Aires, Argentina. In this paper we describe the problem in detail, which generalizes the Post-Enrollment Course Timetabling Problem (PECTP), propose an ILP model and a heuristic approach based on this formulation. This algorithm has been implemented and tested on instances obtained from real data, showing that the approach is feasible in practice and produces good quality solutions.     

Integer programming methods for large-scale practical classroom assignment problems

In this paper we present an integer programming method for solving the Classroom Assignment Problem in University Course Timetabling. We introduce a novel formulation of the problem which generalises existing models and maintains tractability even for large instances. The model is validated through computational results based on our experiences at the University of Auckland, and on instances from the 2007 International Timetabling Competition. We also expand upon existing results into the computational difficulty of room assignment problems.     

A Two-Stage Decomposition of High School Timetabling applied to cases in Denmark

Integer Programming (IP) has been used to model educational timetabling problems since the very early days of Operations Research. It is well recognized that these IP models in general are hard to solve, and this area of research is dominated by heuristic solution approaches. In this paper a Two-Stage Decomposition of an IP model for a practical case of high school timetabling is shown. This particular timetabling problem consists of assigning lectures to both a timeslot and a classroom, which is modeled using a very large amount of binary variables. The decomposition splits this model into two separate problems (Stage I and Stage II) with far less variables. These two separate problems are solved in sequence, such that the solution for the Stage I model is given as input to the Stage II model, implying that irreversible decisions are made in Stage I. However, the objective of the Stage II model is partly incorporated in the Stage I model by exploiting that Stage II can be seen as a minimum weight maximum matching problem in a bipartite graph. This theoretically strengthens the decomposition in terms of global optimality. The approach relies on Hall's theorem for the existence of matchings in bipartite graphs, which in its basic form yields an exponential amount of constraints in the Stage I model. However, it is shown that only a small subset of these constraints is needed, making the decomposition tractable in practice for IP solvers. To evaluate the decomposition, 100 real-life problem instances from the database of the high school ERP system Lectio are used. Computational results show that the decomposition performs significantly better than solving the original IP, in terms of both found solutions and bounds.     

A hybrid particle swarm optimization based algorithm for high school timetabling problems

In this contribution a hybrid particle swarm optimization (PSO) based algorithm is applied to high school timetabling problems. The proposed PSO based algorithm is used for creating feasible and efficient high school timetables. In order to demonstrate the efficiency of the proposed PSO based algorithm, experiments with real-world input data coming from many different Greek high schools have been conducted. Computational results show that the proposed hybrid PSO based algorithm performs better than existing approaches applied to the same school timetabling input instances using the same evaluation criteria.     

Mixed integer programming for minimizing the period of a cyclic railway timetable for a single track with two train types

In this paper we extend the work of Bergmann (1975) to investigate the capacity of a single track, unidirectional rail line that adheres to a cyclic timetable. A set of intermediate stations lies between an origin and destination with one siding at each station. Two types of trains—express and local—are dispatched from the origin in alternating fashion. The local stops at every intermediate station and the express stops at no intermediate stations. A mixed integer linear program is developed in order to minimize the length of the dispatching cycle and minimize the total stopping (dwell) time of the local train at all stations combined. Constraints include a minimum dwell time for the local train at each station, a maximum total dwell time for the local train, and headway considerations on the main line and in stations. Hundreds of randomly generated problem instances with up to 70 stations are considered and solved to optimality in a reasonable amount of time using IBM ILOG CPLEX.     

Iterated local search using an add and delete hyper-heuristic for university course timetabling

Hyper-heuristics are (meta-)heuristics that operate at a higher level to choose or generate a set of low-level (meta-)heuristics in an attempt of solve difficult optimization problems. Iterated local search (ILS) is a well-known approach for discrete optimization, combining perturbation and hill-climbing within an iterative framework. In this study, we introduce an ILS approach, strengthened by a hyper-heuristic which generates heuristics based on a fixed number of add and delete operations. The performance of the proposed hyper-heuristic is tested across two different problem domains using real world benchmark of course timetabling instances from the second International Timetabling Competition Tracks 2 and 3. The results show that mixing add and delete operations within an ILS framework yields an effective hyper-heuristic approach.     

Case-based heuristic selection for timetabling problems

This paper presents a case-based heuristic selection approach for automated university course and exam timetabling. The method described in this paper is motivated by the goal of developing timetabling systems that are fundamentally more general than the current state of the art. Heuristics that worked well in previous similar situations are memorized in a case base and are retrieved for solving the problem in hand. Knowledge discovery techniques are employed in two distinct scenarios. Firstly, we model the problem and the problem solving situations along with specific heuristics for those problems. Secondly, we refine the case base and discard cases which prove to be non-useful in solving new problems. Experimental results are presented and analyzed. It is shown that case based reasoning can act effectively as an intelligent approach to learn which heuristics work well for particular timetabling situations. We conclude by outlining and discussing potential research issues in this critical area of knowledge discovery for different difficult timetabling problems.     

Applying evolutionary computation to the school timetabling problem: The Greek case

In this contribution, an adaptive algorithm based on evolutionary computation techniques is designed, developed and applied to the timetabling problem of educational organizations. Specifically, the proposed algorithm has been used in order to create feasible and efficient timetables for high schools in Greece. The algorithm has been tested exhaustively with real-world input data coming from many different high schools and has been compared with several other effective techniques in order to demonstrate its efficiency and superior performance. Simulation results showed that the algorithm is able to construct a feasible and very efficient timetable more quickly and easily compared to other techniques, thus preventing disagreements and arguments among teachers and assisting each school to operate with its full resources from the beginning of the academic year. Except from that, due to its inherent adaptive behavior it can be used each time satisfying different specific constraints, in order to lead to timetables, thus meeting the different needs that each school may have.     

Developing software for generating pouring schedules for steel foundries

The authors have been involved in an industry-wide project whose goal is to improve the production systems of steel foundries. As a part of this effort, we have studied the process by which the foundries develop their daily pouring schedule. Typically, the foundries are unable to consider the impact of their pouring schedule on downstream operations because developing a feasible schedule is a labor-intensive task involving numerous constraints. To address this, the authors are working with Harrison Steel to develop software that can both automate the current scheduling process and improve it by estimating the impact of the pouring schedule on downstream work-in-process (WIP) inventory levels. An integer programming model is described that minimizes a comprehensive cost function that includes the costs of pattern tooling set-up, late delivery, WIP inventory, and under-utilization of assets. The software implements a heuristic that finds multiple solutions to this integer program, each of which corresponds to a feasible schedule. Computational tests reveal that the software is capable of handling realistically sized scheduling problems in a reasonable amount of time. Upon its completion, this system could be extended for implementation at many other steel foundries.     

Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm

In this contribution we present the application of a hybrid cat swarm optimization (CSO) based algorithm for solving the school timetabling problem. This easy to use, efficient and fast algorithm is a hybrid variation of the classic CSO algorithm. Its efficiency and performance is demonstrated by conducting experiments with real-world input data. This data, collected from various high schools in Greece, has also been used as test instances by many other researchers in their publications. Results reveal that this hybrid CSO based algorithm, applied to the same school timetabling test instances using the same evaluation criteria, exhibits better performance in less computational time compared to the majority of other existing approaches, such as Genetic Algorithms (GAs), Evolutionary Algorithms (EAs), Simulated Annealing (SA), Particle Swarm Optimization (PSO) and Artificial Fish Swarm (AFS). The algorithm's main process constitutes a variation of the classic CSO algorithm, properly altered so as to be applied for solving the school timetabling problem. This process contains the main algorithmic differences of the proposed approach compared to other algorithms presented in the respective literature.     

A practical three‐phase ILP approach for solving the examination timetabling problem

A practical mathematical programming based approach is introduced for solving the examination timetabling problem at the German Jordanian University (GJU), whereby the complex process of acquiring a feasible examination timetable is simplified by subdividing it into three smaller sub‐problems (phases). Accordingly, the exams are initially allocated to time slots in phase one, the time slots are then allotted to days in phase two, and finally in phase three the exams are assigned to rooms based on the number of students taking each exam and capacities of the rooms. The solution for each phase is acquired based on an integer linear programming (ILP) formulation, while satisfying a set of hard constraints that ensure comfortable exam timetables for all students and meet the desired requirements set by GJU administrative staff. Furthermore, the solver can be controlled and launched from a student information system named MyGJU Admin, which enabled registrars at the university to easily, quickly, and accurately generate final exam timetables in several standard formats. Moreover, the approach was validated based on recent GJU registration information as well as real‐world benchmark data.     

Creating schedules and computing operating costs for LTL load plans

This paper presents a computational approach for creating an operational schedule for the tactical load plan used by a less-than-truckload (LTL) motor carrier. A load plan determines how freight is routed through an LTL carrier's linehaul terminal network by specifying a sequence of transfer terminals for all freight shipments, but does not provide a timed schedule of trailer, tractor, and driver dispatches required to operate the plan. Developing a detailed operational schedule allows one to more accurately estimate the likely cost of a given load plan, along with other important performance metrics. Given a load plan, the scheduling approach we develop creates loaded truck dispatches between terminals with specified time windows, and then creates cyclic driver schedules to cover all dispatches. A computational study using data from a large U.S. LTL carrier demonstrates that our technology produces schedules that accurately model operational costs, typically within 2% of actual reported costs.     

A multi-objective evolutionary algorithm for examination timetabling

This paper considers the scheduling of exams for a set of university courses. The solution to this exam timetabling problem involves the optimization of complete timetables such that there are as few occurrences of students having to take exams in consecutive periods as possible but at the same time minimizing the timetable length and satisfying hard constraints such as seating capacity and no overlapping exams. To solve such a multi-objective combinatorial optimization problem, this paper presents a multi-objective evolutionary algorithm that uses a variable-length chromosome representation and incorporates a micro-genetic algorithm and a hill-climber for local exploitation and a goal-based Pareto ranking scheme for assigning the relative strength of solutions. It also imports several features from the research on the graph coloring problem. The proposed algorithm is shown to be a more general exam timetabling problem solver in that it does not require any prior information of the timetable length to be effective. It is also tested against a few influential and recent optimization techniques and is found to be superior on four out of seven publicly available datasets.     

MaxSAT-based large neighborhood search for high school timetabling

High School Timetabling (HSTT) is a well known and wide spread problem. The problem consists of coordinating resources (e.g. teachers, rooms), times, and events (e.g. lectures) with respect to various constraints. Unfortunately, HSTT is hard to solve and just finding a feasible solution for simple variants of HSTT have been proven to be NP-complete. We propose a new algorithm for HSTT which combines local search with a novel maxSAT-based large neighborhood search. A local search algorithm is used to drive an initial solution into a local optimum and then more powerful large neighborhood search (LNS) techniques based on maxSAT are used to further improve the solution. We prove the effectiveness of our approach with experimental results on instances taken from the Third International Timetabling Competition 2011 and the XHSTT-2014 benchmark archive. We were able to model 27 out of 39 instances. The remaining 12 instances were not modeled because the currently used maxSAT formulation for XHSTT does not support resource assignments in general. For the instances which could be modeled, our algorithm shows good performance when compared to other XHSTT state-of-the-art solvers and for several instances new best known upper bounds have been computed.     

A survey of search methodologies and automated system development for examination timetabling

Examination timetabling is one of the most important administrative activities that takes place in all academic institutions. In this paper, we present a critical discussion of the research on exam timetabling which has taken place in the last decade or so. This last ten years has seen a significantly increased level of research attention for this important area. There has been a range of insightful contributions to the scientific literature both in terms of theoretical issues and practical aspects. The main aim of this survey is to highlight the new trends and key research achievements that have been carried out in the last decade. We also aim to outline a range of relevant important research issues and challenges that have been generated by this body of work. We first define the problem and discuss previous survey papers. Within our presentation of the state-of-the-art methodologies, we highlight recent research trends including hybridisations of search methodologies and the development of techniques which are motivated by raising the level of generality at which search methodologies can operate. Summarising tables are presented to provide an overall view of these techniques. We also present and discuss some important issues which have come to light concerning the public benchmark exam timetabling data. Different versions of problem datasets with the same name have been circulating in the scientific community for the last ten years and this has generated a significant amount of confusion. We clarify the situation and present a re-naming of the widely studied datasets to avoid future confusion. We also highlight which research papers have dealt with which dataset. Finally, we draw upon our discussion of the literature to present a (non-exhaustive) range of potential future research directions and open issues in exam timetabling research.     

基于贪心法和禁忌搜索的实用高校排课系统研究

在深入分析普通高校排课的流程、特点和难点的基础上，提出一个基于贪心法和禁忌搜索的排课算法。算法采用基于优先级的贪心法构造排课的初始解，进而利用禁忌搜索获得全局较优的排课结果。设计中充分考虑了当前高校课表问题的实际情况，如课程性质对排课的要求、教师的特殊要求等。实现的原型系统同时支持自动排课和交互式排课，对于一些难度较大的问题，可以通过人机交互方式来解决。通过对高校的实际排课数据进行测试，结果表明该算法可行且能够有效地提高排课效率。     

An effective hybrid algorithm for university course timetabling

The university course timetabling problem is an optimisation problem in which a set of events has to be scheduled in timeslots and located in suitable rooms. Recently, a set of benchmark instances was introduced and used for an ‘International Timetabling Competition’ to which 24 algorithms were submitted by various research groups active in the field of timetabling. We describe and analyse a hybrid metaheuristic algorithm which was developed under the very same rules and deadlines imposed by the competition and outperformed the official winner. It combines various construction heuristics, tabu search, variable neighbourhood descent and simulated annealing. Due to the complexity of developing hybrid metaheuristics, we strongly relied on an experimental methodology for configuring the algorithms as well as for choosing proper parameter settings. In particular, we used racing procedures that allow an automatic or semi-automatic configuration of algorithms with a good save in time. Our successful example shows that the systematic design of hybrid algorithms through an experimental methodology leads to high performing algorithms for hard combinatorial optimisation problems.     

Improving the modulo simplex algorithm for large-scale periodic timetabling

The periodic event scheduling problem (PESP), in which events have to be scheduled repeatedly over a given period, is a complex and well-known discrete problem with numerous real-world applications. The most prominent of them is to find periodic timetables in public transport. Although even finding a feasible solution to the PESP is NP-hard, recent achievements demonstrate the applicability and practicability of the periodic event scheduling model. In this paper we propose different approaches to improve the modulo network simplex algorithm (Nachtigall and Opitz, 2008 [17]), which is a powerful heuristic for the PESP problem, by exploiting improved search methods in the modulo simplex tableau and larger classes of cuts to escape from the many local optima. Numerical experiments on large-scale railway instances show that our algorithms not only perform better than the original method, but even outperform a state-of-the-art commercial MIP solver.     

Exact formulations and algorithm for the train timetabling problem with dynamic demand

In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time.