Skip to content

Analisi e confronto di algoritmi euristici per il Resource-Constrained Project Scheduling Problem

Informazioni tesi

  Autore: Salvatore Grimaldi
  Tipo: Laurea liv.I
  Anno: 2004-05
  Università: Università degli Studi di Siena
  Facoltà: Ingegneria
  Corso: Ingegneria gestionale
  Relatore: Alessandro Agnetis
  Lingua: Italiano
  Num. pagine: 88

Le tecniche di pianificazione e allocazione di risorse all’interno delle attività di un progetto, hanno attratto negli ultimi anni una sempre più crescente attenzione. Questo interesse è stato largamente motivato dalla reale importanza pratica e applicabilità che esse assumono in campo industriale e nel mondo del lavoro, si pensi ad esempio: alla produzione di manufatti a commessa, alla realizzazione di nuovi prodotti o di prototipi, alle grandi opere di costruzione, all’istallazione di impianti industriali, allo sviluppo di nuovi sistemi etc. Sia nel settore della produzione che in quello dei servizi, molte società e organizzazioni hanno una struttura basata su progetto, di conseguenza si può dedurre quanto sia importante una corretta opera di pianificazione e controllo delle fasi di un progetto, per evitare di incorrere in problemi quali superamento del budget stanziato, penali amministrative, perdita di alcune caratteristiche peculiari del progetto stesso. I tre elementi fondamentali per il successo di un progetto sono il tempo, il costo, e la qualità, ma molti operatori del settore sostengono, specialmente in campo industriale che la variabile tempo ha un ruolo predominante. Anche perchè, un progetto la cui durata è in linea con quanto pianificato, permette di rispettare il budget previsionale sulle entrate e molto spesso è sinonimo di corretta gestione della tempistica e delle risorse. Il problema in evidenza in questa tesi, chiamato in letteratura RCPSP( Resource Constrained Project Scheduling Problem) si pone l’obiettivo di minimizzare la durata del progetto in presenza di vincoli sulle risorse e di vincoli di precedenza che ogni attività facente parte del progetto deve rispettare per essere correttamente schedulata. In generale risolvere un problema di RCPSP significa ricercare uno schedule ottimo per le attività di un progetto che soddisfi non solo i vincoli di precedenza, ma che provveda anche ad una corretta allocazione delle risorse disponibili quali: manodopera, materie prime, macchinari, equipaggiamenti, capital budget, etc. La ricerca di una soluzione ottima per le istanze di RCPSP specialmente per i problemi che possono capitare in pratica, è un’operazione intrattabile non appena la dimensione del problema diventa significativa e può impedire di risolvere all’ottimo il problema in tempi ragionevoli. Del resto questo problema fa parte della classe NP-Hard ovvero dei problemi di ottimizzazione più difficili, per convincersi di ciò basta osservare che RCPSP generalizza un problema NP-completo noto con il nome Partition. Per ovviare a questa limitazione si ricorre ad approcci euristici che spesso costringono a sacrificare la qualità della soluzione a scapito di tempi di esecuzione accettabili. Normalmente le tecniche euristiche sono algoritmi con una bassa complessità che non garantiscono di ottenere la soluzione ottima, ma in generale sono in grado di fornire una buona soluzione ammissibile per il problema.Lo scopo che si prefigge questa tesi è quello di confrontare e valutare un approccio euristico al problema del RCPSP, gli algoritmi trattati maggiormente in questo lavoro sono di tipo greedy-like e costruiscono lo schedule del progetto iterativamente in conformità a una regola di priorità e a un determinato criterio di assegnazione degli istanti di tempo alle attività selezionate. Il lavoro di tesi riguarda, in primo luogo, proprio lo studio e l’implementazione di algoritmi euristici quali Greedy Seriale e Greedy Parallelo per verificare il comportamento e le variazioni rispetto all’ottimo che si hanno in relazione a una regola di priorità prescelta. In seguito, determinata la regola migliore tra quelle testate, lo studio è esteso all’intorno della soluzione precedentemente determinata mediante l’utilizzo di algoritmi meta-euristici. Gli algoritmi meta-euristici che sono oggetto di questa tesi sono: il simulated annealing, il tabu search e gli algoritmi genetici. Queste tecniche sono state implementate in Matlab, e sono state testate sul campione di istanze. L’oggetto della ricerca è quello di confrontare e valutare il comportamento di questi algoritmi meta-euristici in relazione all’ottimo in modo cosi da individuare quale dei seguenti approcci ha una migliore performance in termini di numero di iterazioni, tempo di calcolo e qualità della soluzione trovata. Inoltre si vuole determinare l’entità del miglioramento della soluzione fornita da questi approcci rispetto alla soluzione iniziale individuata con un algoritmo greedy. Addentrandoci nello specifico del lavoro, lo studio è stato svolto su un campione di 200 istanze di RCPSP caratterizzate da un numero variabile di attività o job che non possono essere interrotte( non-preemption) e che hanno un certo fabbisogno di risorse. Ogni istanza è rappresentata tramite un grafo aciclico AoN dove le attività rappresentate dai nodi del grafo sono topologicamente interconnesse.

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista
Mostra/Nascondi contenuto.
Introduzione Le tecniche di pianificazione e allocazione di risorse all’interno delle attività di un progetto, hanno attratto negli ultimi anni una sempre più crescente attenzione. Questo interesse è stato largamente motivato dalla reale importanza pratica e applicabilità che esse assumono in campo industriale e nel mondo del lavoro, si pensi ad esempio: alla produzione di manufatti a commessa, alla realizzazione di nuovi prodotti o di prototipi, alle grandi opere di costruzione, all’istallazione di impianti industriali, allo sviluppo di nuovi sistemi etc. Sia nel settore della produzione che in quello dei servizi, molte società e organizzazioni hanno una struttura basata su progetto, di conseguenza si può dedurre quanto sia importante una corretta opera di pianificazione e controllo delle fasi di un progetto, per evitare di incorrere in problemi quali superamento del budget stanziato, penali amministrative, perdita di alcune caratteristiche peculiari del progetto stesso. I tre elementi fondamentali per il successo di un progetto sono il tempo, il costo, e la qualità, ma molti operatori del settore sostengono, specialmente in campo industriale che la variabile tempo ha un ruolo predominante. Anche perchè, un progetto la cui durata è in linea con quanto pianificato, permette di rispettare il budget previsionale sulle entrate e molto spesso è sinonimo di corretta gestione della tempistica e delle risorse. Il problema in evidenza in questa tesi, chiamato in letteratura RCPSP( Resource Constrained Project Scheduling Problem) si pone l’obiettivo di minimizzare la durata del progetto in presenza di vincoli sulle risorse e di vincoli di precedenza che ogni attività facente parte del progetto deve rispettare per essere correttamente schedulata. In generale risolvere un problema di RCPSP significa ricercare uno schedule ottimo per le attività di un progetto che soddisfi non solo i vincoli di

