Название курса

Скачать 61.12 Kb.

Название	Название курса
Дата публикации	10.01.2015
Размер	61.12 Kb.
Тип	Документы

100-bal.ru > Математика > Документы

Организационно-методический раздел.

1.1Название курса.

Теория расписаний

Направление - математика

Раздел - общие математические и естественно-научные дисциплины

Семестр(ы) — 1-10

1.2Цели и задачи курса.

Дисциплина "Теория расписаний" предназначена для студентов механико-математических факультетов университетов.

Основной целью освоения студентами данной дисциплины является изучение методов математического моделирования реальных протекающих во времени дискретных управляемых процессов, а также — эффективных методов построения оптимальных (или близких к оптимальным) расписаний для этих процессов.

Для достижения поставленной цели выделяются задачи курса:

1) изучение теоретической части курса в соответствии с программой

2) сдача экзамена в соответствии с учебным планом.

1.3Требования к уровню освоения содержания курса.

По окончании изучения указанной дисциплины студент должен

иметь представление о месте и роли изучаемой дисциплины среди других наук;
знать содержание программы курса;
иметь навыки моделирования реальных протекающих во времени дискретных управляемых процессов;
иметь навыки построения эффективных алгоритмов точного или приближённого решения оптимизационных задач на построение расписаний различных процессов;
уметь выполнять анализ вычислительной сложности дискретных задач.

1.4Формы контроля

Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен экзамен.

Текущий контроль. Не предусмотрено.

Содержание дисциплины.

1.5Новизна.

Курс "Теория расписаний", к сожалению, не является традиционной дисциплиной математической подготовки студентов российских вузов. В то же время, он активно изучается в западных университетах (в рамках курсов по дискретной оптимизации либо в виде самостоятельной дисциплины), что обусловлено его значительной прикладной значимостью. Курс с аналогичным названием "Теория расписаний" читался в НГУ с 1973 по 1976 гг. (доцентом В.А. Перепелицей), однако с тех пор в этой науке произошли огромные изменения: значительно обновился и пополнился класс изучаемых моделей, появились новые мощные и эффективные методы решения трудных задач, при этом сделан значительный крен с точных методов в сторону разработки эффективных приближённых методов. Все эти изменения были учтены при разработке настоящего курса. При этом использовались как классические источники информации (монографии), так и в значительной мере — современные статьи.

1.6Тематический план курса.

Наименование разделов и тем	К о л и ч е с т в о ч а с о в
Наименование разделов и тем	Лекции	Семинары	Лаборатор- ные работы	Самостоятель-ная работа	Всего часов
Теория расписаний	68				68
Итого по курсу:	68				68

1.7Содержание отдельных разделов и тем.

Теория расписаний

Введение

Что изучает теория расписаний?
Что значит «решить» оптимизационную задачу?
Некоторые понятия из теории вычислительной сложности задач

Глава 1. Модели и задачи теории расписаний

Классификация задач Project Scheduling
Классификация задач Machine Scheduling

Глава 2. Задачи сетевого планирования

Минимизация произвольной неубывающей функции от моментов окончания работ при ограничениях предшествования, заданных взвешенным орграфом

6.1. Алгоритм на ациклическом графе

6.2. Алгоритм на произвольном взвешенном графе

Глава 3. Задача FLOW SHOP

Анализ свойств оптимальных расписаний задачи Джонсона

7.1. Анализ перестановочных расписаний

7.2. Соотношение оптимумов задач с прерываниями и без прерываний

Алгоритмы решения двухмашинной задачи Джонсона
NP-трудность трехмашинной задачи Джонсона
Разрешимые случаи трехмашинной задачи Джонсона

10.1. Условие Глебова

10.2. Условие Серваха

Использование динамичных нижних оценок оптимума при нахождении приближенного решения задачи FLOW SHOP с двумя машинами и неодновременным поступлением работ.

Глава 4. Задача JOB SHOP

Эффективно разрешимые случаи задачи JOB SHOP

12.1. Задача Акерса-Фридман на двух машинах

12.2. Задача JOB SHOP для двух работ. Графический метод Акерса

Глава 5. Задача OPEN SHOP

Эффективно разрешимые случаи задачи OPEN SHOP

13.1. Задача OPEN SHOP: две машины

13.2. Задача OPEN SHOP с прерываниями

Труднорешаемость задачи OPEN SHOP

14.1. NP-трудность задачи OPEN SHOP для трех машин

14.2. Трудность приближенного решения задачи OPEN SHOP

