The effect of neighborhood structures on tabu search algorithm in solving course timetabling problem

The course timetabling problem must be solved by the departments of Universities at the beginning of every semester. It is a though problem which requires department to use humans and computers in order to find a proper course timetable. One of the most mentioned difficult nature of the problem is context dependent which changes even from departments to departments. Different heuristic approaches have been proposed in order to solve this kind of problem in the literature. One of the efficient solution methods for this problem is tabu search. Different neighborhood structures based on different types of move have been defined in studies using tabu search. In this paper, the effects of moves called simple and swap on the operation of tabu search are examined based on defined neighborhood structures. Also, two new neighborhood structures are proposed by using the moves called simple and swap. The fall semester of course timetabling problem of the Department of Statistics at Hacettepe University is solved utilizing four neighborhood structures and the comparison of the results obtained from these structures is given.     

Real-life examination timetabling

An examination timetabling problem at a large American university is presented. Although there are some important differences, the solution approach is based on the ITC 2007 winning solver which is integrated in the open source university timetabling system UniTime. In this work, nine real world benchmark data sets are made publicly available and the results on four of them are presented in this paper. A new approach to further decreasing the number of student conflicts by allowing some exams to be split into multiple examination periods is also studied.     

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.     

Term-end exam scheduling at United States Military Academy/West Point

Scheduling term-end exams (TEE) at the United States Military Academy in West Point is unlike any other exam timetabling problem we know of. Exam timetabling normally produces a conflict-free timetable covering a reasonably long exam period, where every exam is scheduled exactly once for all the students enrolled in the corresponding class. The situation is quite different at West Point. There are hundreds of exams to schedule over such a short time period that there is simply no feasible solution. The challenge is then to allow something that is not even considered elsewhere, that is, creating multiple sessions of some exams, scheduled at different times within the exam period, to allow each student to take all exams he/she must take. The overall objective is to find a feasible exam schedule with a minimum number of such duplicate exams.     

A Survey of Automated Timetabling

The timetabling problem consists in 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 also to Artificial Intelligence (e.g., genetic algorithms, tabu search, and constraint satisfaction). In this paper, we survey the various formulations of the problem, and the techniques and algorithms used for its solution.     

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

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

An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables

In this paper, we present an investigation into using fuzzy methodologies to guide the construction of high quality feasible examination timetabling solutions. The provision of automated solutions to the examination timetabling problem is achieved through a combination of construction and improvement. The enhancement of solutions through the use of techniques such as metaheuristics is, in some cases, dependent on the quality of the solution obtained during the construction process. With a few notable exceptions, recent research has concentrated on the improvement of solutions as opposed to focusing on investigating the ‘best’ approaches to the construction phase. Addressing this issue, our approach is based on combining multiple criteria in deciding on how the construction phase should proceed. Fuzzy methods were used to combine three single construction heuristics into three different pair wise combinations of heuristics in order to guide the order in which exams were selected to be inserted into the timetable solution. In order to investigate the approach, we compared the performance of the various heuristic approaches with respect to a number of important criteria (overall cost penalty, number of skipped exams, number of iterations of a rescheduling procedure required and computational time) on 12 well-known benchmark problems. We demonstrate that the fuzzy combination of heuristics allows high quality solutions to be constructed. On one of the 12 problems, we obtained lower penalty than any previously published constructive method and for all 12 we obtained lower penalty than when any of the single heuristics were used alone. Furthermore, we demonstrate that the fuzzy approach used less backtracking when constructing solutions than any of the single heuristics. We conclude that this novel fuzzy approach is a highly effective method for heuristically constructing solutions and, as such, has particular relevance to real-world situations in which the construction of feasible solutions is often a difficult task in its own right.     

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.     

A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling

The post enrolment course timetabling problem (PECTP) is one type of university course timetabling problems, in which a set of events has to be scheduled in time slots and located in suitable rooms according to the student enrolment data. The PECTP is an NP-hard combinatorial optimisation problem and hence is very difficult to solve to optimality. This paper proposes a hybrid approach to solve the PECTP in two phases. In the first phase, a guided search genetic algorithm is applied to solve the PECTP. This guided search genetic algorithm, integrates a guided search strategy and some local search techniques, where the guided search strategy uses a data structure that stores useful information extracted from previous good individuals to guide the generation of offspring into the population and the local search techniques are used to improve the quality of individuals. In the second phase, a tabu search heuristic is further used on the best solution obtained by the first phase to improve the optimality of the solution if possible. The proposed hybrid approach is tested on a set of benchmark PECTPs taken from the international timetabling competition in comparison with a set of state-of-the-art methods from the literature. The experimental results show that the proposed hybrid approach is able to produce promising results for the test PECTPs.     