CONSULTA INTEGRALMENTE QUESTA TESI

La consultazione è esclusivamente in formato digitale .PDF

Acquista

FAQ

Per consultare la tesi è necessario essere registrati e acquistare la consultazione integrale del file, al costo di 29,89€.
Il pagamento può essere effettuato tramite carta di credito/carta prepagata, PayPal, bonifico bancario, bollettino postale.
Confermato il pagamento si potrà consultare i file esclusivamente in formato .PDF accedendo alla propria Home Personale. Si potrà quindi procedere a salvare o stampare il file.
Maggiori informazioni
Ingiustamente snobbata durante le ricerche bibliografiche, una tesi di laurea si rivela decisamente utile:
  • perché affronta un singolo argomento in modo sintetico e specifico come altri testi non fanno;
  • perché è un lavoro originale che si basa su una ricerca bibliografica accurata;
  • perché, a differenza di altri materiali che puoi reperire online, una tesi di laurea è stata verificata da un docente universitario e dalla commissione in sede d'esame. La nostra redazione inoltre controlla prima della pubblicazione la completezza dei materiali e, dal 2009, anche l'originalità della tesi attraverso il software antiplagio Compilatio.net.
  • L'utilizzo della consultazione integrale della tesi da parte dell'Utente che ne acquista il diritto è da considerarsi esclusivamente privato.
  • Nel caso in cui l'Utente volesse pubblicare o citare una tesi presente nel database del sito www.tesionline.it deve ottenere autorizzazione scritta dall'Autore della tesi stessa, il quale è unico detentore dei diritti.
  • L'Utente è l'unico ed esclusivo responsabile del materiale di cui acquista il diritto alla consultazione. Si impegna a non divulgare a mezzo stampa, editoria in genere, televisione, radio, Internet e/o qualsiasi altro mezzo divulgativo esistente o che venisse inventato, il contenuto della tesi che consulta o stralci della medesima. Verrà perseguito legalmente nel caso di riproduzione totale e/o parziale su qualsiasi mezzo e/o su qualsiasi supporto, nel caso di divulgazione nonché nel caso di ricavo economico derivante dallo sfruttamento del diritto acquisito.
  • L'Utente è a conoscenza che l'importo da lui pagato per la consultazione integrale della tesi prescelta è ripartito, a partire dalla seconda consultazione assoluta nell'anno in corso, al 50% tra l'Autore/i della tesi e Tesionline Srl, la società titolare del sito www.tesionline.it.
L'obiettivo di Tesionline è quello di rendere accessibile a una platea il più possibile vasta il patrimonio di cultura e conoscenza contenuto nelle tesi.
Per raggiungerlo, è fondamentale superare la barriera rappresentata dalla lingua. Ecco perché cerchiamo persone disponibili ad effettuare la traduzione delle tesi pubblicate nel nostro sito.
Scopri come funziona

DUBBI? Contattaci

Contatta la redazione a
[email protected]

Ci trovi su Skype (redazione_tesi)
dalle 9:00 alle 13:00

Oppure vieni a trovarci su

Parole chiave

algoritmi greedy
algoritmo genetico
branch and bound
gestione progetti
ottimizzazione
rcpsp
regole priorità
scheduling
simulated annealing
tabu search

Non hai trovato quello che cercavi?


Abbiamo più di 45.000 Tesi di Laurea: cerca nel nostro database

Oppure consulta la sezione dedicata ad appunti universitari selezionati e pubblicati dalla nostra redazione

Ottimizza la tua ricerca:

  • individua con precisione le parole chiave specifiche della tua ricerca
  • elimina i termini non significativi (aggettivi, articoli, avverbi...)
  • se non hai risultati amplia la ricerca con termini via via più generici (ad esempio da "anziano oncologico" a "paziente oncologico")
  • utilizza la ricerca avanzata
  • utilizza gli operatori booleani (and, or, "")

Idee per la tesi?

Scopri le migliori tesi scelte da noi sugli argomenti recenti


Come si scrive una tesi di laurea?


A quale cattedra chiedere la tesi? Quale sarà il docente più disponibile? Quale l'argomento più interessante per me? ...e quale quello più interessante per il mondo del lavoro?

Scarica gratuitamente la nostra guida "Come si scrive una tesi di laurea" e iscriviti alla newsletter per ricevere consigli e materiale utile.


La tesi l'ho già scritta,
ora cosa ne faccio?


La tua tesi ti ha aiutato ad ottenere quel sudato titolo di studio, ma può darti molto di più: ti differenzia dai tuoi colleghi universitari, mostra i tuoi interessi ed è un lavoro di ricerca unico, che può essere utile anche ad altri.

Il nostro consiglio è di non sprecare tutto questo lavoro:

È ora di pubblicare la tesi