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.

1Introduction to Scheduling Problems Combinatorial Optimization [106] is the discipline of decision making in case of discrete alterna- tives. Specifically, combinatorial problems arise in many areas where computational methods are applied, such as artificial intelligence, bio-informatics or electronic commerce, just to mention a few cases. Noticeable examples of this kind of problems include resource allocation, routing, packing, planning, scheduling, hardware design, and machine learning. The class of scheduling problems is of specific interest for this study, since we apply the tech- niques we have developed on this kind of problems. Essentially, a scheduling problem can be defined as the problem of assigning resources to activities over a time period. In this chapter we define the basic framework for dealing with scheduling problems and we introduce the terminology and the notation used throughout the thesis. 1.1 Combinatorial Problems The formal definition of the concept of problem is a very complex task. In fact, for formally defining what a problem is, we should introduce concepts of formal languages that are beyond the scope of this thesis. For this reason we resort to an intuitive definition and we define a problem as a general and abstract statement of a question/answer relation, in which some elements are left as a parameter. As an example, “can you compute the square root of a number n?” is a problem according to this informal definition, because the sentence is a question with a yes/no answer and the value of n is a parameter. Furthermore, we can define a problem instance as a specific question/answer statement where all elements are specified. For example, “can you compute the square root of 2?” is an instance of the previous problem. Problems can be grouped according to similar question statements in homogeneous problem classes. In this thesis, we focus on a specific class of problems that have a precise mathematical formulation, namely we deal with combinatorial problems. Combinatorial problems typically involve finding groupings, orderings, or assignments of a dis- crete set of objects which satisfy certain conditions or constraints. These elements are generally modeled by means of a combinatorial structure and represented through a vector of decision vari- ables which can assume values within a finite or a countably infinite set. Within these settings, a solution for a combinatorial problem is a value assignment to the variables that meets a specified criterion. The class of combinatorial problems can be subdivided into three main subclasses, that differ by the goals they consider. The class of optimization problems is characterized by the aim of finding a solution that optimizes a quality criterion and fulfills the given constraints. For decision problems, the goal is again to find a solution that satisfies all the conditions. However, in this case we accept all the solutions for which the quality measure is under a certain threshold. Finally, the class of search problems simply aims at finding a valid solution, regardless of any quality criterion. Looking at combinatorial problems from the computational complexity point of view, it has been shown that most of the problems in this class (or the corresponding decision versions) are

Anteprima della Tesi di Luca Di Gaspero

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

Tesi di Dottorato

Dipartimento: Dipartimento di Matematica e Informatica

Autore: Luca Di Gaspero Contatta »

Composta da 136 pagine.


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


Consultata integralmente una volta.

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