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

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

1.5. Timetabling Problems 11 (2) there must be sufficient other resources to service all the events at the times they have been scheduled. The assignment τ is called a timetable. The general timetabling problem can easily be modeled within the already presented Graph Coloring framework. The graph encoding is as follows: each event is associated to a vertex of the graph, and there is an edge between two vertices if they clash, i.e., the events cannot be scheduled in the same period because at least one individual has to attend both of them. Then, periods are regarded as colors, and the scheduling of events to periods is simply a coloring of the graph. Considerable attention has been devoted to automated timetabling during the last forty years. Starting with [67], many papers related to automated timetabling have been published in conference proceedings and journals. In addition, several applications have been developed and employed with good success. Example 1.7 (The family of Educational Timetabling problems) In this thesis we focus on the class of Educational Timetabling problems. These kind of problems consists in scheduling a sequence of events (typically lectures or examinations), involving teachers and students, in a prefixed period of time. The schedule must satisfy a set of constraints of various types, which involve, among others, avoiding the overlap of events with common participants, and not excessing the capacity of rooms. Usually the goal is to obtain solutions that minimize student and teacher’s workload. A large number of variants of Educational Timetabling problems have been proposed in the literature, which differ from each other by the type of events, the kind of institution involved (university or school) and the type and the relative influence of constraints. Noticeable examples of this class of problems are School Timetabling, Course Timetabling and Examination Timetabling. The latter two problems are discussed in detail in the applicative part of the thesis The common ground of these problems is that they all are combinatorial problems (search or optimization ones), are NP -hard, and are subject to similar types of constraints (overlap, availabil- ity, capacity, etc.). Additionally, almost all of them have been recognized to be genuinely “difficult on the average” in practical real-life cases. For this reason, such problems have not been addressed in a complete and satisfactory way yet, and are still a matter of theoretical research and experimental investigation.

Anteprima della Tesi di Luca Di Gaspero

Anteprima della tesi: Local Search Techniques and Tools for Scheduling Problems, Pagina 13

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.