МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение
высшего  профессионального образования
Московский физико-технический институт
(государственный университет)

					УТВЕРЖДАЮ
                             		Проректор по учебной работе
					       Ю.А. Самарский
				«        »_____________ 2005 г.

П Р О Г Р А М М А

Курса по выбору: ТЕОРИЯ РАСПИСАНИЙ. 
АЛГОРИТМИЧЕСКИЙ ПОДХОД
по направлению    511600
все факультеты
кафедра математических основ управления
курс     IV
семестр   8
лекции    18 часов         Экзамен  – 8
семинары  –  нет         Зачёт–  нет
лабораторные занятия   –   16 часов
самостоятельная работа  –  2 часа в неделю

ВСЕГО ЧАСОВ    34

Программу и задание составил: к.ф.-м.н., доцент Лазарев А.А.

Программа утверждена на заседании кафедры математических основ управления 18 марта 2005 г.

Заведующий кафедрой 				С.А. Гуз

Основные понятия  теории расписаний. Классификация задач теории расписаний. Одностадийные и многостадийные системы. Понятие NP- полноты. Некоторые проблемы комбинаторной оптимизации: задачи Разбиения; задача о Ранце; задачи о Выполнимости. Связь с задачами теории расписаний и календарного планирования.
1.	Задачи одного прибора. Критерии: максимальное временное смещение; суммарное запаздывание; среднее время пребывание в системе; количество запаздывающих требований. Алгоритмы Смита, Джексона, Мура.
2.	Метод ветвей и границ. Constraint Programming. Сопоставительный анализ. Применение к задачам теории расписаний.
3.	Job-shop; flow-shop; open-shop проблемы. Алгоритмы решения.
4.	Задача 1|r_ j|L_{max}. Доказательство NP-трудности. Алгоритм Карлье. Полиномиально-разрешимые случаи. Теорема об абсолютной погрешности. Минимизация абсолютной погрешности. Метрика задач теории расписаний с минимаксными критериями. Псевдо-полиномиальные алгоритмы.
5.	Задача 1||\sum T_ j. Доказательство NP-трудности. Псевдо-полиномиальные алгоритмы решения. Связь с задачами Разбиения.
6.	Алгоритмический подход, основанный на методе интерполирования. Полином Лагранжа, корни Чебышева. Эпсилон-приближённые алгоритмы.
7.	Метаэвристические подходы к решению задач теории расписаний: метод муравьиных колоний; метод “отжига”; генетические алгоритмы; tabu search.
8.	Многостадийные системы. Задачи двух и более приборов. Алгоритм Джонсона. Алгоритмы, основанные на групповых технологиях.

СПИСОК ЛИТЕРАТУРЫ

1.	Brucker P.. Scheduling Algorithms. Springer, 2001, 365 p.
2.	Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы.- М.: Наука, 1984, 384 с.
3.	Танаев В.С., Сотсков Ю.Н., Струсевич В.А.  Теория расписаний. Многостадийные  системы.- М.: Наука, 1989, 328 с.

Подписано в печать 26.01.04
Формат 60  84. Бумага офсетная. Печать офсетная.
Усл. печ. л. 0.37.  Уч.-изд. л. 0.25. Тираж  200 экз. Заказ № .

Государственное образовательное учреждение
Высшего профессионального образования
Московский физико-технический институт
(государственный университет)
Отдел автоматизированных издательских систем «ФИЗТЕХ-ПОЛИГРАФ»
141700, Московская обл., г. Долгопрудный, Институтский пер., 9.