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.

11 Definizione 1.12 (Min Multiprocessor Scheduling) Il problema denominato Min Multiprocessor Scheduling, può essere definito nel seguente modo: Istanza : Insieme di task (lavori) T, numero di macchine o processori h, e lunghezza o tempo di esecuzione j p associato ad ogni task. Soluzione : Uno schedule per T, ossia una funzione [ ] :1,f Th→ . Misura : Tempo di completamento dello schedule, ossia: [] () 1, | max jj j ih tft i p ∈ = ∑ . Questo problema appartiene alla classe NP-Hard, poiché il problema di decisione soggiacente è NP-completo. Ciò si dimostra utilizzando la tecnica di riduzione polinomiale, a partire dal famoso problema denominato PARTITION, che a sua volta è NP-completo. Ovviamente anche l’estensione al caso bicriterio del problema Min Multiprocessor Scheduling che sarà definito in seguito, appartiene alla classe NP-Hard. 1.4 Algoritmi di approssimazione ed algoritmi On Line In questa sezione, saranno descritti e confrontati gli algoritmi di approssimazione, gli algoritmi on line, ed i metodo più comuni utilizzati per valutarne le prestazioni. In primo luogo, diamo alcune semplici definizioni. L’estremo superiore di un insieme non vuoto A di numeri reali, denotato con Sup A, è il più piccolo numero reale u, tale che xu ≥ , per ogni Ax∈ . L’estremo inferiore di A, denotato Inf A, è il più grande numero reale l, tale che xl ≤ per ogni Ax∈ . Se A è finito, allora sia Sup A che Inf A appartengono ad A. In questo caso, essi sono chiamati minimo e massimo di A, denotati con min A e max A rispettivamente.

Anteprima della Tesi di Roberto Giovannelli

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

Tesi di Laurea

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Roberto Giovannelli Contatta »

Composta da 115 pagine.

 

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

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