UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Operations Research

a.y. 2001-2002

instructors: Franca Rinaldi and Paolo Serafini

Aims: The two modules complete the topics of the previous course on Optimization and provide an overview of theoretical (Decision Theory, Multi Objective Programming) and practical (Scheduling, Routing,..) modelling issues. Moreover, stochastic techniques will be presented in the second module to model queueing systems and multistage decision processes. Eventually students should be able to identify the mathematical model which best fits a real problem and to solve it.

MODULE # 1

(F. Rinaldi)

DYNAMIC PROGRAMMING (8 hours)

Optimality principle. Bellman's equation. Optimal control. Combinatorial problems.

HEURISTIC ALGORITHMS (10)

Local search, Greedy methods. Disaggregation. Tabu search. Simulated annealing. Genetic algorithms.

ROUTING (12)

Arc routing problems. Node routing problems. Capacitated vehicle routing problems.

SCHEDULING (12)

Pert. One machine problems. Parallel machines. Job shop models.

MULTI OBJECTIVE DECISION MAKING (6)

Pareto optimality. Order structures. Utility functions. Multi attribute decision making. Multi objective programming. Scalarization techniques. Interactive techniques.

MODULE # 2

(P. Serafini)

DECISION THEORY (16)

Criteria in presence of uncertainty. Criteria in presence of risk. Expected value of information. Use of Bayes' theorem to recompute probabilites. Decision trees. Lotteries and value function evaluation. Lotteries and subjective probability. Stochastic linear programming.

MARKOV DECISION PROCESSES (16)

Markov chains. Finite horizon formulation. Policy evaluation and optimal policy computation. Infinite horizon formulation, discounted and average cases. Use of dynamic programming and linear programming.

QUEUEING THEORY (16)

Markov processes. Birth-death processes. Poisson processes. M/M queues. Embedded Markov chains. Queues M/G/1, M/D/1 and M/Er/1. Pollaczek-Khinchin formula.

Exam: oral examination after each module.

For more information on Operatons Research and Optimization see INFORMS (Institute for Operations Research and Management Science) or CIRO (Centro Interuniversitario in Ricerca Operativa)