Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю

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 с.