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.

4 1. Introduction to Scheduling Problems g h c(a) . . . ? ? f(c) d c e f 1 2 3 4 5 a b Figure 1.1: The family of Graph Coloring problems NP -hard1. Therefore, unless P = NP, they cannot be solved to optimality in polynomial time. For this reason there is much interest in heuristics or in approximation algorithms that lead to near-optimal solutions in reasonable running times. In the remaining of this section we formally present the problem classes outlined above, and we provide an example of a family of combinatorial problems. 1.1.1 Optimization Problems A combinatorial optimization problem is either a minimization or a maximization problem over a discrete combinatorial structure. Optimality relates to some cost criterion, which measures the quality of each element of the working set. An answer to the problem is one element of the working set that optimizes the cost criterion. Now we present a more formal definition of combinatorial optimization problems. Without loss of generality, in the following we restrict to minimization problems. However, the modifications for dealing with maximization problems are straightforward. Definition 1.1 (Combinatorial Optimization Problem) We define an instance pi of a combinatorial optimization problem Π as a triple 〈S,F , f〉, where S is a finite set of solutions or answers, F ⊆ S is a set of feasible solutions, and f : S → R denotes an objective function that assesses the quality of each solution in S. The issue is to find a global optimum, i.e., an element x∗ ∈ F such that f(x∗) ≤ f(x) for all x ∈ F . In these settings, the set F is called feasible set and its elements feasible solutions, whereas the elements of the set S \ F are called infeasible solutions. The relation x ∈ F is called constraint. An example of a combinatorial optimization problem that will be used throughout the thesis is the so-called min-Graph Coloring problem [57, Prob. GT4, page 191]. A pictorial represen- tation of the problem is provided in Figure 1.1, whereas its statement is as follows: Example 1.1 (The min-Graph Coloring problem) Given an undirected graph G = (V,E), the min-Graph Coloring problem consists in finding the minimum number of colors, needed to color each vertex of the graph, such that there is no edge e ∈ E connecting two vertices that have been assigned the same color. In this case an instance pi of the problem is defined as follows: any element of S represents a coloring of G, hence it is a function c : V → {1, . . . , |V |}. The set of feasible solutions, F , is 1For a comprehensive reference on the classification of computational problems see, e.g., [57]

Anteprima della Tesi di Luca Di Gaspero

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

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.