Catálogo de publicaciones - libros

Optimization in sports is a field of increasing interest. Combinatorial optimization techniques have been applied, for example, to game scheduling and playoff elimination. A common problem usually found in sports management is the assignment of referees to games already scheduled. There are a number of rules and objectives that should be taken into account when referees are assigned to games. We address a simplified version of a referee assignment problem common to many amateur leagues of sports such as soccer, baseball, and basketball. The problem is formulated by integer programming and its decision version is proved to be NP-complete. To tackle real-life large instances of the referee assignment problem, we propose a three-phase heuristic approach based on a constructive procedure, a repair heuristic to make solutions feasible, and a local search heuristic to improve feasible solutions. Numerical results on realistic instances are presented and discussed.

The qualifying phase of the Chilean soccer championship follows the structure of a compact single round robin tournament. Good schedules are of major importance for the success of the tournament, making them more balanced, profitable, and attractive. The schedules were prepared by ad hoc procedures until 2004, when a rough integer programming strategy was proposed. In this work, we improve the original integer programming formulation. We derive valid inequalities for improving the linear relaxation bound and we propose a new branch-and-cut strategy for the problem. Computational results on a real-life instance illustrate the effectiveness of the approach and the improvement in solution quality.

The modeling and solution approaches being used to automate construction of course timetables at a large university are discussed. A course structure model is presented that allows this complex real-world problem to be described using a classical formulation. The problem is then tackled utilizing a course timetabling solver model that transforms it into a constraint satisfaction and optimization problem. The tiered structure of this approach provides flexibility that is helpful in solving the multiple subproblems that arise from decomposition of the university-wide problem. A production system has been partially implemented and results of early use are presented. Practical issues raised during the implementation of the automated timetabling system are also discussed.

The students of the Industrial Design department at the TU Eindhoven are allowed to design part of their curriculum by selecting courses from a huge course pool. They do this by handing in ordered preference lists with their favorite courses for the forthcoming time period. Based on this information (and on many other constraints), the department then assigns courses to students. Until recently, the assignment was computed by human schedulers who used a quite straightforward greedy approach. In 2005, however, the number of students increased substantially, and as a consequence the greedy approach no longer yielded acceptable results.

This paper discusses the solution of this real-world timetabling problem. We present a complete mathematical formulation of it, and we explain all the constraints resulting from the situation in Eindhoven. We solve the problem using lexicographical optimization with four subproblems. For all four subproblems, an elegant integer linear programming model is given which easily can be put into CPLEX. Finally, we report on our computational experiments and results around the Eindhoven real-world data.

A standard problem within universities is that of teaching space allocation which can be thought of as the assignment of rooms and times to various teaching activities. The focus is usually on courses that are expected to fit into one room. However, it can also happen that the course will need to be broken up, or ‘split’, into multiple sections. A lecture might be too large to fit into any one room. Another common example is that of seminars or tutorials. Although hundreds of students may be enrolled on a course, it is often subdivided into particular types and sizes of events dependent on the pedagogic requirements of that particular course.

Typically, decisions as to how to split courses need to be made within the context of limited space requirements. Institutions do not have an unlimited number of teaching rooms, and need to effectively use those that they do have. The efficiency of space usage is usually measured by the overall ‘utilisation’ which is basically the fraction of the available seat-hours that are actually used. A multi-objective optimisation problem naturally arises; with a trade-off between satisfying preferences on splitting, a desire to increase utilisation, and also to satisfy other constraints such as those based on event location and timetabling conflicts. In this paper, we explore such trade-offs. The explorations themselves are based on a local search method that attempts to optimise the space utilisation by means of a ‘dynamic splitting’ strategy. The local moves are designed to improve utilisation and satisfy the other constraints, but are also allowed to split, and un-split, courses so as to simultaneously meet the splitting objectives.

The timetabling problem is well known to be an NP-complete combinatorial problem. The problem becomes even more complex when addressed to individual timetables of students. The core of dealing with the problem in this application is a timetable builder based on mixed direct–indirect encoding evolved by a genetic algorithm with a self-adaptation paradigm, where the parameters of the genetic algorithm are optimized during the same evolution cycle as the problem itself. The aim of this paper is to present an encoding for self-adaptation of genetic algorithms that is suitable for timetabling problems. Compared to previous approaches we designed the encoding for self-adaptation of not only one parameter or several ones but for all possible parameters of genetic algorithms at the same time. The proposed self-adaptive genetic algorithm is then applied for solving the real university timetabling problem and compared with a standard genetic algorithm. The main advantage of this approach is that it makes it possible to solve a wide range of timetabling and scheduling problems without setting parameters for each kind of problem in advance. Unlike common timetabling problems, the algorithm was applied to the problem in which each student has an individual timetable, so we also present and discuss the algorithm for optimized enrollment of students that minimizes the number of clashing constraints for students.

This paper describes a case study for constructing the yearly schedule of a secondary school in the Netherlands. This construction is divided in three steps. In the first step we create cluster schemes containing the optional subjects. A cluster scheme consists of cluster lines, and a cluster line contains classes which will be taught simultaneously. Part of the problem is that the students are not yet assigned to the classes. Once the cluster schemes are fixed, it remains to schedule the lessons to time slots and rooms. We first schedule the lessons to day-parts, and once this is completed we schedule the lessons to time slots within the day-parts. Thanks to consistency checks in the day-part phase, going from day-parts to time slots is possible. Finally, in the third step, we improve the previously found schedule by a tabu search using ejection chains. Compared to hand-made schedules, the results are very promising.

Prespecified meetings between teachers and parents have to be scheduled. All meetings have the same duration. The goal is in finding a schedule minimizing the total time and the parents’ idle times. This NP-hard problem is addressed by solving first a sequence of weighted assignment problems and then performing a large scale neighborhood search based on finding negative cost cycles and shortest paths in directed graphs. This approach provides good computational results. Finally a variant of the problem with two different durations for the meetings is considered.

A hierarchical timetable is one made by recursively joining smaller timetables together into larger ones. Hierarchical timetables exhibit a desirable regularity of structure, at the cost of some limitation of choice in construction. This paper describes a method of specifying hierarchical timetables using mathematical operators, and introduces a data structure which supports the efficient and flexible construction of timetables specified in this way. The approach has been implemented in KTS, a web-based high school timetabling system created by the author.

KTS is a web-based high school timetabling system, freely accessible on the Internet. This paper is a general survey of KTS, including its data model, user interface, and solver. The solver uses operations research models in a polynomial-time heuristic framework to produce high quality solutions in a few seconds. Results are presented for six instances taken from Australian high schools.