Approximation Algorithms for Uniform Parallel Machine Scheduling through Mathematical Programming

Prendere decisioni in modo attivo ed informato è una parte fondamentale dell'intelletto umano. La Ricerca Operativa è l'ingegnerizzazione di questo processo. Un problema di Ricerca Operativa viene normalmente espresso tramite il linguaggio matematico dell'Ottimizzazione, che cerca di massimizzare un dato obiettivo, espresso come funzione di certe variabili decisionali, soddisfacendo comunque i vincoli dati. Se le variabili decisionali sono continue, e sia l'obiettivo che i vincoli sono funzioni convesse, il problema di ottimizzazione è detto convesso ed esistono algoritmi efficienti per trovarne la soluzione ottima. Se le variabili decisionali sono discrete o la convessità non è soddisfatta, la risoluzione all'ottimo del problema diventa molto più onerosa e ci si accontenta quindi di una soluzione subottima. Tale soluzione può essere trovata in breve tempo e con poche risorse computazionali, usando algoritmi semplici e specifici chiamati algoritmi euristici. Argomento centrale di questa tesi è lo studio di uno dei quesiti teorici più importanti della Ricerca Operativa: trovare il rapporto di approssimazione, se esiste, di un dato algoritmo euristico. In altre parole, si è interessati a certificare che un certo algoritmo euristico produca sempre una soluzione il cui valore è confrontabile con l'ottimo globale. Un algoritmo euristico che ha un rapporto di approssimazione finito è detto algoritmo di approssimazione. In questo lavoro sono stati sviluppati nuovi algoritmi di approssimazione per il problema di machine scheduling con macchine uniformi. In letteratura si trovano diversi esempi di questi algoritmi. Le dimostrazioni sono tuttavia spesso complesse e difficili da generalizzare poiché sono organizzate in molti sottocasi e utilizzano proprietà strettamente dipendenti dall'algoritmo in questione. In questo lavoro si è invece cercato di delineare una metodologia che possa essere applicata e generalizzata a molti altri algoritmi. La ricerca dei vari rapporti di approssimazione viene riscritta come problema di ottimizzazione. Per risolverlo si propone una dimostrazione in due parti. Da un lato si utilizza un risolutore commerciale di Mixed-Integer Non-Linear Program che fornisce un bound superiore. Dall'altro si mostra che tale bound è stretto sviluppando un nuovo teorema molto generale ed applicabile a tutti gli algoritmi considerati. Dunque, unendo i risultati dell'ottimizzatore con le dimostrazioni analitiche, si dimostrano formalmente i rapporti di approssimazione. Con questo processo unificato, vengono replicati vari rapporti di approssimazione noti in letteratura senza il bisogno di utilizzare dimostrazioni specifiche per ogni algoritmo. Per quanto riguarda i nuovi algoritmi, il miglior rapporto di approssimazione ottenuto è di 1.1754. Inoltre, dallo stesso processo, si ottengono nuovi risultati riguardanti la dipendeza funzionale del rapporto di approssimazione rispetto alle velocità delle macchine. Infine, si verifica l'efficienza e l'efficacia dei nuovi algortimi, applicandoli a casi reali.