PERIODO: GENNAIO - FEBBRAIO La schedulazione come area di ricerca è motivata dalla sua applicazione pratica nella pianificazione della produzione (schedulazione di officina), nell’informatica e nei sistemi di telecomunicazioni (schedulazione real-time e gestione di risorse condivise). La schedulazione costituisce ad oggi una branca molto importante della Ricerca Operativa e dell’Ottimizzazione Combinatoria. In generale, la schedulazione è relativa all’allocazione ottima ad attività di risorse scarse nel tempo. Il Corso si propone di fornire le conoscenze di base sui modelli ed algoritmi di schedulazione con enfasi sulla complessità computazionale e sugli algoritmi di approssimazione. Verranno analizzati i principali modelli di schedulazione risolvibili con algoritmi polinomiali, si esporranno i concetti di base di complessità computazionale e verranno introdotti i principali schemi di approssimazione polinomiale. Verranno dati esempi di algoritmi approssimati per problemi paradigmatici. Scheduling as a research area is motivated by its practical application in production planning (machine scheduling) and in computer science and telecommunications systems (real-time scheduling and management of shared resources). Due to its practical relevance, scheduling is nowadays a fairly important branch of the Operations Research and Combinatorial Optimization research areas. In general, scheduling concerns the optimal allocation of scarce resources to activities over time. Aim of the course is to provide an introduction to models and algorithm for sequencing and scheduling with emphasis on computational complexity and approximation for sequencing and scheduling problems. The main polynomially solvable scheduling models will be introduced, basics on computational complexity will be provided and polynomial time approximation schemes will be presented with examples of approximation approaches for paradigmatic problems.

Introduzione ai problemi di schedulazione • Three-field Classificazione in 3 campi • Problemi di schedulazione risolubili in tempo polinomiale Complessità computazionale: • Algoritmi polinomiali • Classi di complessità P e NP • NP-completezza in senso forte ed in senso debole • Riduzioni polinomiali Approssimazione: • Approssimazione polinomiale • PTAS e FPTAS • Inapprossimabilità • Cenni sull’approssimazione esponenziale Introduction to sequencing and scheduling • Three-field classification • Polynomially solvable machine scheduling problems Computational complexity: • polynomial time algorithms • P and NP complexity classes • Strong and Weak NP-completeness • Polynomial time reductions Approximation: • Polynomial time approximation • PTAS and FPTAS • Inapproximability

...

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.