Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Local Search Techniques and Tools for Scheduling Problems

Local Search meta-heuristics are an emerging class of methods for tackling combinatorial search and optimization problems, which recently have been shown to be very effective for a large number of combinatorial problems. The Local Search techniques are based on the iterative exploration of a solution space: at each iteration, a Local Search algorithm steps from one solution to one of its “neighbors”, i.e., solutions that are (in some sense) close to the starting one. One major drawback of this family of techniques is the lack of robustness on a wide variety of problem instances. In fact, in many cases, these methods assure finding good results in reasonable running times, whereas in other cases Local Search techniques are trapped in the so-called local minima. Several approaches to the solution of this problem recently appeared in the literature. These approaches range from the employment of statistical properties (e.g., random explorations of the solution space), to the application of learning methods or hybrid techniques. In this thesis we propose an alternative approach to cope with local minima, which is based on the principled combination of several neighborhood structures. We introduce a set of neighborhood operators that, given a collection of basic neighborhoods, automatically create a new compound neighborhood and prescribe the strategies for its exploration. We call this approach Multi-Neighborhood Search. Although a broad range of problems can be tackled by means of Local Search, in this work we restrict our attention to scheduling problems, i.e., the problems of associating one or several resources to activities over a certain time period. This is the applicative domain of our research. We present the application of Multi-Neighborhood Search to a selected set of scheduling problems. Namely, the problems tackled in this thesis belong to the classes of educational timetabling, workforce assignment and production scheduling problems. In general, we obtain improvements w.r.t. classical solution techniques used in this field. An additional research line pursued in the thesis deals with the issues raised by the implementation of Local Search algorithms. The main problem is related to the difficulty of engineering the code developed for Local Search applications. In order to overcome this problem we designed and developed an Object-Oriented framework as a general tool for the implementation of Local Search algorithms. The framework, called EasyLocal++, favors the development of well-engineered Local Search applications, by helping the user to derive a neat conceptual scheme of the application and by supporting the design and the rapid implementation of new compound techniques. Therefore, EasyLocal++ allows the user to focus on the most difficult parts of the development process, i.e., the design and the experimental analysis of the heuristics.

Mostra/Nascondi contenuto.
Introduction The Calvin and Hobbes strip reported in the first page is a nutshell description of our work. Similarly to Calvin, we deal with high-quality organization of time. However, our real “homework” is to devise the ETM1 for drawing up the schedules, rather than carrying out the assignments as Calvin will do. For this purpose, we have also our own Hobbes tiger (i.e., a quality measure) that gives us an objective judgment of the schedules we developed. In our work we look inside several ETMs, arising from different domains. Actually, these ETMs in the scientific terminology are the methods to tackle scheduling problems. This thesis mainly deals with a specific class of these methods. Scheduling problems can be defined as the task of associating one or several resources to ac- tivities over a certain time period. These problems are of particular interest both in the research community and in the industrial environment. They commonly arise in business operations, espe- cially in the areas of supply chain management, airline flight crew scheduling, and scheduling for manufacturing and assembling. High-quality solutions to instances of these problems can result in huge financial savings. Moreover, scheduling problems arise also in other organizations, such as schools (and at home, as Calvin suggested), universities or hospitals. In these cases other aspects beside the financial one are more meaningful. For instance, a good school or university timetable improves students’ satisfaction, while a well-done nurse rostering (i.e., the shift assignment in hospitals) is of critical importance for assuring an adequate health-care level to patients. Differently from Calvin, in order to draw up a schedule for these problems we cannot start with pencil and paper. Generally speaking, scheduling problems belong to the class of combinatorial optimization problems. Furthermore, in non-trivial cases these problems are NP -hard and it is extremely unlikely that someone could find an efficient method (i.e., a polynomial algorithm) for solving them exactly. For this reason our solution methods are based on heuristic algorithms that do not assure us to find the “best” solution, but which perform fairly well in practice. The algorithms studied in this thesis belong to the Local Search paradigm described in the following. Local Search methods are based on the simple idea of navigating a solution space by iteratively stepping from one solution to one of its neighbors. The neighborhood of a solution is usually given in an intensional fashion, i.e., in terms of atomic local changes that can be applied upon it. Furthermore, each solution is assigned a quality measure by means of a problem dependent cost function, that is exploited to guide the exploration of the solutions. On this simple setting it is possible to design a wide variety of abstract algorithms or meta- heuristics such as Hill Climbing, Simulated Annealing, or Tabu Search. These techniques are non-exhaustive in the sense that they do not guarantee to find a feasible (or optimal) solution, but they search non-systematically until a specific stop criterion is satisfied. Individual heuristics do not always perform well on all problem instances, even though a com- mon requirement of approximation algorithms is to be robust on a wide variety of instances. To cope with this issue, a possible direction to pursue is the employment of several heuristics on the same problem. This should reduce the bias of a specific heuristic to be applied on a given instance. Furthermore, this idea opens the way to a line of research which attempts to investigate new compound Local Search methods obtained by combination of neighborhoods and basic techniques. 1ETM is the short for “Effective Time Management” (see the first page). We remark that it is absolutely not a scientific term, but a word invented by the cartoonist.

Tesi di Dottorato

Dipartimento: Dipartimento di Matematica e Informatica

Autore: Luca Di Gaspero Contatta »

Composta da 136 pagine.


Questa tesi ha raggiunto 658 click dal 20/03/2004.


Consultata integralmente una volta.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.