Riassunto analitico
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.
|
Abstract
This thesis is focused on the development of exact and heuristic algorithms for scheduling and related problems. The thesis contains an initial introductory chapter, five research chapters, one for each considered problem and, a final conclusion chapter. The first part focuses on the research on the identical parallel machine scheduling problem to minimize the Total Weighted Completion Time (TWCT) of the jobs. New enhanced arc-flow formulations are proposed to solve the problem. Computational results show a superior performance of the main developed method when compared with the state-of-the-art exact approaches from the literature. In the second chapter, a scheduling problem with family setup times is tackled. In this problem, a set of identical parallel machines are available to process a set of jobs which are partitioned into families. Each time a pair of jobs belonging to different families is scheduled consecutively on the same machine a setup must be performed. The objective is to find a schedule with minimum TWCT. A set of Mixed Integer Linear Programs (MILPs), simple but effective valid inequalities and a branch-and-price algorithm are developed. The computational results indicate the efficiency of the best proposed methods when compared to the literature. The third problem regards another parallel machine scheduling problem to minimize the TWCT. In this version, instead of family setup times there are release dates on the jobs. The problem is addressed from an exact point of view by the development of a tailored branch-and-price algorithm. The proposed algorithm encompasses a heuristic method for obtaining good quality initial solutions, pricing heuristics and efficient exact dynamic programming algorithms to accelerate the subproblem resolution as well as other features such as stabilization techniques. The fourth part concerns the Dynamic Berth Allocation Problem (DBAP). The DBAP aims at allocating container vessels along a quay partitioned into berths, while reducing the sum of vessels turnaround time. In the DBAP, each vessel has a service time, depending on the berth, and must be served within a time window. Two novel MILP formulations, modeling enhancements and a reduced-cost variable-fixing procedure, with the aim of reducing the formulations sizes and execution times, are proposed. Extensive computational experiments have been carried out on benchmark instances from the literature as well as on a new proposed set of instances. The obtained results show that our best approach is competitive when compared with the best method in the literature. The last part of the thesis is dedicated to a real management problem faced by an Emergency Department (ED) of a hospital located in the north of Italy. The goal of the study is to understand, model and propose changes in the system with the aim of improving patients’ satisfaction, e.g., reducing their waiting time and length of stay. To deal with this problem, a Discrete Event Simulation (DES) model is developed as a supporting tool. The DES model allows the proposition and analysis of multiple scenarios. Among these scenarios, one of them has been chosen to be implemented in practice by the considered ED. In conclusion, the thesis deals with the development of efficient exact algorithms to solve relevant theoretical and practical scheduling and related problems.
|