Geum.ru

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

Вид материалаДокументы

Содержание


Всего часов
Подобный материал:

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

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. Что изучает теория расписаний?
  2. Что значит «решить» оптимизационную задачу?
  3. Некоторые понятия из теории вычислительной сложности задач

Глава 1. Модели и задачи теории расписаний
  1. Классификация задач Project Scheduling
  2. Классификация задач Machine Scheduling

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

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

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


Глава 3. Задача FLOW SHOP
  1. Анализ свойств оптимальных расписаний задачи Джонсона

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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


Глава 6. Эффективные алгоритмы решения многостадийных задач с использованием алгоритмов суммирования векторов.
  1. Теоремы о компактном и нестрогом суммировании векторов
  2. Приближенное решение задачи Джонсона с использованием компактного и нестрогого суммирования векторов.
  3. Алгоритм компактного суммирования векторов для задачи OPEN SHOP
  4. Алгоритм нестрогого суммирования векторов для задачи OPEN SHOP с тремя машинами
  5. Точное решение задачи OPEN SHOP методом Фиалы
  6. Двухмаршрутные задачи трех машин
  7. Задача Акерса-Фридман для трех машин
  8. Асимптотически точные алгоритмы решения задач JOB SHOP и DAG SHOP с произвольным числом машин

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

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

Приложения

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


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

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

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


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

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


Вопросы для подготовки к экзамену практически совпадают с программой курса "Теория расписаний". Ниже приводится образец экзаменационного билета, содержащего один теоретический вопрос и упражнение по теме, отличной от первого вопроса:
  1. Алгоритм решения задачи на построение ``наиболее раннего'' расписания для $n$ работ, если граф предшествований не содержит контуров положительного веса; в противном случае — нахождение такого контура.
  2. Докажите свойство ``блочности'' оптимального расписания задачи 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. Sequen­cing 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Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования.


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


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