UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Operations Research

a.y. 2000-2001

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.

QUEUEING THEORY (16)

Markov chains and Markov processes with finite states. 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.

MARKOV DECISION PROCESSES (16)

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

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)