Catálogo de publicaciones - libros

We consider the single machine scheduling problem with dynamic job arrival and total weighted tardiness and makespan as objective functions. The machine is subject to disruptions related to late raw material arrival and machine breakdowns. We propose a proactive—reactive approach to deal with possible perturbations. In the proactive phase, instead of providing only one schedule to the decision maker, we present a set of predictive schedules. This set is characterized by a partial order of jobs and a type of associated schedules, here semi-active schedules. This allows us to dispose of some flexibility in job sequencing and flexibility in time that can be used on-line by the reactive algorithm to hedge against unforeseen disruptions. We conduct computational experiments that indicate that our approach outperforms a predictive reactive approach particularly for disruptions with low to medium amplitude.

Although tabu search is one of the most effective meta-heuristics for solving the job-shop scheduling problem (JSP), very little is known about why this approach works so well and under what conditions it excels. Our goal is to develop models of tabu search algorithms for the JSP that answer these and other related research questions. We have previously demonstrated that the mean distance between random local optima and the nearest optimal solution, denoted , is highly correlated with problem difficulty for a well-known tabu search algorithm for the JSP introduced by Taillard. In this paper, we discuss various shortcomings of the model and develop new models of problem difficulty that correct these deficiencies. We show that Taillard's algorithm can be modelled with exceptionally high fidelity using a surprisingly simple Markov chain. The Markov model also enables us to characterise the exact conditions under which different initialisation methods can be expected to improve performance. Finally, we analyse the relationship between the Markov and > models.

In this paper, we deal with multibin packing problems. These problems are linked to multiprocessor-task scheduling as well as to bin packing problems: they consist of objects to be packed into bins, with each object requiring space in several bins.

We propose an intuitive greedy approach (the best-fit rule), which extends the well-known list algorithms for multiprocessor scheduling, to solve the case when objects have fixed height and size. We prove that it provides a 2-approximation, and even a 4/3-approximation if the objects are sorted by non-increasing heights. Based on this method, a polynomial time approximation scheme (PTAS) will be developed.

Examination timetabling problems are traditionally solved by choosing a solution procedure from a plethora of heuristic algorithms based either on a direct construction principle or on some incremental improvement procedure. A number of hybrid approaches have also been examined in which a sequential heuristic and a metaheuristic are employed successively. As a rule, best results for a problem instance are obtained by implementing heuristics with domain-specific knowledge. However, solutions of this kind are not easily adoptable across different problem classes. In order to lessen the need for a problem-specific knowledge we developed a novel solution approach to examination timetabling by incorporating the case-based reasoning methodology. A solution to a given problem is constructed by implementing case-based reasoning to select a sequential heuristic, which produces a good initial solution for the Great Deluge metaheuristic. A series of computational experiments on benchmark problems were conducted which subsequently demonstrate that this approach gives comparable or better results than solutions generated not only by a single Great Deluge algorithm, but also the state-of-the-art approaches.

This paper investigates a tabu-search-based hyper-heuristic for solving examination timetabling problems. The hyper-heuristic framework uses a tabu list to monitor the performance of a collection of low-level heuristics and then make tabu heuristics that have been applied too many times, thus allowing other heuristics to be applied. Experiments carried out on examination timetabling datasets from the literature show that this approach is able to produce good quality solutions.

We examine round robin tournaments with teams and rounds, for ≥ 3, with the property that every team plays no game in one round and exactly one game in each of the remaining − 1 rounds. We show that for every such there exists a unique schedule in which no team plays two consecutive home or away games.

This paper considers a container rail service planning problem, in which customer demands are known in advance. The existing rail freight optimisation models are complex and not demand responsive. This paper focuses on constructing profitable schedules, in which service supply matches customer demands and optimises on booking preferences whilst satisfying regulatory constraints. A constraint satisfaction approach is used, in which optimisation criteria and operational requirements are formulated as soft and hard constraints respectively. We present a constraint-based search algorithm capable of handling problems of realistic size. It employs a randomised strategy for the selection of constraints and variables to explore, and uses a predictive choice model to guide and intensify the search within more promising regions of the space. Experimental results, based on real data from the Royal State Railway of Thailand, have shown good computational performance of the approach and suggest significant benefits can be achieved for both the rail company and its customers.

Of all the tasks related to bus station management, one of the most important decisions that greatly affects the quality of the service is the assignment of platforms. A bad assignment procedure may be uncomfortable for frequent passengers who often suffer changes in departure gates, or may even be affected by the lack of platforms. Assignment is complicated due to the frequent incidents that cause delays in or the moving forward of services (with the corresponding changes in assignment), and to increases in services that convert the platforms into a limited resource. Even though this problem of platform assignment has been studied in more detail in the field of airport terminals, the difficulties in road transportation are both distinct and significant. In this paper we develop an intelligent system employing rule-based models for the daily management of the platforms of a bus station. The developed system is currently being used in a real bus station with more than 1,000 daily services.

Constructing good quality fleet schedules is essential for an airline to operate in an effective and efficient way in order to accomplish high levels of consumer satisfaction and to maximise profits. The robustness of an airline schedule is an indicative measure of how good the schedule is because a robust plan allows the airline to cope with the unexpected disturbances which normally occur on a daily basis. This paper describes a method to measure the robustness of schedules for aircraft fleet scheduling within KLM Airlines. The method is based on the “Aircraft on Ground (ACOG)” measure, it employs statistical methods (although alternative methods were also considered) and it is shown to provide a good estimation of the robustness of a given schedule.