Algoritmi esatti ed euristici per problemi di schedulazione

Questa tesi è focalizzata sullo sviluppo di metodi esatti ed euristici per la risoluzione di problemi di schedulazione e problemi correlati. La tesi è strutturata in un capitolo introduttorio, cinque capitoli di ricerca, uno per ogni problema studiato e un breve capitolo conclusivo. Il primo capitolo di ricerca è focalizzato su un problema di schedulazione su Macchine Parallele Identiche (MPI) con l'obbiettivo di minimizzare il Tempo Pesato Totale di Completamento (TPTC) dei lavori. Nuove formulazioni arc-flow sono proposte per risolvere il problema. I risultati computazionali dimostrano una performance superiore del principale metodo sviluppato quando comparato con i migliori metodi esatti della letteratura. Nella seconda parte della tesi, un problema di schedulazione con tempi di setup per famiglia è affrontato. In questo problema, un insieme di MPI è disponibile per lavorare un insieme di lavori partizionato in famiglie. Ogni volta che una coppia di lavori di famiglie diverse è schedulata consecutivamente nella medesima macchina, un setup deve essere eseguito. L'obbiettivo è di trovare la schedulazione con minimo TPTC. Un insieme di modelli di Programmazione Lineare Intera Mista (PLIM), semplici disuguaglianze valide e un metodo branch-and-price sono sviluppati. I risultati computazionali indicano l'efficienza dei metodi proposti in comparazione ai risultati della letteratura. Il terzo problema riguarda ancora la minimizzazione del TPCT su MPI. In questa versione, invece dei tempi di setup per famiglia ci sono date di rilascio sui lavori. Il problema viene affrontato da un punto di vista esatto mediante lo sviluppo di un algoritmo branch-and-price avanzato. L'algoritmo proposto comprende un metodo euristico per ottenere soluzioni iniziali di buona qualità, metodi euristici e algoritmi esatti efficienti per accelerare la risoluzione del sotto problema e altre strategie quali le tecniche di stabilizzazione. La quarta parte riguarda il Dynamic Berth Allocation Problem (DBAP). Il DBAP ha lo scopo di allocare le navi portacontainer lungo un molo suddiviso in baie riducendo la somma dei tempi di risposta delle navi. Nel DBAP, ogni nave ha un tempo di servizio dipendente della baia e deve essere servita entro una finestra temporale. Vengono proposte due nuove formulazioni PLIM, alcuni miglioramenti dei modelli e una procedura di fissaggio di variabili basata sui costi ridotti, con l'obiettivo di ridurre le dimensioni delle formulazioni e i tempi di esecuzione. Esperimenti computazionali condotti su istanze dalla letteratura e su un nuovo set di istanze dimostrano che il nostro miglior approccio è competitivo rispetto alla letteratura. L'ultima parte della tesi è dedicata ad un problema gestionale reale affrontato da un Pronto Soccorso (PS) di un ospedale situato nel nord Italia. L'obiettivo dello studio è capire, modellare e proporre cambiamenti nel sistema con l'obiettivo di migliorare la soddisfazione dei pazienti, ad esempio riducendo i loro tempi di attesa e permanenza. Per affrontare questo problema un modello di Simulazione a Eventi Discreti (SED) è stato sviluppato. Il modello SED consente di analizzare una serie di scenari migliorativi. Tra questi scenari, uno è stato scelto per essere implementato nella pratica dal PS considerato. In conclusione, la tesi si occupa dello sviluppo di algoritmi esatti ed euristici efficienti per risolvere rilevanti problemi teorici e pratici di schedulazione e problemi correlati.