Catálogo de publicaciones - libros

The study of the relationship and interaction between the work carried out in the academic literature and the requirements of university administrators is essential if ideas generated by research are to benefit every-day users. Conversely, it is crucial that the needs of the timetabling community influence the direction taken by research if high-quality practical solutions are to be produced. A main objective of the work presented here is to provide up-to-date information which will enable researchers to further investigate the area of timetabling research in relation to the generation of robust and flexible techniques which can cope with complexities experienced during implementation in ‘real world’ scenarios. Furthermore, although not discussed here in detail, it is essential, from a commercial perspective, that these developed leading edge techniques are incorporated and used within general applicable timetabling tools. The aim of this paper is to motivate the discussion required to by bringing timetabling research and educational requirements closer together.

We describe the use of very large-scale neighborhood search (VLSN) techniques in examination timetabling problems. We detail three applications of VLSN algorithms that illustrate the versatility and potential of such algorithms in timetabling. The first of these uses , in which an ordered subset of exams in disjoint time slots are swapped cyclically such that each exam moves to the time slot of the exam following it in the order. The neighborhood of all such cyclic exchanges may be searched effectively for an improving set of moves, making this technique computationally reasonable in practice. We next describe the idea of in genetic algorithms, where the parent solutions used in the genetic algorithm perform an optimization routine to produce the ‘most fit’ of their children under the crossover operation. This technique can be viewed as a form of multivariate large-scale neighborhood search, and it has been applied successfully in several areas outside timetabling. The final topic we discuss is , which gives a method of incorporating neighborhood search techniques into simulated annealing algorithms. Under this technique, the objective function is perturbed slightly to avoid stopping at local optima, while neighborhood search techniques help provide an effective search of the feasible space.

In this paper, we first discuss the level of compliance for timetabling research to two important research qualities, namely measurability and reproducibility, analyzing what we believe are the most important contributions in the literature. Secondly, we discuss some practices that, in our opinion, could contribute to the improvement on the two aforementioned qualities for future papers in timetabling research.

For the sake of brevity, we restrict our scope to university timetabling problems (exams, courses, or events), and thus we leave out other equally important timetabling problems, such as high-school, employee, and transportation timetabling.

We discuss the problem of constructing physician schedules in emergency rooms. Starting from practical instances encountered in five different hospitals of the Montreal (Canada) area, we first propose generic forms for the constraints encountered in this context. We then review several possible solution techniques that can be applied to physician scheduling problems, namely tabu search, column generation, mathematical programming and constraint programming, and examine their suitability for application depending on the specifics of the situation at hand. We conclude by discussing the problems encountered when trying to perform computational comparisons of solution techniques on the basis of implementations in different practical settings.

We propose a flexible model and several integer linear programming and constraint programming formulations for integrated employee timetabling and production scheduling problems. A hybrid constraint and linear programming exact method is designed to solve a basic integrated employee timetabling and job-shop scheduling problem for lexicographic minimization of makespan and labor costs. Preliminary computational experiments show the potential of hybrid methods.

This paper presents an empirical study on memetic algorithms in two parts. In the first part, the details of the memetic algorithm experiments with a set of well known benchmark functions are described. In the second part, a heuristic template is introduced for solving timetabling problems. Two adaptive heuristics that utilize a set of constraint-based hill climbers in a co-operative manner are designed based on this template. A hyper-heuristic is a mechanism used for managing a set of low-level heuristics. At each step, an appropriate heuristic is chosen and applied to a candidate solution. Both adaptive heuristics can be considered as hyper-heuristics. Memetic algorithms employing each hyper-heuristic separately as a single hill climber are experimented on a set of randomly generated nurse rostering problem instances. Moreover, the standard genetic algorithm and two self-generating multimeme memetic algorithms are compared to the proposed memetic algorithms and a previous study.

Four heuristic algorithms based on or inspired by the well-known Tabu Search method have been used to cast heuristically optimized schedules for a clinical training unit of a hospital. It has been found experimentally that the algorithm of choice for this problem depends on the exact goal being sought where the execution time is one of the components of the goal. If only one run is allowed, then classical Tabu Search with a tenure of 5 gave the schedule with the lowest average (and fixed) penalty. If time is not of concern and many runs are allowed then the Great Deluge algorithm may generate the schedule with the lowest penalty.

In many funding agencies a model is adopted whereby a fixed panel of evaluators evaluate the set of applications. This is then followed by a general meeting where each proposal is discussed by those evaluators assigned to it with a view to agreeing on a consensus score for that proposal. It is not uncommon for some evaluators to be unavailable for the entire duration of the meeting; constraints of this nature, and others, complicate the search for a solution and take it outside the realm of the classical graph colouring problem. In this paper we (a) report on a system developed to ensure the smooth running of such meetings and (b) compare two different ILP formulations of a sub-problem at its core, the list-colouring problem.

The traveling tournament problem considers scheduling round-robin tournaments that minimize traveling distance, which is an important issue in sports scheduling. Various studies on the traveling tournament problem have appeared in recent years, and there are some variants of this problem. In this paper, we deal with the constant distance traveling tournament problem, which is a special class of the traveling tournament problem. This variant is essentially equivalent to the problem of ‘maximizing breaks’ and that of ‘minimizing breaks’, which is another significant objective in sports scheduling. We propose a lower bound of the optimal value of the constant distance traveling tournament problem, and two constructive algorithms that produce feasible solutions whose objective values are close to the proposed lower bound. For some size of instances, one of our algorithms yields optimal solutions.

The Brazilian soccer tournament is organized every year by the Brazilian Soccer Confederation. Its major sponsor is TV Globo, the largest media group and television network in Brazil, which imposes constraints on the games to be broadcast. Scheduling the games of this tournament is a very constrained problem, with two objectives: breaks minimization (fairness) and the maximization of the revenues from TV broadcasting. We propose an integer programming decomposition strategy to solve this problem to optimality. Numerical results obtained for the 2005 and 2006 editions of the tournament are reported and compared.