Servizi per la didattica
PORTALE DELLA DIDATTICA

Scheduling models and algorithms: computational complexity and approximation

01SCQRP

A.A. 2018/19

Course Language

Inglese

Course degree

Doctorate Research in Gestione, Produzione E Design - Torino

Course structure
Teaching Hours
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Teaching assistant
Espandi

Context
SSD CFU Activities Area context
*** N/A ***    
Valutazione CPD /
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.
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
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.
In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.
Esporta Word


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti