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



Скачать 35.79 Kb.
Дата29.11.2012
Размер35.79 Kb.
ТипСеминар
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский физико-технический институт

(государственный университет)
УТВЕРЖДАЮ

Проректор по учебной работе

Ю.А. Самарский

« »_____________ 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.

Похожие:

Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconСеминары нет Зачет Vсеместр лабораторные занятия нет Самостоятельная работа 2 часа в неделю
Информация, данные, знания. Аспекты работы с данными. Понятие об информационных технологиях. Особенности информационных систем. Задачи,...
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 34 часа Экзамен нет семинары 34 часа Зачет с оценкой 3 семестр лабораторные занятия нет
Программа обсуждена на заседании кафедры математических основ управления 15 мая 2011 г
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет
Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные занятия нет
Охватывает более простые, главным образом «одномерные» методы; третье задание относится к анализу существенно многомерных данных
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 32 часа Экзамен 8 семестр семинары -нет Зачет с оценкой нет лабораторные занятия нет
Некоторые задачи, приводящие к стохастическим аналогам обыкновенных дифференциальных уравнений (стохастические модели, возникающие...
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 32 часа Экзамен нет семинары нет Зачёт с оценкой 4 семестр лабораторные занятия 32 часа
Понятия базы данных, системы баз данных и субд. Требования к субд. Характеристики, функции субд
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет
Приближенные алгоритмы с гарантированными оценками точности. Анализ точности жадного алгоритма в задачах о покрытии, вершинном покрытии...
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет
Алфавиты, конструктивные объекты, их примеры. Понятие алгоритма, вычислимые функции. Формализация понятия алгоритма: частично-рекурсивные...
Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю iconЛекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов
Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org