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