Advanced Scheduling Systems
Docente/Teacher
prof. Andrea SCHAERF
Crediti/Credits
6 CFU
Lingua/Language
Inglese/English
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