Skip to content

Local Search Techniques and Tools for Scheduling Problems

Informazioni tesi

  Autore: Luca Di Gaspero
  Tipo: Tesi di Dottorato
Dottorato in Dottorato di Ricerca in Informatica
Anno: 2003
Docente/Relatore: Schaerf Andrea
Istituito da: Università degli Studi di Udine
Dipartimento: Dipartimento di Matematica e Informatica
  Lingua: Inglese
  Num. pagine: 136

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.


La consultazione è esclusivamente in formato digitale .PDF

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.


La consultazione è esclusivamente in formato digitale .PDF



Per consultare la tesi è necessario essere registrati e acquistare la consultazione integrale del file, al costo di 29,89€.
Il pagamento può essere effettuato tramite carta di credito/carta prepagata, PayPal, bonifico bancario, bollettino postale.
Confermato il pagamento si potrà consultare i file esclusivamente in formato .PDF accedendo alla propria Home Personale. Si potrà quindi procedere a salvare o stampare il file.
Maggiori informazioni
Ingiustamente snobbata durante le ricerche bibliografiche, una tesi di laurea si rivela decisamente utile:
  • perché affronta un singolo argomento in modo sintetico e specifico come altri testi non fanno;
  • perché è un lavoro originale che si basa su una ricerca bibliografica accurata;
  • perché, a differenza di altri materiali che puoi reperire online, una tesi di laurea è stata verificata da un docente universitario e dalla commissione in sede d'esame. La nostra redazione inoltre controlla prima della pubblicazione la completezza dei materiali e, dal 2009, anche l'originalità della tesi attraverso il software antiplagio
  • L'utilizzo della consultazione integrale della tesi da parte dell'Utente che ne acquista il diritto è da considerarsi esclusivamente privato.
  • Nel caso in cui l'Utente volesse pubblicare o citare una tesi presente nel database del sito deve ottenere autorizzazione scritta dall'Autore della tesi stessa, il quale è unico detentore dei diritti.
  • L'Utente è l'unico ed esclusivo responsabile del materiale di cui acquista il diritto alla consultazione. Si impegna a non divulgare a mezzo stampa, editoria in genere, televisione, radio, Internet e/o qualsiasi altro mezzo divulgativo esistente o che venisse inventato, il contenuto della tesi che consulta o stralci della medesima. Verrà perseguito legalmente nel caso di riproduzione totale e/o parziale su qualsiasi mezzo e/o su qualsiasi supporto, nel caso di divulgazione nonché nel caso di ricavo economico derivante dallo sfruttamento del diritto acquisito.
  • L'Utente è a conoscenza che l'importo da lui pagato per la consultazione integrale della tesi prescelta è ripartito, a partire dalla seconda consultazione assoluta nell'anno in corso, al 50% tra l'Autore/i della tesi e Tesionline Srl, la società titolare del sito
L'obiettivo di Tesionline è quello di rendere accessibile a una platea il più possibile vasta il patrimonio di cultura e conoscenza contenuto nelle tesi.
Per raggiungerlo, è fondamentale superare la barriera rappresentata dalla lingua. Ecco perché cerchiamo persone disponibili ad effettuare la traduzione delle tesi pubblicate nel nostro sito.

Scopri come funziona »

DUBBI? Contattaci

Contatta la redazione a
[email protected]

Ci trovi su Skype (redazione_tesi)
dalle 9:00 alle 13:00

Oppure vieni a trovarci su

Parole chiave

software framework
object oriented programming
engineering algorithms
generic programming
local search

Non hai trovato quello che cercavi?

Abbiamo più di 45.000 Tesi di Laurea: cerca nel nostro database

Oppure consulta la sezione dedicata ad appunti universitari selezionati e pubblicati dalla nostra redazione

Ottimizza la tua ricerca:

  • individua con precisione le parole chiave specifiche della tua ricerca
  • elimina i termini non significativi (aggettivi, articoli, avverbi...)
  • se non hai risultati amplia la ricerca con termini via via più generici (ad esempio da "anziano oncologico" a "paziente oncologico")
  • utilizza la ricerca avanzata
  • utilizza gli operatori booleani (and, or, "")

Idee per la tesi?

Scopri le migliori tesi scelte da noi sugli argomenti recenti

Come si scrive una tesi di laurea?

A quale cattedra chiedere la tesi? Quale sarà il docente più disponibile? Quale l'argomento più interessante per me? ...e quale quello più interessante per il mondo del lavoro?

Scarica gratuitamente la nostra guida "Come si scrive una tesi di laurea" e iscriviti alla newsletter per ricevere consigli e materiale utile.

La tesi l'ho già scritta,
ora cosa ne faccio?

La tua tesi ti ha aiutato ad ottenere quel sudato titolo di studio, ma può darti molto di più: ti differenzia dai tuoi colleghi universitari, mostra i tuoi interessi ed è un lavoro di ricerca unico, che può essere utile anche ad altri.

Il nostro consiglio è di non sprecare tutto questo lavoro:

È ora di pubblicare la tesi