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

In questa tesi è stato presentato il primo studio sperimentale comprensivo di algoritmi on-line per la versione bicriterio del classico problema di scheduling di Graham (1966), nel quale ogni lavoro (in inglese job) è caratterizzato da una coppia di costi o pesi non negativi, rappresentanti un tempo di esecuzione ed un’occupazione di memoria.
Ogni lavoro deve essere assegnato ad ognuna delle m macchine in modo da minimizzare simultaneamente il massimo tempo di completamento (in inglese makespan), e la massima occupazione di memoria.

Mostra/Nascondi contenuto.
1 Capitolo 1 Problemi di Scheduling 1.1 Introduzione Un problema di scheduling può essere definito come un problema di allocazione di risorse. Esempi di problemi di scheduling si presentano in diverse situazioni reali come per esempio, lavori in fabbriche manifatturiere, programmi in esecuzione su un computer oppure code di attesa negli sportelli bancari. Fra questi problemi vi è una fondamentale somiglianza. Gli elementi essenziali nei problemi di scheduling sono infatti le risorse, i lavori e gli obiettivi. Le risorse sono tipicamente caratterizzate in termini delle loro capacità, sia qualitative che quantitative, cosi che in un problema di scheduling esse sono descritte dal loro tipo e dalla loro quantità. Ogni lavoro è invece descritto da informazioni che riguardano i loro tempi di esecuzione, di inizio e di consegna. Inoltre, alcuni insiemi di lavori possono essere descritti tramite vincoli di precedenza esistenti fra i lavori stessi. L’obiettivo di un problema di scheduling, è di migliorare la misura di una determinata quantità. Alcuni fra gli obiettivi più comuni nello scheduling riguardano il miglioramento del tempo di completamento totale (in inglese makespan) e del massimo tempo di ritardo (in inglese lateness). 1.2 Problemi di scheduling tradizionali In questa sezione, saranno classificati i vari problemi di scheduling, seguendo la notazione utilizzata da Graham, Lawler, Lenstra, e Rinnooy Kan [32]. Supponiamo che m macchine i M ( )mi ,...,1= , debbano processare n lavori j J ()nj ,...,1= .

Tesi di Laurea

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Roberto Giovannelli Contatta »

Composta da 115 pagine.

 

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

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