Docente/Teacher

prof. Andrea SCHAERF

Crediti/Credits

6 CFU

Obiettivi formativi specifici/Objectives

The course describes models, algorithmic techniques, and software tools for the solution of problems in scheduling, logistics, and timetabling.

Competenze acquisite/Acquired skills

- Ability to model a discrete optimization problem.
- Ability to develop appropriate algorithmic techniques for the solution of the problem.
- Ability to develop and test software for the solution of the problem.
- Ability to develop experimental analyses of the software.

Programma/Lectures and exercises

Discrete optimization problems in industrial context: scheduling of activities and machines; workforce and educational timetabling; traveling salesman and vehicle routing (8 hours).
Computational complexity: P and NP problem classes; techniques for exact and approximate greedy methods (2 hours).
Constraint programming: constraint programming, modeling, consistency, search, analysis (4 hours).
Tools for Constraint programming: use of the tool MiniZinc; modeling in MiniZinc; examples (6 hours).
Complements of C++: inheritance; polymorphism; virtual functions; abstract classes; C++ Frameworks (6 hours).
Optimizazion by enumeration and backtracking: frameworks for enumeration and backtracking in C++ (6 hours).
Local search optimization techniques: local search; basic elements and techniques of local search; Hill Climbing, Simulated Annealing, and Tabu Search; genetic algorithms and hybrid techniques (hints); tuning of parameters through statistical analysis (hints) (8 hours).
Tools for metaheuristic optimization: architecture and use of software O-O frameworks; use of the framework EasyLocal++ (12 hours).
Lab sessions (8 hours).

Bibliografia/References

- M. Pinedo, Planning and Scheduling in Manufacturing and Services (2ed), Springer, 2009

Modalità d'esame/Type of exam

oral exam and/or thesis

Additional material or information on line