Tesi di LAUREA Titolo Mutual exclusion scheduling: formulazioni, rilassamento semidefinito positivo, metodi euristici Data 2011-02-21 Autore/i Massa, Stefano Relatore Maffioli, F. Relatore Gualandi, S. Full text non disponibile Abstract In questa tesi di laurea di primo livello ci occupiamo del MES ovvero del mutual exclusion scheduling. Tale problema risulta essere N P -difficile e quindi la sua risoluzione puó essere onerosa in termini di tempo al crescere delle dimensioni dell’istanza presa in esame. Tale problema ha applicazioni in svariati ambiti tra qui quello del working schedules planning e quindi la sua analisi risulta importante per ottenere risoluzioni approssimate vicine a quella ottima. Il MES ha un’elegante formulazione in termini di teoria dei grafi. Per determinate categorie di questi ultimi é possibile ottenere una modellizzazione matematica di problemi reali. Per ottenere risoluzioni del MES utilizziamo le formulazioni, e relativi rilassamenti, del graph equipartition e del k-min equipartition, due problemi legati al MES dal fatto che ricercano una suddivisione in insiemi indipendenti dei vertici del grafo preso in esame. Le modellizzazioni del MES usate fanno uso della programmazione semidefinita positiva.