Алгоритмы приближенного решения задачи OPEN SHOP

15.1. Плотные расписания и жадные алгоритмы

15.2. Компьютерное доказательство теоремы о локализации оптимумов задачи OPEN SHOP для трех машин

Глава 6. Эффективные алгоритмы решения многостадийных задач с использованием алгоритмов суммирования векторов.

Теоремы о компактном и нестрогом суммировании векторов
Приближенное решение задачи Джонсона с использованием компактного и нестрогого суммирования векторов.
Алгоритм компактного суммирования векторов для задачи OPEN SHOP
Алгоритм нестрогого суммирования векторов для задачи OPEN SHOP с тремя машинами
Точное решение задачи OPEN SHOP методом Фиалы
Двухмаршрутные задачи трех машин
Задача Акерса-Фридман для трех машин
Асимптотически точные алгоритмы решения задач JOB SHOP и DAG SHOP с произвольным числом машин

Глава 7. Аппроксимационные схемы решения задач на построение кратчайших расписаний

PTAS для задачи OPEN SHOP с ограниченным числом машин
Линейная схема Янсена-Солис-Оба-Свириденко для JOB SHOP с ограниченным числом машин
PTAS для цеховой задачи FLOW SHOP с произвольным числом машин и ограниченным числом цехов

Глава 8. Анализ задач с прерываниями операций

Структурные теоремы о числе прерываний.
Когда существует решение с прерываниями в целочисленных точках?

Приложения

1.8Перечень примерных контрольных вопросов и заданий для самостоятельной работы.

Не предусмотрено.

2Учебно-методическое обеспечение дисциплины

2.1Темы рефератов (курсовых работ).

Не предусмотрено.

2.2Образцы вопросов для подготовки к экзамену (дифференцированному зачету, зачету).

Вопросы для подготовки к экзамену практически совпадают с программой курса "Теория расписаний". Ниже приводится образец экзаменационного билета, содержащего один теоретический вопрос и упражнение по теме, отличной от первого вопроса:

Алгоритм решения задачи на построение ``наиболее раннего'' расписания для $n$ работ, если граф предшествований не содержит контуров положительного веса; в противном случае — нахождение такого контура.
Докажите свойство ``блочности'' оптимального расписания задачи JOB SHOP для двух машин.

2.3Список основной и дополнительной литературы.

МОНОГРАФИИ:

1) Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

2) Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.

3) Танаев В.С., Гордон В.С., Шафранский Я.Н. Теория расписаний. Одностадийные системы. М.: Наука, 1984.

4) Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы, М.: Наука, 1989. 328 с.

5) Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.

6) Харари Ф. Теория графов. М.: Мир, 1973.

7) Brucker P. Scheduling Algorithms., Berlin, Heidelberg, New York: Springer-Verlag, 1995.

8) Pinedo M. Scheduling: Theory, Algorithms, and Systems // Prentice-Hall, Englewood Cliffs, New Jersey, 1995.

9) Pinedo M., Chao X. Operations Scheduling with Applications in Manufacturing and Services // Irwin/McGraw-Hill, 1999.
СТАТЬИ:

1) Akers, S.B. A graphical approach to production scheduling problems // Oper. Res. 1956. V. 4. P. 244-245.

2) Akers, S.B. and Friedman, J. A non-numerical approach to production scheduling problems // Oper. Res. 1955. V. 3. P. 429-442.

3) Chen B., Potts C.N., and Woeginger G.J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization, Boston: Kluwer Acad. Publ., V. 3. 1998. P. 21-169.

4) Jansen, K., Solis-Oba, R., and Sviridenko, M. Makespan minimization in job shops: a polynomial time approximation scheme // Proceedings of the 31st Annual ACM Symp. on Theory of Computing. 1999. P. 394-399.

5) Gonzalez, T. and Sahni, S. Open Shop Scheduling to Minimize Finish Time., J.ACM 1976. V. 23, no.4. P. 665-679.

6) Kashyrskikh, K.N., Potts, C.N., and Sevastianov, S.V. 3/2-Approximation algorithm for two-machine flow-shop sequencing subject to release dates, Discrete Appl. Math. 2001. V. 114. P. 255-271.

7) Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. Sequencing and scheduling: algorithms and complexity // Handbooks in Operations Research and Management Science V.4. Amsterdam: North Holland, 1993. P. 445-522.

8) Sevastianov, S. Nonstrict vector summation in multi-operation scheduling, Annals of Oper. Res. 1998. V. 83. P. 179-211.