A hyperheuristic approach to examination timetabling problems: benchmarks and a new problem from practice

Many researchers studying examination timetabling problems focus on either benchmark problems or problems from practice encountered in their institutions. Hyperheuristics are proposed as generic optimisation methods which explore the search space of heuristics rather than direct solutions. In the present study, the performance of tournament-based hyperheuristics for the exam timetabling problem are investigated. The target instances include both the Toronto and ITC 2007 benchmarks and the examination timetabling problem at KAHO Sint-Lieven (Ghent, Belgium). The Toronto and ITC 2007 benchmarks are post-enrolment-based examination timetabling problems, whereas the KAHO Sint-Lieven case is a curriculum-based examination timetabling problem. We drastically improve the previous (manually created) solution for the KAHO Sint-Lieven problem by generating a timetable that satisfies all the hard and soft constraints. We also make improvements on the best known results in the examination timetabling literature for seven out of thirteen instances for the To ronto benchmarks. The results are competitive with those of the finalists of the examination timetabling track of the International Timetabling Competition.     

The classroom assignment problem: Complexity,size reduction and heuristics

In this paper, we investigate a compound of the exam timetabling problems which consists of assigning a set of independent exams to a certain number of classrooms. We can define the exam timetabling problem as the scheduling of exams to time slots in first stage and at a second stage, the assignment of a set of exams extracted from one time slot to some available classrooms.Even though the formulation of this problem looks simple as it contains only two sets of constraints including only binary variables, we show that it belongs to the class of NP hard problems by reduction from the Numerical Matching with Target Sum problems (NMTS).In order to reduce the size of this problem and make it efficiently solvable either by exact method or heuristic approaches, a theorem is rigorously demonstrated and a reduction procedure inspired from the dominance criterion is developed. The two methods contribute in the search for a feasible solution by reducing the size of the original problem without affecting the feasibility. Since the reduction procedures do not usually assign all exams to classrooms, we propose a Variable Neighbourhood Search (VNS) algorithm in order to obtain a good quality complete solution. The objective of VNS algorithm is to reduce the total classroom capacity assigned to exams. A numerical result concerning the exam of the main session of the first semester of the academic year 2009–2010 of the Faculty of Economics and Management Sciences of Sfax shows the good performance of our approach compared with lower bound defined as the sum of the total capacity of all assigned classrooms and the total size of the remaining exams after reduction.     

Scatter search technique for exam timetabling

At universities where students enjoy flexibility in selecting courses, the Registrar’s office aims to generate an appropriate exam timetable for numerous courses and large number of students. An appropriate, real-world exam timetable should show fairness towards all students, respecting the following constraints: (a) eliminating or minimizing the number of simultaneous exams; (b) minimizing the number of consecutive exams; (c) minimizing the number of students with two or three exams per day (d) eliminating the possibility of more than three exams per day (e) exams should fit in rooms with predefined capacity; and (f) the number of exam periods is limited. These constraints are conflicting, which makes exam timetabling intractable. Hence, solving this problem in realistic time requires the use of heuristic approaches. In this work, we develop an evolutionary heuristic technique based on the scatter search approach for finding good suboptimal solutions for exam timetabling. This approach is based on maintaining and evolving a population of solutions. We evaluate our suggested technique on real-world university data and compare our results with the registrar’s manual timetable in addition to the timetables of other heuristic optimization algorithms. The experimental results show that our adapted scatter search technique generates better timetables than those produced by the registrar, manually, and by other meta-heuristics.     

分组遗传算法优化大学考试时间表

大学考试时间表是一个多约束条件下的优化问题。传统遗传算法寻优的计算量是指数级的规模,而寻优的操作有可能会破坏时间表的硬约束条件,从而最终得到的解并不一定理想甚至不可行。该文从某高校的实际应用出发,对用图着色模型得到的已经满足了硬约束条件的初始考试时间表,用改进的分组遗传算法在既不破坏硬约束条件也不延长考试周的条件下扩大并平均分配了学生的复习时间,并且还大大减少了寻优的计算量。     

An integer program and a hybrid genetic algorithm for the university timetabling problem

The university timetabling problem (UTP) has been studied by numerous research groups for decades. In addition to addressing hard and soft constraints, we extend the UTP by considering consecutiveness and periodicity constraints of multi-session lectures, which are common in many eastern Asian universities. Because schedulers can decide the consecutiveness and periodicity constraints for the multi-session lectures within a limited ratio, we consider these novel decision variables in our model. We develop a mixed integer linear program for the UTP. For the analysis, we convert the UTP into the three-dimensional container packing problem (3DCPP) and create a hybrid genetic algorithm (HGA), which has been shown to be efficient in solving the 3DCPP. We also develop a tabu search algorithm based on the existing UTP literature and compare the findings with that of our HGA. The results show that our HGA obtains a better solution than the tabu search algorithm in a reasonable amount of time.     

Fairness in examination timetabling: Student preferences and extended formulations

Variations of the examination timetabling problem have been investigated by the research community for more than two decades. The common characteristic between all problems is the fact that the definitions and datasets used all originate from actual educational institutions, particularly universities, including specific examination criteria and the students involved. Although much has been achieved and published on the state-of-the-art problem modelling and optimisation, a lack of attention has been focussed on the students involved in the process. This work presents and utilises the results of an extensive survey seeking student preferences with regard to their individual examination timetables, with the aim of producing solutions which satisfy these preferences while still also satisfying all existing benchmark considerations. The study reveals one of the main concerns relates to fairness within the student's cohort; i.e. a student considers fairness with respect to the examination timetables of their immediate peers, as highly important. Considerations such as providing an equitable distribution of preparation time between all student cohort examinations, not just a majority, are used to form a measure of fairness. In order to satisfy this requirement, we propose an extension to the state-of-the-art examination timetabling problem models widely used in the scientific literature. Fairness is introduced as a new objective in addition to the standard objectives, creating a multi-objective problem. Several real-world examination data models are extended and the benchmarks for each are used in experimentation to determine the effectiveness of a multi-stage multi-objective approach based on weighted Tchebyceff scalarisation in improving fairness along with the other objectives. The results show that the proposed model and methods allow for the production of high quality timetable solutions while also providing a trade-off between the standard soft constraints and a desired fairness for each student.     

Multiobjective multiproduct parcel distribution timetabling: a real‐world application

Multiobjective multiproduct parcel distribution timetabling problem is concerned with generating effective timetables for parcel distribution companies that provide interdependent services (products) and have more than one objective. A parcel distribution timetabling problem is inherently multiobjective because of the multitude of criteria that can measure the performance of a timetable. This paper provides the mathematical formulation of the problem and applies the model to a real‐world case study. The application shows that without a common ground with the practitioners, it would be impossible to define the actual requirements and objectives of the company; problem definition is as important as model construction and solution method.     

A hybrid method based on linear programming and tabu search for routing of logging trucks

In this paper, we consider an operational routing problem to decide the daily routes of logging trucks in forestry. This industrial problem is difficult and includes aspects such as pickup and delivery with split pickups, multiple products, time windows, several time periods, multiple depots, driver changes and a heterogeneous truck fleet. In addition, the problem size is large and the solution time limited. We describe a two-phase solution approach which transforms the problem into a standard vehicle routing problem with time windows. In the first phase, we solve an LP problem in order to find a destination of flow from supply points to demand points. Based on this solution, we create transport nodes which each defines the origin(s) and destination for a full truckload. In phase two, we make use of a standard tabu search method to combine these transport nodes, which can be considered to be customers in vehicle routing problems, into actual routes. The tabu search method is extended to consider some new features. The solution approach is tested on a set of industrial cases from major forest companies in Sweden.     

Solution approaches to the course timetabling problem

University course timetabling is one of the most important administrative activities that take place in all academic institutions. In this work, we go over the main points of recent papers on the timetabling problem. We concentrate on university timetabling and introduce hard and soft constraints as well as most currently used objective functions. We also discuss some solution methods that have been applied by researchers. Finally, we raise more questions to be explored in future studies. We hope the directions lead to new researches that cover all aspects of the problem and result in high-quality timetables.     

Train service timetabling in railway open markets by particle swarm optimisation

Railway timetabling is an important process in train service provision as it matches the transportation demand with the infrastructure capacity while customer satisfaction is also considered. It is a multi-objective optimisation problem, in which a feasible solution, rather than the optimal one, is usually taken in practice because of the time constraint. The quality of services may suffer as a result. In a railway open market, timetabling usually involves rounds of negotiations amongst a number of self-interested and independent stakeholders and hence additional objectives and constraints are imposed on the timetabling problem. While the requirements of all stakeholders are taken into consideration simultaneously, the computation demand is inevitably immense. Intelligent solution-searching techniques provide a possible solution. This paper attempts to employ a particle swarm optimisation (PSO) approach to devise a railway timetable in an open market. The suitability and performance of PSO are studied on a multi-agent-based railway open-market negotiation simulation platform.     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.