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

Analisi e sperimentazione di algoritmi di scheduling bicriterio

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.

5 obiettivo può essere una qualunque funzione dei costi j f , nj ,...,1= . Comuni funzioni obiettivo sono tipicamente espresse nella forma ∑ j j f , oppure jj fmax . Esempi di comuni criteri sono il total weighted completion time jj j wc ∑ , il massimo tempo di completamento o makespan max max jj CC= , e la massima lateness max max jj LL= . 1.2.5 Esempi di problemi di scheduling Consideriamo alcuni esempi di problemi di scheduling utilizzando la notazione a tre campi. Nel problema ∑ jjj Cwr ||1 si vuole minimizzare la somma pesata dei tempi di completamento su una macchina, con date di rilascio. Nel problema max 3| , |PpmtnprecL si vuole minimizzare la massima lateness, su tre macchine parallele identiche, con vincoli di precedenza generici fra i lavori, ed interruzione consentita. 1.3 Complessità asintotica 1.3.1 Introduzione In questa sezione saranno introdotte alcune nozioni basilari sui problemi di ottimizzazione e sulle classi di complessità, che saranno utili per classificare molti dei problemi di scheduling come problemi “difficili”. Un problema di ottimizzazione di qualsiasi tipo, può essere rappresentato tramite la coppia () ,I S , dove I è un insieme di istanze del problema, e S è un insieme di soluzioni. Più precisamente, un problema è detto: • di decisione, se { } 0,1S = , ovvero bisogna decidere se l’istanza di input verifica o no una determinata proprietà; • di ricerca, se bisogna determinare una qualsiasi soluzione per l’istanza di input; • di ottimizzazione, se bisogna minimizzare o massimizzare una determinata misura della soluzione restituita.

Anteprima della Tesi di Roberto Giovannelli

Anteprima della tesi: Analisi e sperimentazione di algoritmi di scheduling bicriterio, Pagina 5

Tesi di Laurea

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Roberto Giovannelli Contatta »

Composta da 115 pagine.

 

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

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