9) Sevastianov, Sergey V., Woeginger, Gerhard J. Makespan minimization in

preemptive two machine job shops, Computing 1998. V. 60, no.1, 73-79.

10) Sevastianov, S.V. and Woeginger, G.J. Linear time approximation scheme for the multiprocessor open shop problem, Discrete Appl. Math. 2001. V. 114. P. 273-288.

11) Shmoys, D.B., Stein, C., and Wein, J. Improved Approximation Algorithms for Shop Scheduling Problems// SIAM J. on Computing. 1994. V. 23. P. 617-632.

12) Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A.J., Lenstra, J.K., Sevastianov, S.V., and Shmoys, D.B. Short Shop Schedules, Oper.Res. 1997. V. 45, no.2, 288-294.

2.4Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.

Не предусмотрено.

Составил доцент кафедры кибернетики Севастьянов С.В.

Добавить документ в свой блог или на сайт

Похожие:

	Название: 900 дней и ночей Название темы и раздела учебного курса: Великая война и Великая Победа. История нашей страны		Рабочая программа по географии (название учебного предмета, курса,... Программа курса географии 5–9 классов составлена на основе программы География: программа: 5 – 9 классы / А. А. Летягин, И. В. Душина...
	Название курса Основной курс "Линейная алгебра и аналитическая геометрия" предназначен для студентов первого курса отделения прикладной инфоматики...		Название курса Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики...
	Название курса «Алгебра». 9 класс Цель изучения курса: изучить свойства и графики элементарных функций, научиться использовать функционально-графические представления...		Рабочая программа по истории (название учебного предмета, курса,... ...
	Программа курса «Философия» Название курса. «Философия». Курс относится к разделу Федерального государственного образовательного стандарта высшего профессионального...		Календарно-тематический план по магистерской программе «Мировая экономика»... Календарно-тематический план по магистерской программе «Мировая экономика» по дисциплине (название читаемого курса) Экономика международного...
	Пояснительная записка цель данного курса Название курса: «Основы информационной культуры». Программа рассчитана на 64 часа и предназначается для учащихся 9-11 классов. Данный...		Освоение методики экспериментального исследования мира на уроках тризформатики в начальной школе Доклад базируется на «Пермской версии» пропедевтического курса информатики [1–4] (рабочее название курса – «тризформатика») и опыте...
	Название курса Смирнова Е. В., ст преподаватель кафедры дидактики и частных методик ипкиппро огпу		Название предмета или курса Рабочая программа учебного курса по алгебре для 9 класса разработана на основе Примерной программы основного общего образования (базовый...
	Название предмета или курса Рабочая программа учебного курса по алгебре для 8 класса разработана на основе Примерной программы основного общего образования (базовый...		Название Примечание Самостоятельная работа студентов в рамках учебного курса «Культурология» включает в себя
	Программа курса для специальности: (перечень специальностей, для... Программа курса составлена в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования...		Название курса Выучить новые слова, найти в тексте все глаголы и объяснить употребление глагольных времен

Школьные материалы

Название курса

Организационно-методический раздел.

1.1Название курса.

1.2Цели и задачи курса.

1.3Требования к уровню освоения содержания курса.

1.4Формы контроля

1.5Новизна.

1.6Тематический план курса.

1.7Содержание отдельных разделов и тем.

6.1. Алгоритм на ациклическом графе

6.2. Алгоритм на произвольном взвешенном графе

7.1. Анализ перестановочных расписаний

7.2. Соотношение оптимумов задач с прерываниями и без прерываний

10.1. Условие Глебова

10.2. Условие Серваха

12.1. Задача Акерса-Фридман на двух машинах

12.2. Задача JOB SHOP для двух работ. Графический метод Акерса

13.1. Задача OPEN SHOP: две машины

13.2. Задача OPEN SHOP с прерываниями

14.1. NP-трудность задачи OPEN SHOP для трех машин

14.2. Трудность приближенного решения задачи OPEN SHOP

15.1. Плотные расписания и жадные алгоритмы

15.2. Компьютерное доказательство теоремы о локализации оптимумов задачи OPEN SHOP для трех машин

1.8Перечень примерных контрольных вопросов и заданий для самостоятельной работы.

2Учебно-методическое обеспечение дисциплины

2.1Темы рефератов (курсовых работ).

2.2Образцы вопросов для подготовки к экзамену (дифференцированному зачету, зачету).

2.3Список основной и дополнительной литературы.

2.4Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.

Похожие: